Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436186 | Theoretical Computer Science | 2007 | 19 Pages |
Abstract
Let Σ be an alphabet of size t, let f:Σ∗→Σ∗ be a non-erasing morphism, let be an infinite fixed point of f, and let be the critical exponent of . We prove that if is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension Q[r,λ1,…,λℓ], where r,λ1,…,λℓ are the eigenvalues of the incidence matrix of f. In particular, is algebraic of degree at most t. Under certain conditions, our proof implies an algorithm for computing .
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics