×

zbMATH — the first resource for mathematics

On critical exponents in fixed points of non-erasing morphisms. (English) Zbl 1227.68074
Ibarra, Oscar H. (ed.) et al., Developments in language theory. 10th international conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006. Proceedings. Berlin: Springer (ISBN 3-540-35428-X/pbk). Lecture Notes in Computer Science 4036, 280-291 (2006).
Let \(\Sigma \) be an alphabet of size \(t\), let \(f\): \Sigma ^{*}\rightarrow \Sigma ^{*}\( be a non-erasing morphism, let \)w\( be an infinite fixed point of \)f\(, and let \)E(w)\( be the critical exponent of \)w\(. We prove that if \)E(w)\( is finite, then for a uniform \)f\( it is rational, and for a non-uniform \)f\( it lies in the field extension \){{\mathbb Q}[{\lambda_1},\ldots,{\lambda_\ell}]}\(, where \)\lambda _{1},…,\lambda _{\ell }\( are the eigenvalues of the incidence matrix of \)f\(. In particular, \)E(w)\( is algebraic of degree at most \)t\(. Under certain conditions, our proof implies an algorithm for computing \)E(w)\(.\)
For the entire collection see [Zbl 1108.68001].
MSC:
68Q70 Algebraic theory of languages and automata
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI