Hierarchies of weak automata and weak monadic formulas (Q805253)

Given a set of trees, define its Muller index (the Rabin index, respectively) as the minimal Muller (Rabin) index of the alternating finite automata (afa) representing this set. First, it is proved that the two indices - the Muller index and the Rabin index - coincide, both in weak and in strong conditions. The main result proves that for k successor monadic arithmetics, a weak formula with a bounded suffix has m unbounded quantifiers (m\(\geq 2)\) in the prefix iff it is represented by a weak afa of index m. An infinite hierarchy of weak indices for afa is obtained in this way. See defnitions in the related papers by \textit{D. E. Muller}, \textit{P. E. Schupp} [Theor. Comput. Sci. 54, 264-276 (1987; Zbl 0636.68108) and Lect. Notes Comput. Sci. 192, 100-107 (1985; Zbl 0608.03004)].