The Complexity of Decision Problems in Automata Theory and Logic.

摘要

The inherent computational complexity of a variety of decision problems in mathematical logic and the theory of automata is analyzed in terms of Turing machine time and space and in terms of the complexity of Boolean networks. The problem of deciding whether a star-free expression (a variation of the regular expressions of Kleene used to describe languages accepted by finite automata) defines the empty set is shown to require time and space exceeding any composition of functions exponential in the length of expressions. In particular,this decision problem is not elementary-recursive in the sense of Kalmar. The emptiness problem can be reduced efficiently to decision problems for truth or satisfiability of sentences in the first order monadic theory of (N,<),the first order theory of linear orders,and the first order theory of two successors and prefix,among others. It follows that the decision problems for these theories are also not elementary-recursive. (Modified author abstract)