uf14.pdf (262.53 kB)
Download fileFactorization in formal languages
conference contribution
posted on 2015-09-25, 08:48 authored by Paul Bell, Daniel Reidenbach, J.O. ShallitWe consider several language-theoretic aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of L is regular
if L is regular, and from this deduce an quadratic upper and lower bound on the length of the shortest word not in uf(L). We observe that uf(L) need not be context-free if L is context-free. Next, we consider some variations on unique factorization. We de ne a notion of \semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even nite, the set of words having such a factorization need not be context-free. Finally, we consider additional variations, such as unique factorization \up to permutation" and \up to subset". Although all these variations have
been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up to now. We also consider the length of the shortest word not having the
desired property.
History
School
- Science
Department
- Computer Science