The definable criterion for definability in Presburger arithmetic and its applications.
From MaRDI portal
Publication:1401169
DOI10.1016/S0304-3975(02)00047-6zbMath1052.68079OpenAlexW1998927893WikidataQ56059273 ScholiaQ56059273MaRDI QIDQ1401169
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00047-6
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30)
Related Items
Decidability of Definability Issues in the Theory of Real Addition, Structural Presburger digit vector automata, Unnamed Item, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems, The lattice of definability: origins, recent developments, and further directions, Lattice of definability in the order of rational numbers, Unnamed Item, Unnamed Item, Büchi Automata Recognizing Sets of Reals Definable in First-Order Logic with Addition and Order, Minimal automaton for multiplying and translating the Thue-Morse set, Semi-synchronous transductions, Defining Multiplication in Some Additive Expansions of Polynomial Rings, A DECISION PROBLEM FOR ULTIMATELY PERIODIC SETS IN NONSTANDARD NUMERATION SYSTEMS, Recurrence along directions in multidimensional words, A multidimensional critical factorization theorem
Cites Work
- Unnamed Item
- Logic and \(p\)-recognizable sets of integers
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
- Weak Second‐Order Arithmetic and Finite Automata
- Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
- Cobham's Theorem seen through Büchi's Theorem
- Some results in the effective descriptive set theory
- On the base-dependence of sets of numbers recognizable by finite automata
