Regular prefix relations

From MaRDI portal





We define a class of n-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 of k 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.











This page was built for publication: Regular prefix relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3763605)