wiki_research

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

pattern_language_membership (316B)

      1 # Pattern language membership
      2 
      3 [membership_problem] for [pattern_languages]: given a [pattern_with_variables] p and [word] w, decide if w can be obtained from p via a substitution
      4 
      5 - [nowotka2024equivalence], [NP_complete] for both erasing and nonerasing substitutions
      6 
      7 Up: [pattern_language_computational_problems]