On monadic theories of monadic predicates

DOI10.1007/978-3-642-15025-8_30MaRDI QIDQ3586024zbMATH OpenOpenAlexFDO

Authors 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

decidable theoriesmonadic second-order logictree automata

Mathematics Subject Classification ID

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

Recommendations

• On decidability of monadic logic of order over the naturals extended by monadic predicates
• scientific article; zbMATH DE number 1418347
• scientific article; zbMATH DE number 3880651
• The Monadic Theory of Tree-like Structures
• The monadic theory of morphic infinite words and generalizations

Cites work

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

Cited in

(20)

• Monadic \(\Pi _ 1^ 1\)-theories of \(\Pi _ 1^ 1\)-properties
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• Undecidable first-order theories of affine geometries
• On countable chains having decidable monadic theory
• Truthful Monadic Abstractions
• scientific article; zbMATH DE number 4016858 (Why is no real title available?)
• scientific article; zbMATH DE number 5976699 (Why is no real title available?)
• Model Transformations in Decidability Proofs for Monadic Theories
• Synthesizing Monadic Predicates
• On Monadic Second-Order Theories of Multidominance Structures
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• A MONADIC APPROACH TO THE MODAL THEORY
• scientific article; zbMATH DE number 175645 (Why is no real title available?)
• scientific article; zbMATH DE number 522862 (Why is no real title available?)
• scientific article; zbMATH DE number 1735985 (Why is no real title available?)
• scientific article; zbMATH DE number 1759414 (Why is no real title available?)
• scientific article; zbMATH DE number 1418347 (Why is no real title available?)
• Monotone recursive definition of predicates and its realizability interpretation
• Monadic translation of classical sequent calculus
• More on monadic logic. C: Monadically interpreting in stable unsuperstable \(\mathcal T\) and the monadic theory of \(^{\omega}\lambda\)

This page was built for publication: On monadic theories of monadic predicates

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