On Critical Exponents in Fixed Points of Non-Erasing Morphisms

Dalia Krieger


Abstract

Let $\Sigma$ be an alphabet of size $t$, let $f:\Sigma^*\rightarrow\Sigma^*$ be a non-erasing morphism, let $\mathbf w$ be an infinite fixed point of $f$, and let $E(\mathbf w)$ be the critical exponent of $\mathbf w$. We prove that if $E(\mathbf w)$ is finite, then for a uniform $f$ it is rational, and for a non-uniform $f$ it lies in the field extension $\Q[\lambda_1,\ldots,\lambda_\ell]$, where $\lambda_1,\ldots,\lambda_\ell$ are the distinct eigenvalues of the incidence matrix of $f$. In particular, $E(\mathbf w)$ is algebraic of degree at most $t$. We also give an algorithm for computing $E(\mathbf w)$. \\\\ {\bf MSC}: 68R15\\ {\bf Key Words}: Critical exponent; Circular D0L languages


Server START Conference Manager
Update Time 20 Feb 2006 at 20:05:03
Maintainer zdang@eecs.wsu.edu.
Start Conference Manager
Conference Systems