Regular prefix relations |
| |
Authors: | Dana Angluin Douglas N Hoover |
| |
Affiliation: | 1. Computer Science Department, Yale University, 06520, New Haven, Conn., USA 2. Department of Mathematics and Statistics, Queen's University, K7L 3N6, Kingston, Canada
|
| |
Abstract: | We define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class: - the relations recognized by a new type of automaton, the prefix automata,
- the relations recognized by tree automata specialized to relations on strings,
- the relations between strings definable in the second order theory ofk successors,
- 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|