Automata calculating the complexity of automatic sequences

DOI10.5802/JTNB.109MaRDI QIDQ1340682zbMATH OpenOpenAlexFDO

Authors Théodore Tapsoba

Publication date 9 July 1995

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=JTNB_1994__6_1_127_0, https://eudml.org/doc/225850, http://www.emis.de/journals/JTNB/1994-1/jtnb6-1.html

zbMATH Keywords

complexityautomatic sequencesThue-Morse sequence

Mathematics Subject Classification ID

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

Recommendations

• Reconnaissabilité des substitutions et complexité des suites automatiques
• Complexity and special factors
• Complexity of automatic sequences
• Complexity of generalized Rudin-Shapiro sequences
• On the joint subword complexity of automatic sequences

Cites work

• scientific article; zbMATH DE number 3114014 (Why is no real title available?)
• scientific article; zbMATH DE number 4198078 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3926275 (Why is no real title available?)
• Automata calculating the complexity of automatic sequences
• Enumeration of factors in the Thue-Morse word
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• Suites algébriques, automates et substitutions
• Uniform tag sequences

Cited in

(27)

• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• Behavior of various complexity functions
• Complexity of generalized Rudin-Shapiro sequences
• The ring of \(k\)-regular sequences
• Entropy analysis of substitutive sequences revisited
• Shift registers fool finite automata
• Special factors of automatic sequences
• On the permutation complexity of the Cantor-like sequences
• Représentation géométrique de suites de complexité $2n+1$
• Subword complexity and \(k\)-synchronization
• On the computational complexity of the Arnold complexity of binary words
• On the context-freeness of the set of words containing overlaps
• Complexity and special factors
• On the D0L Repetition Threshold
• Subword complexity of uniform D0L words over finite groups
• Asymptotic subword complexity of fixed points of group substitutions
• Automatic complexity of shift register sequences
• Computing the prefix of an automaton
• Automata calculating the complexity of automatic sequences
• Complexity of automatic sequences
• Calculation of the complexities of substitutive sequences over a binary alphabet
• Calculating with Automata
• Complexity of automatic sequences
• The subword complexity of fixed points of binary uniform morphisms
• Separators in infinite words generated by morphisms.
• On the subword complexity of Thue-Morse polynomial extractions
• Minimum complexity of automatic non sturmian sequences

This page was built for publication: Automata calculating the complexity of automatic sequences

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