NotesFAQContact Us
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ846665
Record Type: Journal
Publication Date: 2009-Aug
Pages: 26
Abstractor: As Provided
Reference Count: 0
ISSN: ISSN-0926-7220
The Concept of Nondeterminism: Its Development and Implications for Teaching
Armoni, Michal; Ben-Ari, Mordechai
Science & Education, v18 n8 p1005-1030 Aug 2009
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 & Scott, Floyd and Dijkstra, as well as 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.
Springer. 233 Spring Street, New York, NY 10013. Tel: 800-777-4643; Tel: 212-460-1500; Fax: 212-348-4505; e-mail:; Web site:
Publication Type: Journal Articles; Reports - Descriptive
Education Level: N/A
Audience: Teachers
Language: English
Sponsor: N/A
Authoring Institution: N/A