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

DOI10.2307/2275643zbMath0896.03011OpenAlexW2058960916MaRDI QIDQ4382476

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

arithmeticfinite automatadecidable 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)

Related Items (7)

Automatic Sets of Rational Numbers ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ The definable criterion for definability in Presburger arithmetic and its applications. ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Cobham's theorem for substitutions ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Defining Multiplication in Some Additive Expansions of Polynomial Rings

Cites Work

• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• 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
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Weak Second‐Order Arithmetic and Finite Automata
• A note on undecidable extensions of monadic second order successor arithmetic
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem