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
Full Text: