Back to Search
Start Over
Factorization in Formal Languages
- Publication Year :
- 2015
- Publisher :
- arXiv, 2015.
-
Abstract
- We consider several novel 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 variations on unique factorization. We define a notion of "semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even finite, 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".
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....860eee49652ef230a4ab74f9604582f0
- Full Text :
- https://doi.org/10.48550/arxiv.1503.06365