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

prefix grammarsregular languagessuffix grammars

Mathematics Subject Classification ID

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

Review text

A prefix grammar \(G\) describes a language \(L_ G\) by (1) explicitly specifying a finite subset of the strings of \(L_ G\), and (2) specifying productions that rewrite prefixes of strings in \(L_ G\), to yield other strings in \(L_ G\). Suffix grammars can be defined in the obvious manner analogous to prefix grammars. This paper shows that prefix grammars generate exactly the regular languages.

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

(9)

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

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)