- Report number: 2003-020
- Authors: Daniel Kirsten
- Title: Desert automata i. a burnside problem and its solution
We introduce a new model of weighted automata: the desert automata. We show the decidability of the limitedness problem for desert automata by solving the underlying Burnside problem. As an application of this result, we give a positive solution to the so-called finite substitution problem which was open for more than 10 years: given recognizable languages $K$ and $L$, decide whether there exists a finite substitution $\sigma$ such that $\sigma(K)=L$.