Non-Determinism and Underspecification

Underspecified command is command that gives one result, but program semantics does not say which one.

  • Example: parameter order in C compilers is underspecified
  • user cannot assume that parameters are evaluated e.g. left-to-right

In contrast, we now consider non-deterministic commands that simultaneously yields multiple results

  • typically, if there exists a choice for which program gives correct result, the language implementation should find it

Languages with non-deterministic commands to more elegantly express search algorithms

This is like non-deterministic automaton, but we user it for arbitrary programs, not just finite-state machines

Note: subset construction still works - we could be computing sets of results

  • but storing sets of states is expensive
  • many implementations are instead based on back-tracking


  • easier programming of difficult problems (deciphering, natural language processing, scheduling)
  • program testing: searching for error in programs