Automata on infinite objects and their applications to logic and programming

DOI10.1016/0890-5401(89)90046-1zbMATH Open0691.68068OpenAlexW2088892929MaRDI QIDQ582913FDOQ582913

Ahmed Saoudi, M. 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) Artificial intelligence (68T99) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• First-order dynamic logic
• Alternation
• Fundamental properties of infinite trees
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Testing and generating infinite sequences by a finite automaton
• Deciding full branching time logic
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Algorithm = logic + control
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pushdown tree automata
• Title not available (Why is that?)
• A note on \(\omega\)-regular languages
• 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
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Formal computations of non deterministic recursive program schemes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The minimalization of tree automata
• Infinitary tree languages recognized by \(\omega\)-automata

Cited In (17)

• Title not available (Why is that?)
• A unified approach for showing language inclusion and equivalence between various types of \(\omega\)-automata
• Infinite trees and automaton-definable relations over \(\omega\)-words
• Title not available (Why is that?)
• Title not available (Why is that?)
• Profinite Methods in Automata Theory
• Title not available (Why is that?)
• Automata theory and its applications
• Title not available (Why is that?)
• Weak Muller acceptance conditions for tree automata
• Parallel generation of infinite images
• On automata on infinite trees
• A branching time logic with past operators
• Generalized automata on infinite trees and Muller-McNaughton's theorem
• Automata and logics over finitely varying functions
• Title not available (Why is that?)
• Title not available (Why is that?)

   Recommendations

• Title not available (Why is that?) 👍 👎
• Topological characterizations of infinite tree languages 👍 👎
• Title not available (Why is that?) 👍 👎
• On automata on infinite trees 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Uniform inevitability is tree automaton ineffable 👍 👎
• PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS 👍 👎

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)