Automata on infinite objects and their applications to logic and programming
type: Item
instance of: scholarly article
title: Automata on infinite objects and their applications to logic and programming
zbMATH Open document ID: 0691.68068
DOI: 10.1016/0890-5401(89)90046-1
published in: Information and Computation
publication date: 1989-01-01T00:00:00Z
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.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68T99
zbMATH DE Number: 4131683
zbMATH Keywords: finite automata
zbMATH Keywords: infinite words
zbMATH Keywords: infinite trees
zbMATH Keywords: tree automata
zbMATH Keywords: program schemas
author: M. Nivat
author: Ahmed Saoudi
MaRDI profile type: Publication
full work available at URL: 0890-5401(89)90046-1
OpenAlex ID: W2088892929
cites work: Formal computations of non deterministic recursive program schemes
cites work: Q3900995
cites work: The minimalization of tree automata
cites work: Q5525343
cites work: Alternation
cites work: Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
cites work: Theories of automata on \(\omega\)-tapes: a simplified approach
cites work: Fundamental properties of infinite trees
cites work: Q4079524
cites work: Deciding full branching time logic
cites work: Q4954439
cites work: Pushdown tree automata
cites work: First-order dynamic logic
cites work: Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
cites work: Algorithm = logic + control
cites work: Definability in dynamic logic
cites work: Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices
cites work: Q3748266
cites work: Q4726235
cites work: Testing and generating infinite sequences by a finite automaton
cites work: Q3857704
cites work: Q3907077
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Q5616162
cites work: Infinitary tree languages recognized by \(\omega\)-automata
cites work: Q4770337
cites work: The greatest fixed-points and rational omega-tree languages
cites work: A note on \(\omega\)-regular languages
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
cites work: Q3967525
Recommended article: Q3746905
Recommended article: Topological characterizations of infinite tree languages
Recommended article: Q4273667
Recommended article: On automata on infinite trees
Recommended article: Q3823145
Recommended article: Q4737000
Recommended article: Uniform inevitability is tree automaton ineffable
Recommended article: PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS
description: scientific article; zbMATH DE number 4131683