LIAFA Laboratoire d'Informatique Algorithmique: Fondements et Applications CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 701475205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
 Staff Contact How to get to LIAFA Teaching Webmail

 Research reports

• Report number: 2003-020
• Authors: Daniel Kirsten
• Title: Desert automata i. a burnside problem and its solution
• Summary:

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$.
http://www.math.tu-dresden.de/~kirsten/publications/desert1.ps.gz

 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr