Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem

DOI10.2307/2275643MaRDI QIDQ4382476zbMATHOpenAlexFDO

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

zbMATH Keywords

finite automataarithmeticdecidable and undecidable theories

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

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

Cites work

• A note on undecidable extensions of monadic second order successor arithmetic
• On the base-dependence of sets of numbers recognizable by finite automata
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Presburgerness of predicates regular in two number systems
• STACS 92. Theoretical aspects of computer science. Proceedings of the 9th annual symposium, Cachan, France, February 13--15, 1992
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(13)

• Defining multiplication in some additive expansions of polynomial rings
• Automatic sets of rational numbers
• Some proofs of undecidability of arithmetic
• On the existential arithmetics with addition and bitwise minimum
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• The definable criterion for definability in Presburger arithmetic and its applications.
• A list of arithmetical structures complete with respect to the first-order definability
• scientific article; zbMATH DE number 3851087 (Why is no real title available?)
• 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
• Cobham's theorem for substitutions
• scientific article; zbMATH DE number 3916265 (Why is no real title available?)
• A Uniformly, Extremely Nonextensional Formula of Arithmetic with many Undecidable Fixed Points in many Theories

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)