Top Qs
Timeline
Chat
Perspective

Smallest grammar problem

From Wikipedia, the free encyclopedia

Remove ads
Remove ads

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.[1] Others also add the number of rules to that.[2] A grammar that generates only a single string, as required for the solution to this problem, is called a straight-line grammar.[3]

Every binary string of length has a grammar of length , as expressed using big O notation.[3] For binary de Bruijn sequences, no better length is possible.[4]

The (decision version of the) smallest grammar problem is NP-complete.[1] It can be approximated in polynomial time to within a logarithmic approximation ratio; more precisely, the ratio is where is the length of the given string and 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 would also improve certain algorithms for approximate addition chains.[5]

Remove ads

See also

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads