The Church problem for expansions of (N,<) by unary predicates

DOI10.1016/J.IC.2012.06.001MaRDI QIDQ690498zbMATH OpenOpenAlexFDO

Authors 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

Church's synthesis problemcomposition mehodgame-theoretical techniquesmonadic logic of orderparametrized 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)

Review text

For a two-variable formula \(B(X,Y)\) of the monadic logic of order (MLO), Church's synthesis problem concerns the existence and construction of a finite-state operator \(Y=F(X)\) such that \(B(X,F(X))\) is universally valid over \((\mathbb N,<)\). In this version of the problem, \(B\) and \(F\) contain as a parameter a unary predicate \(P\). A large class of predicates \(P\) is exhibited such that Church's problem with parameter \(P\) is decidable. Those \(P\) are increasing recursive \(\omega\)-sequences of integers which are effectively sparse and effectively ultimately reducible (the latter notions, which are defined in the paper, are very natural).

Recommendations

• Decidable Extensions of Church’s Problem
• The Church Synthesis Problem with Parameters
• Church Synthesis Problem with Parameters
• The Church synthesis problem with metric
• Logical Refinements of Church’s Problem

Cites work

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

Cited in

(5)

• Church Synthesis Problem with Parameters
• The Church Problem for Countable Ordinals
• Decidable Extensions of Church’s Problem
• Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey
• The Church Synthesis Problem with Parameters

This page was built for publication: The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates

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