Regular prefix relations

DOI10.1007/BF01744439MaRDI QIDQ3763605zbMATH OpenFDO

Authors Dana Angluin, Douglas N. Hoover

Publication date 1984

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01744439

zbMATH Keywords

inductive inferencetree automatapumpingregular setsn-ary relations on stringsprefix automataregular prefix relationssecond order theory of k successors

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Recommendations

• Prefix grammars: An alternative characterization of the regular languages
• Deciding Whether or Not a Synchronous Relation is Regular Prefix
• Inference of -languages from prefixes.
• \(\mathcal{PS}\)-regular languages
• The prefix automaton

Cites work

• scientific article; zbMATH DE number 3947593 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• 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
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Language identification in the limit
• Tree acceptors and some of their applications

Cited in

(6)

• Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
• Rational relations having a rational trace on each finite intersection of rational relations
• Resynchronized uniformization and definability problems for rational relations
• Deciding Whether or Not a Synchronous Relation is Regular Prefix
• The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
• Learning two-tape automata from queries and counterexamples

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)