Joining k- and l-recognizable sets of natural numbers

DOI10.1007/3-540-55210-3_175zbMath1496.03163OpenAlexW1489701161MaRDI QIDQ5096772

Roger Villemaire

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_175

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05)

Related Items

Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable

Cites Work

• 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
• Decision problems for multiple successor arithmetics
• 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
• Concatenation as a basis for arithmetic