Revisiting Shinohara's algorithm for computing descriptive patterns
Revisiting Shinohara's algorithm for computing descriptive patterns
复制标题
重新审视筱原计算描述模式的算法
DOI：
10.1016/j.tcs.2018.04.035
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Markus L. Schmid
中科院分区：
文献类型：
--
作者：
H. Fernau;F. Manea;Robert Mercas;Markus L. Schmid
模式α是由常量和变量组成的词，它描述了所有词的模式语言L（α），这些词可以通过用常量词一致地替换变量来获得。1982年，Shinohara提出了一种算法，该算法计算出一个模式，该模式描述了一个有限的词集S，即它的模式语言在所有模式语言中以最接近的方式包含S。我们概括Shinohara的算法的子类模式，并将其适用的子类。此外，在这组模式类中，我们对Shinohara算法具有多项式运行时间的模式类进行了验证（在假设P≠ NP的情况下）。此外，我们还研究了模式的一致性问题的复杂性，即找到一个模式，分离两个给定的有限集的话。
A pattern α is a word consisting of constants and variables and it describes the pattern language L (α) of all words that can be obtained by uniformly replacing the variables with constant words. In 1982, Shinohara presents an algorithm that computes a pattern that is descriptive for a finite set S of words, ie, its pattern language contains S in the closest possible way among all pattern languages. We generalise Shinohara's algorithm to subclasses of patterns and characterise those subclasses for which it is applicable. Furthermore, within this set of pattern classes, we characterise those for which Shinohara's algorithm has a polynomial running time (under the assumption P≠ NP). Moreover, we also investigate the complexity of the consistency problem of patterns, ie, finding a pattern that separates two given finite sets of words.