The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable

DOI10.1016/0304-3975(92)90256-FzbMath0773.03008MaRDI QIDQ1202930

Roger Villemaire

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

first-order theoryBüchi's theoremencoding for \(k\)-automatarecognizability by automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (15)

On iterating linear transformations over recognizable sets of integers ⋮ LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD ⋮ Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems ⋮ Bertrand numeration systems and recognizability ⋮ Automata Presenting Structures: A Survey of the Finite String Case ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ Recognizable sets of power series over finite fields ⋮ EXPANSIONS OF THE ORDERED ADDITIVE GROUP OF REAL NUMBERS BY TWO DISCRETE SUBGROUPS ⋮ Cobham's Theorem seen through Büchi's Theorem ⋮ On the expressiveness of Büchi arithmetic ⋮ Ostrowski numeration systems, addition, and finite automata ⋮ Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Defining Multiplication in Some Additive Expansions of Polynomial Rings ⋮ A generalization of Cobham's theorem to automata over real numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak Second‐Order Arithmetic and Finite Automata
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• A note on undecidable extensions of monadic second order successor arithmetic
• Joining k- and l-recognizable sets of natural numbers
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable