Monadic second order definable relations on the binary tree

DOI10.2307/2273878zbMath0628.03005OpenAlexW2061100541MaRDI QIDQ3764124

Hans Läuchli, Christian Savioz

Publication date: 1987

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2273878

zbMATH Keywords

binary treefinite tree automatasecond order theoriesdefinability of n-ary relationstwo successor functions

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40)

Related Items

Generalized rational relations and their logical definability ⋮ Logics for unordered trees with data constraints ⋮ To know or not to know: Epistemic approaches to security protocol verification ⋮ Deciding whether a relation defined in Presburger logic can be defined in weaker logics ⋮ Infinite trees and automaton-definable relations over \(\omega\)-words ⋮ Grid structures and undecidable constraint theories ⋮ Definability and decidability of binary predicates for time granularity ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Rational relations having a rational trace on each finite intersection of rational relations ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

Cites Work

• Unnamed Item
• Unnamed Item
• Logical Complexity of Some Classes of Tree Languages Generated by Multiple‐Tree‐Automata
• On the bounded monadic theory of well-ordered structures