2015/03/21 by Paul Bell, Paul C. Bell, Daniel Reidenbach +4
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1503.06365
arxiv created 2015/03/21 · openalex publication_date 2015/03/21 · arxiv updated 2015/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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".