MSO on the Infinite Binary Tree: Choice and Order

DOI10.1007/978-3-540-74915-8_15MaRDI QIDQ3608411zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Christof Löding

Publication date 5 March 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00620169/file/csl07.pdf

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Applications of game theory (91A80)

Recommendations

• Choice functions and well-orderings over the infinite binary tree
• scientific article; zbMATH DE number 1418347
• Monadic second-order logic on tree-like structures
• A complete axiomatization of MSO on infinite trees
• Monadic second order definable relations on the binary tree

Cited in

(22)

• Tree-automatic scattered linear orders
• Delay games with WMSO+U winning conditions
• Delay games with WMSO+U winning conditions
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• On the Borel complexity of MSO definable sets of branches
• On monadic theories of monadic predicates
• A complete axiomatization of MSO on infinite trees
• scientific article; zbMATH DE number 1418347 (Why is no real title available?)
• Unambiguous languages exhaust the index hierarchy
• scientific article; zbMATH DE number 7559440 (Why is no real title available?)
• scientific article; zbMATH DE number 7559451 (Why is no real title available?)
• scientific article; zbMATH DE number 7561705 (Why is no real title available?)
• A functional (monadic) second-order theory of infinite trees
• Ambiguity hierarchy of regular infinite tree languages
• On the decidability of MSO+U on infinite trees
• Monoidal-closed categories of tree automata
• Unambiguity in automata theory
• How much lookahead is needed to win infinite games?
• How Much Lookahead is Needed to Win Infinite Games?
• Choice functions and well-orderings over the infinite binary tree
• Uniformisation of regular relations in first-order logic with two variables
• Second-order finite automata: expressive power and simple proofs using automatic structures

This page was built for publication: MSO on the Infinite Binary Tree: Choice and Order

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