Fixed-point Logics with Nondeterministic Choice
Anuj Dawar · Journal of Logic and Computation · 2003
The inductive operators nio (due to Arvind and Biswas) and c-ifp (due to Gire and Hoang) allow for a nondeterministic choice of tuples at each stage in the inductive construction of a relation. We consider the extensions of first-order logic with each of these operators, presenting a formal semantics for each, in which formulae denote sets of relations. We derive normal forms for these formulae and prove that the operators have equal expressive power. Finally, we show that, by using an appropriate notion of satisfaction for nondeterministic formulae, essentially any computational complexity class defined in terms of nondeterministic Turing machines operating within polynomial time bounds can be expressed in terms of nondeterministic fixed-point formulae.