A language C is a code relative to L if every word in L has a unique factorization into words of C; this is a generalization of a code. We extend this notion to d-decodability (respectively, finite-decodability) for \(d \ge 1\) , which means that every word in L has at most d (respectively, a finite number of) factorizations into words of C. We study decidability of testing this property on languages accepted (respectively, generated) by different machine (respectively, grammar) models. Then, we study applications of finite decodability towards a new notion regarding bounded languages called C-boundedness for a language C, leading to several new and general decidability results. In particular, we show that in any family with a decidable finiteness problem that is effectively closed under homomorphism, inverse homomorphism, and intersection with regular languages, it is decidable, given a language L in the family and a set \(\varSigma ^{\le l}\) of all strings of length at most l over \(\varSigma \) , whether there exist words \(w_1, \ldots , w_n\) in \(\varSigma ^{\le l}\) such that \(L \subseteq w_1^* \cdots w_n^*\) . This can be considered as a finite analog of the boundedness problem. This also implies that the letter-boundedness problem is always decidable in these families.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Relativized Codes, Finite Decodability, and Bounded Languages

  • Oscar H. Ibarra,
  • Ian McQuillan

摘要

A language C is a code relative to L if every word in L has a unique factorization into words of C; this is a generalization of a code. We extend this notion to d-decodability (respectively, finite-decodability) for \(d \ge 1\) , which means that every word in L has at most d (respectively, a finite number of) factorizations into words of C. We study decidability of testing this property on languages accepted (respectively, generated) by different machine (respectively, grammar) models. Then, we study applications of finite decodability towards a new notion regarding bounded languages called C-boundedness for a language C, leading to several new and general decidability results. In particular, we show that in any family with a decidable finiteness problem that is effectively closed under homomorphism, inverse homomorphism, and intersection with regular languages, it is decidable, given a language L in the family and a set \(\varSigma ^{\le l}\) of all strings of length at most l over \(\varSigma \) , whether there exist words \(w_1, \ldots , w_n\) in \(\varSigma ^{\le l}\) such that \(L \subseteq w_1^* \cdots w_n^*\) . This can be considered as a finite analog of the boundedness problem. This also implies that the letter-boundedness problem is always decidable in these families.