Regular prefix relations
Regular prefix relations
复制标题
正则前缀关系
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
D. N. Hoover
中科院分区：
文献类型：
--
作者：
D. Angluin;D. N. Hoover
本文定义了一类n元字符串关系，称为正则前缀关系，并给出了这类关系的四个可供选择的刻画：1.由一种新的自动机--前缀自动机所识别的关系; 2.由专门研究字符串关系的树自动机所识别的关系; 3.由k个后继者的二阶理论所定义的字符串之间的关系; 4.包含正则集和前缀关系的最小类，并且在布尔运算、笛卡尔积、投影、显式变换和与正则集的笛卡尔积的连接下是封闭的。
我们给出了具体的例子，经常前缀关系，和泵参数前缀自动机。应用这些结果的研究归纳推理的正则集。
AbstractWe define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class:1.the relations recognized by a new type of automaton, the prefix automata,2.the relations recognized by tree automata specialized to relations on strings,3.the relations between strings definable in the second order theory ofk successors,4.the smallest class containing the regular sets and the prefix relation, and closed under the Boolean operations, Cartesian product, projection, explicit transformation, and concatenation with Cartesian products of regular sets.
We give concrete examples of regular prefix relations, and a pumping argument for prefix automata. An application of these results to the study of inductive inference of regular sets is described.