Alternating automata, the weak monadic theory of the tree, and its complexity. (English) Zbl 0617.03020

Muller, David E.; Saoudi, Ahmed; Schupp, Paul E.

Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 275-283 (1986).

[For the entire collection see Zbl 0587.00019.]
This article continues the point of view that the ”natural” theory of automata on trees is that of automata which are alternating in the sense of D. E. Muller and P. E. Schupp [”Alternating automata on infinite objects and Rabin’s theorem”, Theor. Comput. Sci. (to appear)]. We use alternating automata to give a ”direct” automata-theoretic characterization of the languages of k-ary trees which are weakly- definable, that is to say, definable by a formula in the weak monadic logic of the tree where one allows quantification only over finite sets. We define a ”weak” acceptance condition and show that a language is weakly definable if and only if it is accepted by an alternating automaton using the weak acceptance condition. Secondly, alternating automata are closely related to complexity and we give a simple proof of a bound on the complexity of deciding formulas whose prenex normal form has n alternations of quantifiers.

MSC:

03D05	Automata and formal grammars in connection with logical questions
03B25	Decidability of theories and sets of sentences
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

automata on trees; alternating automata; weak monadic logic; alternations of quantifiers

Citations:

Zbl 0587.00019