Presburgerness of predicates regular in two number systems
From MaRDI portal
Publication:1259594
DOI10.1007/BF00967164zbMath0411.03054OpenAlexW2008644136MaRDI QIDQ1259594
Publication date: 1977
Published in: Siberian Mathematical Journal (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00967164
finite automatafirst-order arithmeticmonadic predicatedefinability in first-order languagesPresburger predicateregular predicatestwo number system
Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30)
Related Items (25)
Lattice of definability (of reducts) for integers with successor ⋮ On iterating linear transformations over recognizable sets of integers ⋮ THE BASE PROBLEM FOR D0L PARIKH SETS ⋮ On multiplicatively dependent linear numeration systems, and periodic points ⋮ Unnamed Item ⋮ Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems ⋮ On interpretations of Presburger arithmetic in Büchi arithmetics ⋮ Addition machines, automatic functions and open problems of Floyd and Knuth ⋮ Semiautomatic structures ⋮ The lattice of definability: origins, recent developments, and further directions ⋮ Lattice of definability in the order of rational numbers ⋮ Unnamed Item ⋮ First-Order Logic and Numeration Systems ⋮ Counting the solutions of Presburger equations without enumerating them. ⋮ Büchi Automata Recognizing Sets of Reals Definable in First-Order Logic with Addition and Order ⋮ Cobham-Semenov theorem and \(\mathbb N^d\)-subshifts ⋮ Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ A Generalization of Semenov’s Theorem to Automata over Real Numbers ⋮ An extension of the Cobham-Semënov Theorem ⋮ Self-similar tiling systems, topological factors and stretching factors ⋮ A generalization of Cobham's theorem to automata over real numbers ⋮ On recognizable sets of integers ⋮ Recurrence along directions in multidimensional words ⋮ A More Reasonable Proof of Cobham’s Theorem
Cites Work
This page was built for publication: Presburgerness of predicates regular in two number systems
