Article ID Journal Published Year Pages File Type
436186 Theoretical Computer Science 2007 19 Pages PDF
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