Monadic second order definable relations on the binary tree

DOI10.2307/2273878MaRDI QIDQ3764124zbMATH OpenOpenAlexFDO

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

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)

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 -words

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• Logical Complexity of Some Classes of Tree Languages Generated by Multiple‐Tree‐Automata
• On the bounded monadic theory of well-ordered structures

Cited in

(21)

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

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)