Joining k- and l-recognizable sets of natural numbers

DOI10.1007/3-540-55210-3_175MaRDI QIDQ5096772zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• scientific article; zbMATH DE number 3993564
• scientific article; zbMATH DE number 39360
• Cobham's Theorem seen through Büchi's Theorem

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• A note on undecidable extensions of monadic second order successor arithmetic
• Concatenation as a basis for arithmetic
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decision problems for multiple successor arithmetics
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• On the base-dependence of sets of numbers recognizable by finite automata
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(4)

• scientific article; zbMATH DE number 3993564 (Why is no real title available?)
• 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
• On the existential arithmetics with addition and bitwise minimum

This page was built for publication: Joining \(k\)- and \(l\)-recognizable sets of natural numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096772)