wiki_research

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

smallest_grammar_problem (653B)

      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 [infinite_languages], cf [bucher1981concise]
     10 
     11 Related: https://cstheory.stackexchange.com/questions/11747/minimal-number-of-symbols-in-context-free-grammar-for-a-special-one-letter-langu
     12 
     13 Up: [minimization] of [context_free_grammar]
     14 
     15 See also: [grammar_compression], [straight_line_program], [minimum_circuit_size_problem], [addition_chain]