Computing maximal Kleene closures that are embeddable in a given subword-closed language

作     者：Konstantinidis, Stavros Santean, Nicolae 

作者机构：St Marys Univ Dept Math & Comp Sci Halifax NS B3H 3C3 Canada 

出 版 物：《NATURAL COMPUTING》 (自然计算)

年 卷 期：2013年第12卷第2期

页      面：211-222页

核心收录：

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

主　　题：Algorithm Automaton Code DNA encodings Maximal Regular language Subword closure 

摘      要：Motivated by certain coding techniques for reliable DNA computing, we consider the problem of characterizing nontrivial languages D that are maximal with the property that D (*) is contained in the subword closure of a given set S of words of some fixed length k. This closure is simply the set of all words whose subwords of length k must be in S. We provide a deep structural characterization of these languages D, which leads to polynomial time algorithms for computing such languages.