On decidability of monadic logic of order over the naturals extended by monadic predicates

DOI10.1016/J.IC.2006.12.004MaRDI QIDQ2373700zbMATH OpenOpenAlexFDO

Authors Alexander Rabinovich

Publication date 16 July 2007

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On monadic theories of monadic predicates
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• scientific article; zbMATH DE number 1759414
• The monadic theory of morphic infinite words and generalizations
• scientific article; zbMATH DE number 3880651

Cites work

• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• 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 1759414 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3337664 (Why is no real title available?)
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• 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
• Uniformization and skolem functions in the class of trees

Cited in

(23)

• On Boolean closed full trios and rational Kripke frames
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Decidability of Cancellative Extension of Monoidal T-norm Based Logic
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• On monadic theories of monadic predicates
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• Decidable Extensions of Church’s Problem
• Decidability of Scott's model as an ordered ℚ-vectorspace
• Infinite and bi-infinite words with decidable monadic theories
• Monadic decomposition
• scientific article; zbMATH DE number 7559440 (Why is no real title available?)
• scientific article; zbMATH DE number 7561705 (Why is no real title available?)
• The logical strength of Büchi's decidability theorem
• Choice functions and well-orderings over the infinite binary tree
• Predicative Aspects of Order Theory in Univalent Foundations
• Selection over classes of ordinals expanded by monadic predicates
• The monadic theory of toric words
• The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates
• The Church synthesis problem over continuous time
• On the decidability of monadic second-order logic with arithmetic predicates
• On the expansion of monadic second-order logic with Cantor-Bendixson rank and order type predicates
• On expansions of monadic second-order logic with dynamical predicates
• Regular sets over extended tree structures

This page was built for publication: On decidability of monadic logic of order over the naturals extended by monadic predicates

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