Logic and $p$-recognizable sets of integers

Christian Michaux, Georges Hansel, Véronique Bruyère, Roger Villemaire

Publication date: 22 January 1995

Published in: Bulletin of the Belgian Mathematical Society - Simon Stevin (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/232407

zbMATH Keywords

survey finite automata first-order definability infinite words formal power series Cobham-Semenov theorem $p$-recognizable sequences

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Automata sequences (11B85)

Related Items

Decidability of Definability Issues in the Theory of Real Addition, Asymptotic properties of free monoid morphisms, Decidability questions related to abstract numeration systems, Automatic sequences of rank two, On iterating linear transformations over recognizable sets of integers, Dynamical directions in numeration, Mechanical Proofs of Properties of the Tribonacci Word, Synchronized sequences, Structural Presburger digit vector automata, Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences, Multi-dimensional sets recognizable in all abstract numeration systems, On the Recognizability of Self-generating Sets, Automatic Theorem-Proving in Combinatorics on Words, Decision algorithms for Fibonacci-automatic Words, I: Basic results, Effective S-adic Symbolic Dynamical Systems, CONTRIBUTIONS TO THE THEORY OF F-AUTOMATIC SETS, Deciding Boolean algebra with Presburger arithmetic, Ultimate periodicity problem for linear numeration systems, Automata and tame expansions of $(\mathbb{Z}, +)$, Unnamed Item, On Pascal triangles modulo a prime power, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems, When is an automatic set an additive basis?, Recognizable sets of numbers in nonstandard bases, Automatic winning shifts, Properties of a class of Toeplitz words, Automaticity of double sequences generated by one-dimensional linear cellular automata, Bertrand numeration systems and recognizability, On the factors of automatic words, Regular model checking revisited, On the existential arithmetics with addition and bitwise minimum, On interpretations of Presburger arithmetic in Büchi arithmetics, On extended boundary sequences of morphic and Sturmian words, Proving results about OEIS sequences with \texttt{Walnut}, The definable criterion for definability in Presburger arithmetic and its applications., On images of D0L and DT0L power series., Decidable problems in substitution shifts, Spectra and satisfiability for logics with successor and a unary function, Automaticity and Parikh-Collinear Morphisms, Knapsack and the power word problem in solvable Baumslag–Solitar groups, Automata methods in transcendence, Transduction of automatic sequences and applications, A General Approach to Proving Properties of Fibonacci Representations via Automata Theory, On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases, On digital sequences associated with Pascal's triangle, A Hierarchy of Automaticω-Words having a Decidable MSO Theory, First-Order Logic and Numeration Systems, Unnamed Item, Regular languages of nested words: fixed points, automata, and synchronization, 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, Ostrowski-automatic sequences: theory and applications, From Combinatorial Games to Shape-Symmetric Morphisms, On the expressiveness of Büchi arithmetic, On the regularity of the Hankel determinant sequence of the characteristic sequence of powers of 2, On the boundary sequence of an automatic sequence, $\mathbb \{Q\}$ muni de l’arithmétique faible de Penzin est décidable, Additive number theory via automata theory, Syntactical and automatic properties of sets of polynomials over finite fields, Deciding game invariance, Ostrowski numeration systems, addition, and finite automata, Cobham-Semenov theorem and $\mathbb N^d$-subshifts, Permutive one-way cellular automata and the finiteness problem for automaton groups, Multitree automata that count, It is decidable whether the image of an $\mathbb N$-rational sequence has a base, Formal language properties of hybrid systems with strong resets, A Generalization of Semenov’s Theorem to Automata over Real Numbers, Unnamed Item, A Characterization of Multidimensional <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>S</mml:mi></mml:math>-Automatic Sequences, Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series, Minimal automaton for multiplying and translating the Thue-Morse set, Partial Projection of Sets Represented by Finite Automata, with Application to State-Space Visualization, Self-similar tiling systems, topological factors and stretching factors, Semi-synchronous transductions, A generalization of Cobham's theorem to automata over real numbers, Morphisms and almost-periodicity, On number systems with finite degree of ambiguity, On recognizable sets of integers, Independent numeration systems and syndeticity, Substitutive systems and a finitary version of Cobham's theorem, Regular sequences and synchronized sequences in abstract numeration systems, More on morphisms and almost-periodicity, The convex hull of a regular set of integer vectors is polyhedral and effectively computable, Unnamed Item, A More Reasonable Proof of Cobham’s Theorem, A multidimensional critical factorization theorem, An analogue of Cobham's theorem for graph directed iterated function systems, Say no to case analysis: automating the drudgery of case-based proofs

Logic and \(p\)-recognizable sets of integers