wiki_research

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

k_ambiguous_cfg (992B)

      1 # K ambiguous CFG
      2 
      3 A *k-ambiguous CFG* is a [CFG] where every [word] has at most k [parse_trees]
      4 
      5 Special cases:
      6 - k=1: [uCFGs]
      7 - k=2: [2_ambiguous_CFGs]
      8 - they exist for each value of k, cf [naji1998grad] p9
      9 
     10 It is an [open_problem] whether every k-ambiguous CFG can be written as a [language_union] of k [uCFGs], but within [bounded_CFGs] this is known to be true, cf [wich2005ambiguity] p181 point (iv).
     11 
     12 [Computational_problems]:
     13 - [CFG_inclusion]: [undecidable], in fact already [undecidable] for [linear_uCFGs]
     14 - [CFG_equivalence]: [open_problem] whether it is [decidable], in fact already open for [UCFGs]
     15 - [CFG_universality]: [undecidable], because testing if there is a word in the [intersection] of two [linear_UCFGs] is [undecidable] (by coding [Turing_machines] using [baker1974reversal])
     16 - counting the number of words in the [k_slice]: this is [sharpP1_hard] by [bertoni1991complexity]
     17 
     18 Up: [k_ambiguous], [CFG]
     19 
     20 See also: [infinitely_ambiguous_CFG], [Degree_of_ambiguity_cfg]