Monadic second order definable relations on the binary tree

DOI10.2307/2273878zbMATH Open0628.03005OpenAlexW2061100541MaRDI QIDQ3764124FDOQ3764124

Authors: Hans Läuchli, Christian Savioz 

Publication date: 1987

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

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

Recommendations

• Publication:4941910
• scientific article; zbMATH DE number 4051591
• A characterization of Büchi tree automata
• scientific article; zbMATH DE number 4208050
• Infinite trees and automaton-definable relations over \(\omega\)-words

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the bounded monadic theory of well-ordered structures
• Logical Complexity of Some Classes of Tree Languages Generated by Multiple‐Tree‐Automata

Cited In (21)

• Logics for unordered trees with data constraints
• Sheaf recursion and a separation theorem
• Existential monadic second order logic on random rooted trees
• Infinite trees and automaton-definable relations over \(\omega\)-words
• Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law
• Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
• Rational relations having a rational trace on each finite intersection of rational relations
• Resynchronized uniformization and definability problems for rational relations
• Monadic representability of certain binary relations
• Grid structures and undecidable constraint theories
• The full binary tree cannot be interpreted in a chain
• Definability and decidability of binary predicates for time granularity
• Title not available (Why is that?)
• To know or not to know: Epistemic approaches to security protocol verification
• Title not available (Why is that?)
• Generalized rational relations and their logical definability
• Deciding whether a relation defined in Presburger logic can be defined in weaker logics
• The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
• MSO on the Infinite Binary Tree: Choice and Order
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Monadic second order definable relations on the binary tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3764124)