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 treedefinability of n-ary relationsfinite tree automatasecond order theoriestwo successor functions

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1418347
• 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)

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

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)