Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
From MaRDI portal
Publication:5520636
DOI10.2307/2269808zbMath0144.24501OpenAlexW2131663704MaRDI QIDQ5520636
Michael O. Rabin, Calvin C. Elgot
Publication date: 1966
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2269808
Related Items (47)
Lattice of definability (of reducts) for integers with successor ⋮ Construction of decidable singular theories of two successor functions with an extra predicate ⋮ On Boolean closed full trios and rational Kripke frames ⋮ The theory of ends, pushdown automata, and second-order logic ⋮ On decidability of monadic logic of order over the naturals extended by monadic predicates ⋮ Nonmaximal decidable structures ⋮ Computational complexity of logical theories of one successor and another unary function ⋮ Undecidability of the first-order arithmetic \(A[P(x),2x,x+1\)] ⋮ Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus ⋮ Joining k- and l-recognizable sets of natural numbers ⋮ The lattice of definability: origins, recent developments, and further directions ⋮ Recognizable sets of power series over finite fields ⋮ Expansions of the p‐adic numbers that interpret the ring of integers ⋮ Weakly maximal decidable structures ⋮ In memoriam Calvin C. Elgot ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Model Transformations in Decidability Proofs for Monadic Theories ⋮ Inferring answers to queries ⋮ A note on undecidable extensions of monadic second order successor arithmetic ⋮ Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts ⋮ Minimal undecidable identity problem for finite-automaton mappings ⋮ Infinite trees and automaton-definable relations over \(\omega\)-words ⋮ The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable ⋮ The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates ⋮ On Monadic Theories of Monadic Predicates ⋮ Logical aspects of Cayley-graphs: the group case ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Definability and decidability of binary predicates for time granularity ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages ⋮ The theory of successor with an extra predicate ⋮ Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes ⋮ A tetrachotomy for expansions of the real ordered additive group ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ Unnamed Item ⋮ Defining Multiplication in Some Additive Expansions of Polynomial Rings ⋮ Revisiting Satisfiability and Model-Checking for CTLK with Synchrony and Perfect Recall ⋮ Decidable Extensions of Church’s Problem ⋮ CARDINAL ARITHMETIC IN THE STYLE OF BARON VON MÜNCHHAUSEN ⋮ Systolic tree \(\omega\)-languages: The operational and the logical view ⋮ Calvin C. Elgot (1922-1980) ⋮ Automata techniques for query inference machines ⋮ 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05 ⋮ The monadic theory of morphic infinite words and generalizations ⋮ Monadic second-order logic on tree-like structures ⋮ Learning via finitely many queries ⋮ Shelah-Stupp's and Muchnik's iterations revisited
Cites Work
This page was built for publication: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
