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 be an alphabet of size , let be a non-erasing morphism, let be an infinite fixed point of , and let be the critical exponent of . We prove that if is finite, then for a uniform it is rational, and for a non-uniform it lies in the field extension , where are the eigenvalues of the incidence matrix of . In particular, is algebraic of degree at most . Under certain conditions, our proof implies an algorithm for computing .
|68Q70||Algebraic theory of languages and automata|
|68R15||Combinatorics on words|