The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates

DOI10.1016/j.ic.2012.06.001zbMath1285.03005OpenAlexW2033265717MaRDI QIDQ690498

Alexander Rabinovich

Publication date: 27 November 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.06.001

zbMATH Keywords

monadic logic of orderChurch's synthesis problemcomposition mehodgame-theoretical techniquesparametrized versions of Church's synthesis problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Second- and higher-order model theory (03C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monadic theory of order
• Pushdown processes: Games and model-checking
• The monadic theory of morphic infinite words and generalizations
• Automata, logics, and infinite games. A guide to current research
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• The first order properties of products of algebraic systems
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• Decidable Extensions of Church’s Problem
• Restricted Set-Theoretical Definitions in Arithmetic
• The recursive sets in certain monadic second order fragments of arithmetic
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Solving Sequential Conditions by Finite-State Strategies
• Finite automata and the logic of one-place predicates