Automata on infinite objects and their applications to logic and programming (Q582913): Difference between revisions

Several aspects of the theory of finite automata accepting infinite words or infinite trees are considered. Automata on infinite words are classified in a systematic way according to the mode of acceptance; the well-known Büchi and Muller automata form two of the classes. The same classification scheme is then applied to both top-down and bottom-up tree automata on infinite trees, and the relationships between the corresponding families of tree languages are studied. For each type both the deterministic and the nondeterministic versions are considered. \(\{\) The interested reader should also note the related study by \textit{T. Hayashi} and \textit{S. Miyano} [Bull. Inf. Cybern. 21, No.3/4, 71-82 (1985; Zbl 0607.68060)] in which six of the acceptance modes considered here appear.\(\}\) Also, corresponding types of grammars generating infinite trees are introduced. Then the effect of a control language of infinite words restricting the computations of tree automata is studied. Finally, some results concerning rational program schemas, rational logic programs and a corresponding class of second order formulae are obtained by relating them to automata on infinite trees.