CC programs with both in- and non-determinism: A concurrent semantics
Ugo Montanari, Francesca Rossi, Vijay Saraswat · Lecture notes in computer science · 1994
We present a concurrent semantics for concurrent constraint (CC) programs with both (“committed choice”) indeterminism and (“back-tracking”) nondeterminism. The semantics extends the previous semantics for Indeterminate CC by (1) allowing each state to contain different or-parallel components and (2) splitting the concurrency relation into two to distinguish between and- and or-concurrency. Thereby, the construction produces a single representation (an And-or contextual net) that captures all the significant relations between events in program runs: concurrency, causal dependency, indeterminism and nondeterminism. We believe this is a first step towards the formal analysis of the concurrent semantics of practical CC languages containing both in- and non-determinism, such as AKL [HJ90].