Automata on infinite objects and their applications to logic and programming

DOI10.1016/0890-5401(89)90046-1MaRDI QIDQ582913zbMATH OpenOpenAlexFDO

Authors M. Nivat, Ahmed Saoudi

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 automatainfinite treesinfinite wordsprogram schemastree automata

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 3982544
• Topological characterizations of infinite tree languages
• scientific article; zbMATH DE number 475420
• On automata on infinite trees
• scientific article; zbMATH DE number 4096786
• scientific article; zbMATH DE number 2086519
• Uniform inevitability is tree automaton ineffable
• PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS

Cites work

• A note on \(\omega\)-regular languages
• Algorithm = logic + control
• Alternation
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deciding full branching time logic
• Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
• Definability in dynamic logic
• Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices
• First-order dynamic logic
• Formal computations of non deterministic recursive program schemes
• Fundamental properties of infinite trees
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 3983141 (Why is no real title available?)
• scientific article; zbMATH DE number 3658971 (Why is no real title available?)
• scientific article; zbMATH DE number 3709584 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3790415 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3999901 (Why is no real title available?)
• scientific article; zbMATH DE number 3445172 (Why is no real title available?)
• scientific article; zbMATH DE number 1456950 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• Infinitary tree languages recognized by \(\omega\)-automata
• Pushdown tree automata
• Testing and generating infinite sequences by a finite automaton
• The greatest fixed-points and rational omega-tree languages
• The minimalization of tree automata
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Theory of -languages. II: A study of various models of - type generation and recognition

Cited in

(29)

• Variétés d'automates descendants d'arbres infinis
• Topological characterizations of infinite tree languages
• Generalized automata on infinite trees and Muller-McNaughton's theorem
• On automata on infinite trees
• Infinite trees and automaton-definable relations over -words
• A branching time logic with past operators
• Weak Muller acceptance conditions for tree automata
• Automata on infinite trees
• scientific article; zbMATH DE number 1670767 (Why is no real title available?)
• scientific article; zbMATH DE number 1678376 (Why is no real title available?)
• Automata and semigroups recognizing infinite words
• scientific article; zbMATH DE number 4208050 (Why is no real title available?)
• Parallel generation of infinite images
• scientific article; zbMATH DE number 3972187 (Why is no real title available?)
• scientific article; zbMATH DE number 3976378 (Why is no real title available?)
• scientific article; zbMATH DE number 3982544 (Why is no real title available?)
• scientific article; zbMATH DE number 3983141 (Why is no real title available?)
• scientific article; zbMATH DE number 4035187 (Why is no real title available?)
• scientific article; zbMATH DE number 49206 (Why is no real title available?)
• scientific article; zbMATH DE number 475418 (Why is no real title available?)
• scientific article; zbMATH DE number 475420 (Why is no real title available?)
• scientific article; zbMATH DE number 4119651 (Why is no real title available?)
• scientific article; zbMATH DE number 2086519 (Why is no real title available?)
• Profinite Methods in Automata Theory
• Finite automata in the mathematical theory of programming
• Automata theory and its applications
• Automata and logics over finitely varying functions
• A unified approach for showing language inclusion and equivalence between various types of -automata
• Infinitary tree languages recognized by \(\omega\)-automata

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)