ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES

DOI10.1142/S0129054112400448zbMath1282.68186OpenAlexW2570053645MaRDI 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

zbMATH Keywords

automataenumerationrecurrencedecidabilitysubword complexityunbordered word\(k\)-automatic sequenceappearance function\(k\)-regular sequence

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85)

Related Items (41)

Abelian-square-rich words ⋮ How to prove that a sequence is not automatic ⋮ Prefix palindromic length of the Thue-Morse word ⋮ Automatic sequences of rank two ⋮ Mechanical Proofs of Properties of the Tribonacci Word ⋮ Computing abelian complexity of binary uniform morphic words ⋮ Synchronized sequences ⋮ Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences ⋮ Decision algorithms for Fibonacci-automatic Words, I: Basic results ⋮ Effective S-adic Symbolic Dynamical Systems ⋮ Derived sequences and the factor spectrum of the period-doubling sequence ⋮ A New Approach to the Paperfolding Sequences ⋮ Lie complexity of words ⋮ Asymptotic analysis of \(q\)-recursive sequences ⋮ Unnamed Item ⋮ Morphisms on infinite alphabets, countable states automata and regular sequences ⋮ When is an automatic set an additive basis? ⋮ Topological invariants for words of linear factor complexity ⋮ Bracket words: A generalisation of Sturmian words arising from generalised polynomials ⋮ Frobenius Numbers and Automatic Sequences ⋮ Automaticity and Parikh-Collinear Morphisms ⋮ Note on a Fibonacci parity sequence ⋮ An Inequality for the Number of Periods in a Word ⋮ On the permutation complexity of the Cantor-like sequences ⋮ Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties ⋮ First-Order Logic and Numeration Systems ⋮ Unnamed Item ⋮ Automaticity and Invariant Measures of Linear Cellular Automata ⋮ From Combinatorial Games to Shape-Symmetric Morphisms ⋮ On the regularity of the Hankel determinant sequence of the characteristic sequence of powers of 2 ⋮ On prefix palindromic length of automatic words ⋮ Topological conjugacy of constant length substitution dynamical systems ⋮ Additive number theory via automata theory ⋮ A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences ⋮ 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 ⋮ ON THE NUMBER OF ABELIAN BORDERED WORDS (WITH AN EXAMPLE OF AUTOMATIC THEOREM-PROVING) ⋮ The simplest binary word with only three squares

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

This page was built for publication: ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES