Infinite trees and automaton-definable relations over \(\omega\)-words
From MaRDI portal
Publication:1199531
DOI10.1016/0304-3975(92)90090-3zbMath0760.68043OpenAlexW1570009926MaRDI QIDQ1199531
Publication date: 16 January 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90090-3
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Generalized rational relations and their logical definability ⋮ Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus ⋮ An initial semantics for the \(\mu\)-calculus on trees and Rabin's complementation lemma ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Model-Checking Strategic Ability and Knowledge of the Past of Communicating Coalitions ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. ⋮ Revisiting Satisfiability and Model-Checking for CTLK with Synchrony and Perfect Recall ⋮ How to decide continuity of rational functions on infinite words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relations rationnelles infinitaires
- Two decidability problems for infinite words
- Uniform inevitability is tree automaton ineffable
- Reasoning about infinite computations
- Automatic verification of finite-state concurrent systems using temporal logic specifications
- Monadic second order definable relations on the binary tree
- Languages that Capture Complexity Classes
- On the bounded monadic theory of well-ordered structures
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Concatenation as a basis for arithmetic
