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

Applications:

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