On Monadic Theories of Monadic Predicates

DOI10.1007/978-3-642-15025-8_30zbMath1287.03029OpenAlexW1510368107MaRDI QIDQ3586024

Wolfgang Thomas

Publication date: 3 September 2010

Published in: Fields of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15025-8_30

zbMATH Keywords

monadic second-order logicdecidable theoriestree automata

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Choice functions and well-orderings over the infinite binary tree
• The monadic theory of order
• The theory of successor with an extra predicate
• The monadic theory of morphic infinite words and generalizations
• Automata, logics, and infinite games. A guide to current research
• Decidability and undecidability of theories with a predicate for the primes
• Rabin's uniformization problem
• MSO on the Infinite Binary Tree: Choice and Order
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• On the bounded monadic theory of well-ordered structures
• Modest theory of short chains. I
• Modest theory of short chains. II
• The Monadic Theory of Tree-like Structures
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: On Monadic Theories of Monadic Predicates