Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
type: Item
instance of: scholarly article
title: Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
zbMATH Open document ID: 0857.03003
DOI: 10.1016/0168-0072(95)00022-4
author: Christian Michaux
author: Roger Villemaire
published in: Annals of Pure and Applied Logic
publication date: 1997-03-11T00:00:00Z
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 908463
zbMATH Keywords: Presburger arithmetic
zbMATH Keywords: Cobham's theorem
zbMATH Keywords: Semenov's theorem
zbMATH Keywords: definability
zbMATH Keywords: recognizability by automata
Wikidata QID: Q56059272
MaRDI profile type: Publication
full work available at URL: 0168-0072(95)00022-4
OpenAlex ID: W2092583023
cites work: Q3673137
cites work: Logic and \(p\)-recognizable sets of integers
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: On the base-dependence of sets of numbers recognizable by finite automata
cites work: Q4079524
cites work: Q4052071
cites work: Q5772619
cites work: Q3312199
cites work: Q4722056
cites work: Q3837737
cites work: The definable criterion for definability in Presburger arithmetic and its applications.
cites work: Q4103466
cites work: Q3764203
cites work: Presburgerness of predicates regular in two number systems
cites work: ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
cites work: The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
cites work: Joining k- and l-recognizable sets of natural numbers
DBLP publication ID: journals/apal/MichauxV96
Recommended article: A generalization of Cobham's theorem to automata over real numbers
Recommended article: A Generalization of Cobham’s Theorem to Automata over Real Numbers
Recommended article: A Generalization of Semenov’s Theorem to Automata over Real Numbers
Recommended article: Properties and limits of recognition of sets of integers by countable automata
Recommended article: Q4508546
Recommended article: On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers
Recommended article: Diophantine equations, Presburger arithmetic and finite automata
Recommended article: Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
Recommended article: Decidability of the theory of the natural integers with the Cantor pairing function and the successor
Recommended article: Approaching arithmetic theories with finite-state automata
description: scientific article; zbMATH DE number 908463