Automata on infinite objects and their applications to logic and programming

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Artificial intelligence (68T99)

Review text

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.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Automata on infinite objects and their applications to logic and programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582913)