wiki_research

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

pattern_language_equivalence (442B)

      1 # Pattern language equivalence
      2 
      3 [nowotka2024equivalence]: decidable for [non-erasing_substitutions]
      4 
      5 [open_problem] whether it is [decidable] for [erasing_substitutions]
      6 
      7 [NP_complete] for [erasing_substitutions] with [patterns_with_variables_terminal_free] [nowotka2024equivalence]
      8 
      9 [undecidability] if allowing [regular_language] constraints on variables, cf [nowotka2024equivalence]
     10 
     11 Up: [language_equivalence_problem], [pattern_language]