Unique decipherability in formal languages

Bell, Paul C.; Reidenbach, Daniel; Shallit, Jeffrey O.

Abstract

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD(L) in L* that have unique factorization over L. We also consider similar notions for weaker forms of unique decipherability, such as numerically decipherable words ND(L), multiset decipherable words MSD(L) and set decipherable words SD(L). Although these notions of unique factorization have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up until now. We show that UD(L), ND(L), MSD(L) and SD(L) need not be context-free if L is context-free. In fact ND(L) and MSD(L) need not be context-free even if L is finite, although UD(L) and SD(L) are regular in this case. We show that if L is context-sensitive, then so are UD(L), ND(L), MSD(L) and SD(L). We also prove that the membership problem (resp., emptiness problem) for these classes is PSPACE-complete (resp., undecidable). We finally determine upper and lower bounds on the length of the shortest word of L* not having the various forms of unique decipherability into elements of L

Citation

Bell, P. C., Reidenbach, D., & Shallit, J. O. (2020). Unique decipherability in formal languages. Theoretical Computer Science, 804, 149 - 160. https://doi.org/10.1016/j.tcs.2019.11.022

• Journal Article Type: Article
• Acceptance Date: Nov 16, 2019
• Online Publication Date: Nov 22, 2019
• Publication Date: Jan 12, 2020
• Publicly Available Date: May 30, 2023
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 804
• Pages: 149 - 160
• DOI: https://doi.org/10.1016/j.tcs.2019.11.022
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0304397519307480?via%3Dihub