In: ACM Computing Surveys, Vol. 29, No. 1, pages 30-81. 1997.
Abstract: A great variety of theories and formalisms dealing with nondeterminism have been developed during the last two decades. There are the denotational models based on power domains, the predicate transformers for the choice construct, and modifications of the lambda calculus. Nondeterminism arises in a natural way when discussing concurrency, and models of concurrency typically also model nondeterminism. There are numerous variants of process languages and algebra, event structures, state transition systems, and Petri nets. One of the main reasons for considering nondeterminism in computer science is the need for abstraction, allowing one to disregard irrelevant aspects of actual computations. The nondeterminism of concurrent systems usually arises as an abstraction of time.
Keywords: Petri nets, nondeterminism, process algebras, process languages.