wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

smallest_grammar_problem (497B)

      1 # Smallest grammar problem
      2 
      3 The [computational_problem] of finding the smallest [CFG], in various contexts:
      4 
      5 - for a single word, i.e., [grammar_compression]
      6 - for [finite_languages]: the smallest [CFG] that generates a specific set of [words]
      7   - it is [np_complete]
      8   - studied in [charikar2005smallest]
      9 - for for [infinite_languages], cf [bucher1981concise]
     10 
     11 Up: [minimization] of [context_free_grammar]
     12 
     13 See also: [grammar_compression], [straight_line_program], [minimum_circuit_size_problem]