Regular prefix relations
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.
- Abstract families of relations
- Characterizations of transductions defined by abstract families of transducers
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Decision Problems of Finite Automata Design and Related Arithmetics
- Generalised finite automata theory with an application to a decision problem of second-order logic
- scientific article; zbMATH DE number 3947593 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- Language identification in the limit
- Tree acceptors and some of their applications
- Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
- The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
- Deciding Whether or Not a Synchronous Relation is Regular Prefix
- Learning two-tape automata from queries and counterexamples
- Resynchronized uniformization and definability problems for rational relations
- Rational relations having a rational trace on each finite intersection of rational relations
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)