Prefix grammars: An alternative characterization of the regular languages

DOI10.1016/0020-0190(94)00074-3zbMath0813.68125OpenAlexW2003192754MaRDI QIDQ1332773

Michael Frazier, C. David jun. Page

Publication date: 5 September 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00074-3

zbMATH Keywords

regular languagesprefix grammarssuffix grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (5)

Peg-solitaire, string rewriting systems and finite automata ⋮ LARS: a learning algorithm for rewriting systems ⋮ Complexity results for prefix grammars ⋮ Multiple splicing systems and the universal computability ⋮ Derivation trees of ground term rewriting systems.

Cites Work

• Prediction-preserving reducibility
• Learning regular sets from queries and counterexamples
• When won't membership queries help?

This page was built for publication: Prefix grammars: An alternative characterization of the regular languages