Regular prefix relations

DOI10.1007/BF01744439zbMath0627.68066MaRDI QIDQ3763605

Douglas N. Hoover, Dana Angluin

Publication date: 1984

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

zbMATH Keywords

pumpingtree automatainductive inferenceregular 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)

Related Items (4)

Learning two-tape automata from queries and counterexamples ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Rational relations having a rational trace on each finite intersection of rational relations ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

Cites Work

• Unnamed Item
• Unnamed Item
• Tree acceptors and some of their applications
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Characterizations of transductions defined by abstract families of transducers
• Language identification in the limit
• Abstract families of relations

This page was built for publication: Regular prefix relations