Straight-line grammar

A straight-line grammar (sometimes with "straight-line" in scare quotes,[1] also abbreviated as SLG) is a formal grammar that generates exactly one string.[2] 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).[2]

SLGs are of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures.

The problem of finding an SLG of minimal size that generates a given string is called the Smallest grammar problem.

Formal Definition

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

2. the graph G=<V,E>, defined by V being the set of non-terminals and (A,B) ∈ E whenever B appears at the right-hand side of a production rule for A, is acyclic.[3]

An SLG in Chomsky normal form is equivalent to a straight-line program.

A list of algorithms using SLGs

See also

References

  1. ↑ http://www.almob.org/content/1/1/4
  2. 1 2 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
  3. ↑ 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 article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.