wiki_research

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

context_free_grammar_unambiguous_equivalence_problem (726B)

      1 # Unambiguous CFG equivalence problem
      2 
      3 It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. More general problem: [CFG_multiplicity_equivalence]
      4 
      5 cf https://cstheory.stackexchange.com/questions/38598/is-equivalence-of-unambiguous-context-free-languages-decidable
      6 
      7 By contrast:
      8 - [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable]
      9 - equivalence of a [UCFG] with a [regular_language] is [decidable] according to [jez2013unambiguous] p2
     10 
     11 Up: [context_free_grammar_equivalence_problem], [uCFGs]
     12 
     13 Aliases: unambiguous CFG equivalence problem, equivalence context free grammar unambiguous, UCFG equivalence, UCFG equivalence problem
     14 
     15 See also: [DPDA_equivalence]