ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
From MaRDI portal
Publication:4902892
DOI10.1142/S0129054112400448zbMath1282.68186MaRDI QIDQ4902892
Émilie Charlier, Narad Rampersad, Jeffrey O. Shallit
Publication date: 18 January 2013
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054112400448
automata; enumeration; recurrence; decidability; subword complexity; unbordered word; \(k\)-automatic sequence; appearance function; \(k\)-regular sequence
Related Items
When is an automatic set an additive basis?, First-Order Logic and Numeration Systems, Unnamed Item, The simplest binary word with only three squares, Automatic sequences of rank two, Unnamed Item, Automaticity and Invariant Measures of Linear Cellular Automata, From Combinatorial Games to Shape-Symmetric Morphisms, ON THE NUMBER OF ABELIAN BORDERED WORDS (WITH AN EXAMPLE OF AUTOMATIC THEOREM-PROVING), Prefix palindromic length of the Thue-Morse word, Bracket words: A generalisation of Sturmian words arising from generalised polynomials, Automaticity and Parikh-Collinear Morphisms, Note on a Fibonacci parity sequence, An Inequality for the Number of Periods in a Word, Topological conjugacy of constant length substitution dynamical systems, On the regularity of the Hankel determinant sequence of the characteristic sequence of powers of 2, On the permutation complexity of the Cantor-like sequences, Morphisms on infinite alphabets, countable states automata and regular sequences, Additive number theory via automata theory, Robustness of Pisot-regular sequences, Minimal automaton for multiplying and translating the Thue-Morse set, Revisiting regular sequences in light of rational base numeration systems, Regular sequences and synchronized sequences in abstract numeration systems, Decidability and \(k\)-regular sequences, How to prove that a sequence is not automatic, Synchronized sequences, Derived sequences and the factor spectrum of the period-doubling sequence, Lie complexity of words, Asymptotic analysis of \(q\)-recursive sequences, On prefix palindromic length of automatic words, A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences, Abelian-square-rich words, Computing abelian complexity of binary uniform morphic words, Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences, Topological invariants for words of linear factor complexity, Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties, Decision algorithms for Fibonacci-automatic Words, I: Basic results, Effective S-adic Symbolic Dynamical Systems, A New Approach to the Paperfolding Sequences, Mechanical Proofs of Properties of the Tribonacci Word, Frobenius Numbers and Automatic Sequences
Cites Work
- Unnamed Item
- On factors of synchronized sequences
- Permutation complexity of the Thue-Morse word
- Lexicographically least words in the orbit closure of the Rudin-Shapiro word
- Handbook of weighted automata
- Every real number greater than 1 is a critical exponent
- The ring of \(k\)-regular sequences
- Separators in infinite words generated by morphisms.
- Bertrand numeration systems and recognizability
- On the factors of automatic words
- The ring of \(k\)-regular sequences. II.
- Palindrome complexity.
- Periodicity, repetitions, and orbits of an automatic sequence
- Stern polynomials
- Palindromic continued fractions
- An Exercise on Fibonacci Representations
- On synchronized sequences and their separators
- On a Theorem of R. Jungen
- Squares and overlaps in the Thue-Morse sequence and some variants
- Least Periods of Factors of Infinite Words
- On the Periodicity of Morphic Words
- ON THE REPETITIVITY INDEX OF INFINITE WORDS
- ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
- A decision method for the recognizability of sets defined by number systems
- Automatic Sequences
- Reconnaissabilité des substitutions et complexité des suites automatiques
- Uniform tag sequences