Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
From MaRDI portal
Publication:4382476
DOI10.2307/2275643zbMATH Open0896.03011OpenAlexW2058960916MaRDI QIDQ4382476FDOQ4382476
Authors: Alexis Bès 
Publication date: 21 September 1998
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275643
Recommendations
- scientific article; zbMATH DE number 952488
- Undecidable extensions of Skolem arithmetic
- scientific article; zbMATH DE number 1160644
- Undecidability of Brouwerian semilattices
- Some proofs of undecidability of arithmetic
- scientific article; zbMATH DE number 4031660
- Degrees of insolubility of extensions of arithmetic by true propositions
- scientific article; zbMATH DE number 3916265
- A Uniformly, Extremely Nonextensional Formula of Arithmetic with many Undecidable Fixed Points in many Theories
- scientific article; zbMATH DE number 4061229
Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)
Cites Work
- On the base-dependence of sets of numbers recognizable by finite automata
- Weak Second‐Order Arithmetic and Finite Automata
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
- The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
- Presburgerness of predicates regular in two number systems
- A note on undecidable extensions of monadic second order successor arithmetic
- STACS 92. Theoretical aspects of computer science. Proceedings of the 9th annual symposium, Cachan, France, February 13--15, 1992
Cited In (13)
- Some proofs of undecidability of arithmetic
- A Hierarchy of Automaticω-Words having a Decidable MSO Theory
- Automatic sets of rational numbers
- Cobham's theorem for substitutions
- A Uniformly, Extremely Nonextensional Formula of Arithmetic with many Undecidable Fixed Points in many Theories
- Defining multiplication in some additive expansions of polynomial rings
- Undecidability of the word problem for Yamamura's HNN-extension under nice conditions.
- The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
- Title not available (Why is that?)
- On the existential arithmetics with addition and bitwise minimum
- Title not available (Why is that?)
- The definable criterion for definability in Presburger arithmetic and its applications.
- A list of arithmetical structures complete with respect to the first-order definability
This page was built for publication: Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382476)
