Finding patterns common to a set of strings (Extended Abstract)
Finding patterns common to a set of strings (Extended Abstract)
复制标题
查找一组字符串共有的模式（扩展摘要）
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
D. Angluin
中科院分区：
文献类型：
--
作者：
D. Angluin
我们激发、形式化和研究具体归纳推理中的计算问题。“模式”被定义为常量和变量的串联，模式的语言被定义为通过用常量字符串替换变量而获得的字符串集。我们考虑的问题是，给定一组字符串，找到包含该集合的最小模式语言。证明了该问题在一般情况下是有效可解的，并在模式语言的限制下得到了正确的推理。在单变量模式受限的情况下，存在一个多项式时间算法。从正数据的推论被重新检查，并给出了递归语言族何时可能的特征。得到了关于模式和模式语言的各种附带结果。第一节是导言，解释了这项工作的背景，并非正式地描述了问题的提出。第二节是定义。第3节是关于模式和模式语言的结果。第四节涉及从正数据进行推理的抽象问题。第五节给出了一个寻找与给定字符串集相容的最小单变量模式语言的多项式时间算法。第6节包含备注。
We motivate, formalize, and study a computational problem in concrete inductive inference. A “pattern” is defined to be a concatenation of constants and variables, and the language of a pattern is defined to be the set of strings obtained by substituting constant strings for the variables. The problem we consider is, given a set of strings, find a minimal pattern language containing this set. This problem is shown to be effectively solvable in the general case and to lead to correct inference in the limit of the pattern languages. There exists a polynomial time algorithm for it in the restricted case of one-variable patterns. Inference from positive data is re-examined, and a characterization given of when it is possible for a family of recursive languages. Various collateral results about patterns and pattern languages are obtained. Section 1 is an introduction explaining the context of this work and informally describing the problem formulation. Section 2 is definitions. Section 3 is results concerning patterns and pattern languages. Section 4 concerns the abstract question of inference from positive data. Section 5 gives a polynomial time algorithm for finding minimal one-variable pattern languages compatible with a given set of strings. Section 6 contains remarks.