On the complexity of infinite words generated by countable \(q\)-automata

DOI10.5802/aif.2246zbMath1121.68090OpenAlexW2501407169MaRDI QIDQ2372782

Marion Le Gonidec

Publication date: 1 August 2007

Published in: Annales de l'Institut Fourier (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=AIF_2006__56_7_2463_0

zbMATH Keywords

complexityautomatasubstitutionsinfinite words

Mathematics Subject Classification ID

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

Related Items

Substitution dynamical systems on infinite alphabets ⋮ Arithmetics properties of substitutions and infinite automata ⋮ Morphisms on infinite alphabets, countable states automata and regular sequences ⋮ Properties and limits of recognition of sets of integers by countable automata ⋮ Drunken man infinite words complexity ⋮ On complexity functions of infinite words associated with generalized Dyck languages ⋮ On the complexity of a family of \(k\)-context-free sequences ⋮ Avoiding squares and overlaps over the natural numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Substitutions in dynamics, arithmetics and combinatorics
• Substitution dynamical systems - spectral analysis
• Subword complexities of various classes of deterministic developmental languages without interactions
• On the complexity of infinite sequences
• Enumeration of factors in the Thue-Morse word
• Substitution dynamical systems on infinite alphabets
• Arithmetics properties of substitutions and infinite automata
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• On the arithmetic structure of the integers whose sum of digits is fixed
• Automatic Sequences
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Uniform tag sequences