Prefix grammars: An alternative characterization of the regular languages

DOI10.1016/0020-0190(94)00074-3zbMATH Open0813.68125OpenAlexW2003192754MaRDI QIDQ1332773FDOQ1332773

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

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

zbMATH Keywords

regular languagesprefix grammarssuffix grammars

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Derivation trees of ground term rewriting systems.
• Complexity results for prefix grammars
• Peg-solitaire, string rewriting systems and finite automata
• Title not available (Why is that?)
• Regular prefix relations
• LARS: a learning algorithm for rewriting systems
• Multiple splicing systems and the universal computability
• Title not available (Why is that?)

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)