Automata on infinite objects and their applications to logic and programming

DOI10.1016/0890-5401(89)90046-1zbMath0691.68068OpenAlexW2088892929MaRDI QIDQ582913

Ahmed Saoudi, Maurice Nivat

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90046-1

zbMATH Keywords

finite automatatree automatainfinite wordsinfinite treesprogram schemas

Mathematics Subject Classification ID

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

Related Items

A branching time logic with past operators ⋮ Parallel generation of infinite images ⋮ Generalized automata on infinite trees and Muller-McNaughton's theorem ⋮ A unified approach for showing language inclusion and equivalence between various types of \(\omega\)-automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinitary tree languages recognized by \(\omega\)-automata
• A note on \(\omega\)-regular languages
• Fundamental properties of infinite trees
• Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices
• The greatest fixed-points and rational omega-tree languages
• Definability in dynamic logic
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• First-order dynamic logic
• Pushdown tree automata
• Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
• Deciding full branching time logic
• Formal computations of non deterministic recursive program schemes
• Alternation
• Algorithm = logic + control
• Generalized finite automata theory with an application to a decision problem of second-order logic
• The minimalization of tree automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees