On the maximality of languages with combined types of code properties

作     者：Kari, Lila Konstantinidis, Stavros Kopecki, Steffen 

作者机构：Univ Western Ontario London ON Canada St Marys Univ Halifax NS B3H 3C3 Canada 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第550卷第C期

页      面：79-89页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Code properties Deciphering delay Decoding delay Decidable Maximal codes Syntactic monoids 

摘      要：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. (C) 2014 Elsevier B.V. All rights reserved.