{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:42:55Z","timestamp":1760121775472,"version":"3.41.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,6,25]],"date-time":"2009-06-25T00:00:00Z","timestamp":1245888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCSE Bull."],"published-print":{"date-parts":[[2009,6,25]]},"abstract":"<jats:p>Nondeterminism is a fundamental concept in computer science that appears in various contexts such as automata theory, algorithms and concurrent computation. We present a taxonomy of the different ways that nondeterminism can be defined and used; the categories of the taxonomy are domain, nature, implementation, consistency, execution and semantics. An historical survey shows how the concept was developed from its inception by Rabin &amp; Scott, Floyd and Dijkstra, as well the interplay between nondeterminism and concurrency. Computer science textbooks and pedagogical software are surveyed to determine how they present the concept; the results show that the treatment of nondeterminism is generally fragmentary and unsystematic. We conclude that the teaching of nondeterminism must be integrated through the computer science curriculum so that students learn to see nondeterminism both in terms of abstract mathematical entities and in terms of machines whose execution is unpredictable.<\/jats:p>","DOI":"10.1145\/1595453.1595495","type":"journal-article","created":{"date-parts":[[2009,8,24]],"date-time":"2009-08-24T14:08:31Z","timestamp":1251122911000},"page":"141-160","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["The concept of nondeterminism"],"prefix":"10.1145","volume":"41","author":[{"given":"Michal","family":"Armoni","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]},{"given":"Mordechai","family":"Ben-Ari","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2009,6,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Abrial J.R. (1996). The B Book: Assigning Programs to Meanings. Cambridge UK: Cambridge University Press.   Abrial J.R. (1996). The B Book: Assigning Programs to Meanings. Cambridge UK: Cambridge University Press.","DOI":"10.1017\/CBO9780511624162"},{"issue":"4","key":"e_1_2_1_2_1","first-page":"325","article-title":"Introducing non-determinism","volume":"25","author":"Armoni M.","year":"2006","journal-title":"Journal of Computing in Mathematics and Science Teaching"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/08993400701442885"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1352135.1352141"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682396"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90005-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289263"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90055-5"},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science 366","volume-title":"Odijk, E., Rem, M. &amp","author":"Back R.J.R.","year":"1989"},{"volume-title":"Proceedings of the 22nd Annual Hawaii International conference on System Sciences, Washington, DC: IEEE Computer Society Press, 231--242","year":"1989","author":"Back R.J.R.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Back R.J.R. &amp; von Wright J. (1989). Refinement calculus part I: sequential nondeterministic programs. In de Bakker J. W. de Roever W.-P. &amp; Rozenberg G. (Eds.) Stepwise Refinement of Distributed Systems Models Formalisms Correctness REX Workshop and in Goos G. and Hartmanis J. (Eds.) Lecture Notes in Computer Science 430 42--66.   Back R.J.R. &amp; von Wright J. (1989). Refinement calculus part I: sequential nondeterministic programs. In de Bakker J. W. de Roever W.-P. &amp; Rozenberg G. (Eds.) Stepwise Refinement of Distributed Systems Models Formalisms Correctness REX Workshop and in Goos G. and Hartmanis J. (Eds.) Lecture Notes in Computer Science 430 42--66.","DOI":"10.1007\/3-540-52559-9_60"},{"volume-title":"Proceedings of the 3rd Colloquium on Automata, Languages and Programming","year":"1976","author":"de Bakker J.W.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the Wold Congress on Formal Methods in the Development of Computing Systems-Volume I (September 20-24","year":"1999","author":"Behm P.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Ben-Ari M. (2006). Principles of Concurrent and Distributed Programming (Second Edition). London: UK Addison-Wesley.   Ben-Ari M. (2006). Principles of Concurrent and Distributed Programming (Second Edition). London: UK Addison-Wesley."},{"key":"e_1_2_1_15_1","unstructured":"Ben-Ari M. (2008). Principles of Spin. London UK: Springer.  Ben-Ari M. (2008). Principles of Spin. London UK: Springer."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijhcs.2003.10.005"},{"issue":"1","key":"e_1_2_1_17_1","first-page":"21","article-title":"Learning concurrency as an entry point to the community of CS practitioners","volume":"23","author":"Ben-David Kolikant Y.","year":"2004","journal-title":"Journal of Computers in Mathematics and Science Teaching"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90040-X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014683"},{"volume-title":"Braffort, P. &amp","year":"1963","author":"Chomsky N.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_23_1","unstructured":"Cormen T.H. Leiserson C.E. Rivest R.L. &amp; Stein C. (2001). Introduction to Algorithms Second Edition. Cambridge MA: MIT Press and Boston MA: McGraw-Hill.   Cormen T.H. Leiserson C.E. Rivest R.L. &amp; Stein C. (2001). Introduction to Algorithms Second Edition. Cambridge MA: MIT Press and Boston MA: McGraw-Hill."},{"key":"e_1_2_1_24_1","unstructured":"Davis M. (1958). Computability &amp; Unsolvability. New-York: McGraw-Hill.  Davis M. (1958). Computability &amp; Unsolvability. New-York: McGraw-Hill."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Davis M.D. Sigal R. &amp; Weyuker E.J. (1994). Computability Complexity and Languages Fundamentals of Theoretical Computer Science (Second Edition). San-Diego CA: Academic Press.   Davis M.D. Sigal R. &amp; Weyuker E.J. (1994). Computability Complexity and Languages Fundamentals of Theoretical Computer Science (Second Edition). San-Diego CA: Academic Press.","DOI":"10.1016\/B978-0-08-050246-5.50020-9"},{"volume-title":"F. Genuys (Ed.)","year":"1968","author":"Dijkstra E.W.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360975"},{"key":"e_1_2_1_28_1","unstructured":"Dijkstra E.W. (1976). A Discipline of Programming. Englewood Cliffs NJ: Prentice-Hall.   Dijkstra E.W. (1976). A Discipline of Programming. Englewood Cliffs NJ: Prentice-Hall."},{"volume-title":"Metropolis, N., Howlett, J. &amp","year":"1980","author":"Dijkstra E.W.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/365691.365962"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321420.321422"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90006-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80001-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90039-6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/563517.563364"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90038-4"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Harel D. (1987). Algorithmics: The Spirit of Computing. Reading MA: Addison-Wesley.   Harel D. (1987). Algorithmics: The Spirit of Computing. Reading MA: Addison-Wesley.","DOI":"10.1007\/978-3-642-27266-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512782"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/363235.363259"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322088"},{"key":"e_1_2_1_42_1","unstructured":"Hoare C.A.R. (1985\/2004). Communicating Sequential Processes. Hemel Hempstead UK: Prentice Hall International. http:\/\/usingcsp.com\/cspbook.pdf (accessed 6 March 2007).  Hoare C.A.R. (1985\/2004). Communicating Sequential Processes. Hemel Hempstead UK: Prentice Hall International. http:\/\/usingcsp.com\/cspbook.pdf (accessed 6 March 2007)."},{"key":"e_1_2_1_43_1","unstructured":"Holzmann G.J. (2004). The Spin Model Checker: Primer and Reference Manual. Boston MA: Addison-Wesley.   Holzmann G.J. (2004). The Spin Model Checker: Primer and Reference Manual. Boston MA: Addison-Wesley."},{"key":"e_1_2_1_44_1","unstructured":"Hopcroft J.E. Motwani R. &amp; Ullman J.D. (2007). Introduction to Automata Theory Languages and Computation (Third Edition). Boston MA: Addison-Wesley.   Hopcroft J.E. Motwani R. &amp; Ullman J.D. (2007). Introduction to Automata Theory Languages and Computation (Third Edition). Boston MA: Addison-Wesley."},{"key":"e_1_2_1_45_1","unstructured":"Hopcroft J.E. &amp; Ullman J.D. (1969). Formal Languages and their Relation to Automata. Reading MA: Addison-Wesley.   Hopcroft J.E. &amp; Ullman J.D. (1969). Formal Languages and their Relation to Automata. Reading MA: Addison-Wesley."},{"key":"e_1_2_1_46_1","unstructured":"Hopcroft J.E. &amp; Ullman J.D. (1979). Introduction to Automata Theory Languages and Computation. Reading MA: Addison-Wesley.   Hopcroft J.E. &amp; Ullman J.D. (1979). Introduction to Automata Theory Languages and Computation. Reading MA: Addison-Wesley."},{"key":"e_1_2_1_47_1","unstructured":"IEEE Computer Society\/ACM (2001). Computing Curricula 2001: Computer Science-Final Report. http:\/\/www.sigcse.org\/cc2001\/ (accessed 1 March 2007).  IEEE Computer Society\/ACM (2001). Computing Curricula 2001: Computer Science-Final Report. http:\/\/www.sigcse.org\/cc2001\/ (accessed 1 March 2007)."},{"key":"e_1_2_1_48_1","unstructured":"INMOS\n\n  \n   (1988). Occam 2 Reference Manual Hemel Hempstead UK: Prentice Hall International.  INMOS (1988). Occam 2 Reference Manual Hemel Hempstead UK: Prentice Hall International."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.2003.1203057"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682548"},{"key":"e_1_2_1_51_1","unstructured":"Kleinberg J. &amp; Tardos &amp;#201;&amp;#201;. (2006). Algorithm Design. Boston MA: Addison-Wesley.   Kleinberg J. &amp; Tardos &amp;#201;&amp;#201;. (2006). Algorithm Design. Boston MA: Addison-Wesley."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/361082.361093"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/567446.567463"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5384"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5385"},{"key":"e_1_2_1_57_1","unstructured":"Lewis H.R. &amp; Papadimitriou C.H. (1981). Elements of the Theory of Computation. Englewood Cliffs: NJ: Prentice-Hall.   Lewis H.R. &amp; Papadimitriou C.H. (1981). Elements of the Theory of Computation. Englewood Cliffs: NJ: Prentice-Hall."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/800161.805161"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(70)90002-0"},{"volume-title":"Braffort, P. &amp","year":"1963","author":"McCarthy J.","key":"e_1_2_1_60_1"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322134"},{"key":"e_1_2_1_62_1","unstructured":"Minsky M.L. (1967). Computation: Finite and Infinite Machines. Englewood Cliffs NJ: Prentice-Hall.   Minsky M.L. (1967). Computation: Finite and Infinite Machines. Englewood Cliffs NJ: Prentice-Hall."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/44501.44503"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90011-6"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/800197.806039"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1118178.1118212"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205035"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"e_1_2_1_69_1","first-page":"472","article-title":"Dijkstra's predicate transformers, non-determinism, recursion and termination","volume":"45","author":"de Roever W.P.","year":"1976","journal-title":"Proceedings of the Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science"},{"issue":"9","key":"e_1_2_1_70_1","first-page":"36","article-title":"JFLAP: An Interactive Formal Languages and Automata Package. Sudbuy, MA: Jones and Bartlett. Ross, P.E. (2005). The Exterminators","volume":"42","author":"Rodger S.H.","year":"2006","journal-title":"IEEE Spectrum"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/800169.805439"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90306-1"},{"key":"e_1_2_1_73_1","unstructured":"Sipser M. (1997). Introduction to the Theory of Computation. Boston MA: PWS Publishing.   Sipser M. (1997). Introduction to the Theory of Computation. Boston MA: PWS Publishing."},{"key":"e_1_2_1_74_1","unstructured":"Spivey J.M. (1992). The Z Notation: A Reference Manual 2nd edition. Hemel Hempstead UK: Prentice Hall International.   Spivey J.M. (1992). The Z Notation: A Reference Manual 2nd edition. Hemel Hempstead UK: Prentice Hall International."},{"volume-title":"Computing Curricula '91","year":"1991","author":"Tucker A.B.","key":"e_1_2_1_75_1"},{"key":"e_1_2_1_76_1","unstructured":"Warwick W. (2001). The Conceptual Development of Nondeterminism in Theoretical Computer Science. Unpublished Ph.D. thesis Indiana University.  Warwick W. (2001). The Conceptual Development of Nondeterminism in Theoretical Computer Science. Unpublished Ph.D. thesis Indiana University."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/248621.248623"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1124706.1121460"}],"container-title":["ACM SIGCSE Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595453.1595495","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1595453.1595495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:04Z","timestamp":1750253404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595453.1595495"}},"subtitle":["its development and implications for teaching"],"short-title":[],"issued":{"date-parts":[[2009,6,25]]},"references-count":77,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6,25]]}},"alternative-id":["10.1145\/1595453.1595495"],"URL":"https:\/\/doi.org\/10.1145\/1595453.1595495","relation":{},"ISSN":["0097-8418"],"issn-type":[{"type":"print","value":"0097-8418"}],"subject":[],"published":{"date-parts":[[2009,6,25]]},"assertion":[{"value":"2009-06-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}