Polynomial Time Inference of Extended Regular Pattern Languages
Polynomial Time Inference of Extended Regular Pattern Languages
复制标题
扩展正则模式语言的多项式时间推理
DOI：
10.1007/3-540-11980-9_19
复制
发表时间：
1983
影响因子：
4.8
通讯作者：
T. Shinohara
中科院分区：
文献类型：
--
作者：
T. Shinohara
模式是一串常量符号和变量符号。模式p的语言是通过用任何非空常量字符串替换p中的每个变量符号而获得的所有字符串的集合。规则模式的每个变量符号最多出现一次。在本文中，我们考虑多项式时间推断从正数据的类扩展的正则模式语言，这是通过取代任何（可能是空的）常数字符串，而不是非空字符串得到的所有字符串的集合。我们的推理机使用MINL计算，找到一个最小的语言包含一个给定的有限字符串集。讨论了扩展正则模式语言类的MINL计算与最长公共子序列问题的关系。
A pattern is a string of constant symbols and variable symbols. The language of a pattern p is the set of all strings obtained by substituting any non-empty constant string for each variable symbol in p. A regular pattern has at most one occurrence of each variable symbol. In this paper, we consider polynomial time inference from positive data for the class of extended regular pattern languages which are sets of all strings obtained by substituting any (possibly empty) constant string, instead of non-empty string. Our inference machine uses MINL calculation which finds a minimal language containing a given finite set of strings. The relation between MINL calculation for the class of extended regular pattern languages and the longest common subsequence problem is also discussed.