Ostrowski-automatic sequences: theory and applications
From MaRDI portal
Publication:2222098
DOI10.1016/j.tcs.2021.01.018zbMath1467.68146OpenAlexW3120172643MaRDI QIDQ2222098
Aseem Baranwal, Luke Schaeffer, Jeffrey O. Shallit
Publication date: 3 February 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.018
repetitionautomatic sequencedecision procedurebalanced wordLucas wordOstrowski numerationpalindrome-rich word
Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)
Related Items
On extended boundary sequences of morphic and Sturmian words, Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents, Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture, Sumsets associated with Beatty sequences
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- Extensions of rich words
- Last cases of Dejean's conjecture
- Palindromic complexity of codings of rotations
- Palindromic rich words and run-length encodings
- Rich, Sturmian, and trapezoidal words
- Palindromic richness
- Learning regular sets from queries and counterexamples
- Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
- Sequences with subword complexity \(2n\)
- Logic and \(p\)-recognizable sets of integers
- Well-balanced sequences
- Additive number theory via approximation by regular languages
- EERTREE: an efficient data structure for processing palindromes in strings
- Ostrowski numeration systems, addition, and finite automata
- Balanced words
- A new characteristic property of rich words
- Critical exponent of infinite balanced words via the Pell number system
- Repetitions in infinite palindrome-rich words
- New results on pseudosquare avoidance
- Some further results on squarefree arithmetic progressions in infinite words
- Rich square-free words
- The number of valid factorizations of Fibonacci prefixes
- Critical exponents of infinite balanced words
- Sur un théorème de Thue
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- The Critical Exponent is Computable for Automatic Sequences
- Constructions of words rich in palindromes and pseudopalindromes
- Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- A proof of Dejean’s conjecture
- Decision algorithms for Fibonacci-automatic Words, I: Basic results
- Complementary symmetric Rote sequences: the critical exponent and the recurrence function
- Mechanical Proofs of Properties of the Tribonacci Word
- Fast and Practical Algorithms for Computing All the Runs in a String
- On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
- Automatic Sequences
- Decidability and Enumeration for Automatic Sequences: A Survey
- Recognizable sets of numbers in nonstandard bases
- The repetition threshold for binary rich words
- Circular critical exponents for Thue–Morse factors
- On the base-dependence of sets of numbers recognizable by finite automata
- Uniform tag sequences
