• Source: Smallest grammar problem

In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.
Others also add the number of rules to that. A grammar that generates only a single string, as required for the solution to this problem, is called a straight-line grammar.
Every binary string of length



n


{\displaystyle n}

has a grammar of length



O
(
n

/

log
⁡
n
)


{\displaystyle O(n/\log n)}

, as expressed using big O notation. For binary de Bruijn sequences, no better length is possible.
The (decision version of the) smallest grammar problem is NP-complete.
It can be approximated in polynomial time to within a logarithmic approximation ratio; more precisely, the ratio is



O
(
log
⁡



n
g



)


{\displaystyle O(\log {\tfrac {n}{g}})}

where



n


{\displaystyle n}

is the length of the given string and



g


{\displaystyle g}

is the size of its smallest grammar. It is hard to approximate to within a constant approximation ratio. An improvement of the approximation ratio to



o
(
log
⁡
n

/

log
⁡
log
⁡
n
)


{\displaystyle o(\log n/\log \log n)}

would also improve certain algorithms for approximate addition chains.




See also


Grammar-based code
Kolmogorov complexity
Lossless data compression




References






External links


"CFG-Kolm-complexity is singleton sets with Lance and Bill". Computational Complexity. June 9, 2024.

Kata Kunci Pencarian:

• Daftar algoritme
• Smallest grammar problem
• Grammar-based code
• Grammar induction
• Straight-line grammar
• Audio codec
• Discrete cosine transform
• Silence compression
• John Kieffer
• Finnish grammar
• Knox Grammar School