Monadic second order definable relations on the binary tree
From MaRDI portal
Publication:3764124
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
binary treefinite tree automatasecond order theoriesdefinability of n-ary relationstwo successor functions
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
