Bell, PC, Reidenbach, D and Shallit, J (2019) Unique Decipherability in Formal Languages. Theoretical Computer Science, 804. pp. 149-160. ISSN 0304-3975

Preview

Text BelReiSha.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (349kB) | Preview

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 UF(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.

Item Type:	Article
Uncontrolled Keywords:	08 Information and Computing Sciences, 01 Mathematical Sciences
Subjects:	P Language and Literature > P Philology. Linguistics
Divisions:	Computer Science & Mathematics
Publisher:	Elsevier
Date Deposited:	26 Nov 2019 14:38
Last Modified:	04 Sep 2021 08:23
URI:	https://researchonline.ljmu.ac.uk/id/eprint/11801

View Item