A Burnside Approach to the Finite Substitution Problem |
| |
Authors: | Daniel Kirsten |
| |
Affiliation: | (1) Institute of Algebra, Dresden University of Technology, D-01062 Dresden, Germany |
| |
Abstract: | We introduce a new model of weighted automata: the desert automata. We show
that their limitedness problem is PSPACE-complete 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 σ such that σ(K) = L. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|