کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434111 | 689684 | 2014 | 11 صفحه PDF | دانلود رایگان |
We consider the decision problem of whether or not a given regular language is maximal with respect to certain combined types of code properties. In the recent past, there have been a few formal methods for defining code properties, such as the trajectory-based type of codes and the transducer-based type of codes, that allow one to decide the maximality problem, including the case where maximality is tested with respect to combined properties within these formal methods. The property of “deciphering delay 1”, also known as decoding delay 1, is not known to be definable with these methods, but it is known that the maximality of this property alone is decidable for regular languages. Here, we consider the problem of deciding maximality of a regular language with respect to deciphering delay 1 and a transducer-based property, such as suffix code, overlap-free language, and error-detection properties.
Journal: Theoretical Computer Science - Volume 550, 18 September 2014, Pages 79–89