Automata on infinite objects and their applications to logic and programming (Q582913)

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.