|This article needs additional citations for verification. (August 2014) (Learn how and when to remove this template message)|
||This article appears to contradict the article Smallest grammar problem. (August 2014) (Learn how and when to remove this template message)|
A straight-line grammar (sometimes with "straight-line" in scare quotes, also abbreviated as SLG) is a formal grammar that generates exactly one string. Consequently, it does not branch (every non-terminal has only one associated production rule) nor loop (if non-terminal A appears in a derivation of B, then B does not appear in a derivation of A).
A context-free grammar G is an SLG if:
1. for every non-terminal N, there is at most one production rule that has N as its left-hand side, and
A list of algorithms using SLGs
- The Sequitur algorithm constructs a straight-line grammar for a given string.
- The Lempel-Ziv-Welch algorithm creates a context-free grammar in a such deterministic way that it is necessary to store only the start rule of the generated grammar.
- Byte pair encoding
- Grammar-based code
- Non-recursive grammar - a grammar that doesn't loop, but may branch; generating a finite rather than a singleton language
- Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441, p. 488
- Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Parameter Reduction in Grammar-Compressed Trees". Proc. FOSSACS (PDF). LNCS. 5504. Springer. pp. 212–226. Here: p.215, Sect.2
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|