Drunken man infinite words complexity

DOI10.1051/ITA:2008012MaRDI QIDQ3526419zbMATH OpenOpenAlexFDO

Authors Marion Le Gonidec

Publication date 25 September 2008

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92890, https://semanticscholar.org/paper/1daeb63928e55e50430133f9bda40af545e8cbab

zbMATH Keywords

block-complexityinfinite words generated by countable automatamorphisms on countable alphabets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15) Automata sequences (11B85)

Recommendations

• On the complexity of infinite words generated by countable \(q\)-automata
• scientific article; zbMATH DE number 2150291
• On complexity functions of infinite words associated with generalized Dyck languages
• On the minimal complexity of infinite words
• Complexity of infinite sequences with zero entropy

Cites work

• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• scientific article; zbMATH DE number 5051582 (Why is no real title available?)
• Arithmetics properties of substitutions and infinite automata
• Automatic Sequences
• Complexity and special factors
• Complexity of sequences and dynamical systems
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Integers with an average sum of digits
• On the arithmetic structure of sets characterized by sum of digits properties
• On the complexity of infinite sequences
• On the complexity of infinite words generated by countable \(q\)-automata
• Substitution dynamical systems on infinite alphabets
• The Kolmogorov complexity of infinite words
• Uniform tag sequences

Cited in

(7)

• On the complexity of infinite words generated by countable \(q\)-automata
• Behavior of various complexity functions
• On complexity functions of infinite words associated with generalized Dyck languages
• On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited
• Properties and limits of recognition of sets of integers by countable automata
• On the complexity of a family of \(k\)-context-free sequences
• Morphisms on infinite alphabets, countable states automata and regular sequences

This page was built for publication: Drunken man infinite words complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526419)