Automata calculating the complexity of automatic sequences
type: Item
instance of: scholarly article
title: Automata calculating the complexity of automatic sequences
zbMATH Open document ID: 0815.11015
author: Théodore Tapsoba
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 1995-07-09T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/225850
full work available at URL: jtnb6-1.html
review text: The complexity of a sequence on a finite alphabet is the function \(n \to \rho (n)\), where \(\rho (n)\) is the number of factors (blocks) of length \(n\) of the sequence. In the case where the sequence is a fixed point of a uniform injective substitution and where the sequence takes only two values, the author shows that if the sequence is minimal, then \(n \to \rho (n+1) - \rho (n)\) is generated by an automaton which is explicitly constructed. Note that, as indicated by the author, B. Mossé has obtained more general results (Preprint, LMD). The paper ends with an example, the Thue-Morse sequence, for which the result of the author implies the previously known result of complexity [see \textit{A. de Luca} and \textit{S. Varricchio}, Theor. Comput. Sci. 63, 333-348 (1989; Zbl 0671.10050) and \textit{S. Brlek}, Discrete Appl. Math. 24, 83-96 (1989; Zbl 0683.20045)].
Mathematics Subject Classification ID: 11B85
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 703940
zbMATH Keywords: automatic sequences
zbMATH Keywords: complexity
zbMATH Keywords: Thue-Morse sequence
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
OpenAlex ID: W2314536985
cites work: Q3700861
cites work: Enumeration of factors in the Thue-Morse word
cites work: Suites algébriques, automates et substitutions
cites work: Uniform tag sequences
cites work: Q3228119
cites work: Q3659988
cites work: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
cites work: Q3348040
DOI: 10.5802/JTNB.109
description: scientific article; zbMATH DE number 703940