Choice functions and well-orderings over the infinite binary tree

DOI10.2478/s11533-010-0046-zzbMath1215.03054OpenAlexW2030037063MaRDI QIDQ607442

Igor Walukiewicz, Christof Löding, Damian Niwinski, Arnaud Carayol

Publication date: 22 November 2010

Published in: Central European Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2478/s11533-010-0046-z

zbMATH Keywords

monadic second-order logicchoice functiondefinability

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items

Solving Infinite Games in the Baire Space, Unnamed Item, On Monadic Theories of Monadic Predicates, Unnamed Item, On the Strength of Unambiguous Tree Automata, On degrees of ambiguity for Büchi tree automata, Unambiguous Büchi Is Weak, Monoidal-closed categories of tree automata, Automata on infinite trees, Unambiguity in Automata Theory, Unnamed Item, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rational \(\omega\)-languages are non-ambiguous
• Systolic tree \(\omega\)-languages: The operational and the logical view
• Automata, logics, and infinite games. A guide to current research
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• Uniformization, choice functions and well orders in the class of trees
• Rabin's uniformization problem
• Deciding Equivalence of Finite Tree Automata
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• The Descriptive Complexity of Parity Games
• MSO on the Infinite Binary Tree: Choice and Order
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• The recursive sets in certain monadic second order fragments of arithmetic
• Uniformization and skolem functions in the class of trees
• On the synthesis of strategies in infinite games
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Church’s Problem and a Tour through Automata Theory
• Solving Sequential Conditions by Finite-State Strategies
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees