Straight-line grammar
A straight-line grammar (sometimes 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"). Areas of usefulness. Straight-line grammars are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). SLGs are of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures. The problem of  finding a context-free grammar (equivalently: an SLG) of minimal size that generates a given string is called the smallest grammar problem. Straight-line grammars (more precisely: straight-line context-free string grammars) can be generalized to "Straight-line context-free tree grammars". The latter can be used conveniently to compress trees. 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 directed 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. A mathematical definition of the more general formalism of straight-line context-free tree grammars can be found in Lohrey et al. An SLG in Chomsky normal form is equivalent to a straight-line program.