Prefix grammars: An alternative characterization of the regular languages

DOI10.1016/0020-0190(94)00074-3MaRDI QIDQ1332773zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1244205
• Complexity results for prefix grammars
• Prefix-free regular languages and pattern matching
• scientific article; zbMATH DE number 7315105
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• On the regular structure of prefix rewriting
• scientific article; zbMATH DE number 125883
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Complexity of proper prefix-convex regular languages

Cites work

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

Cited in

(8)

• Derivation trees of ground term rewriting systems.
• Complexity results for prefix grammars
• Peg-solitaire, string rewriting systems and finite automata
• scientific article; zbMATH DE number 1744267 (Why is no real title available?)
• Regular prefix relations
• LARS: a learning algorithm for rewriting systems
• scientific article; zbMATH DE number 3843156 (Why is no real title available?)
• Multiple splicing systems and the universal computability

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

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