wiki_research

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

membership_problem (444B)

      1 # Membership problem
      2 
      3 given [formal_language] L description and [word] w, test if w belongs to L
      4 
      5 - [regular_language_membership]
      6 - [pattern_language_membership]
      7 - [context_free_language_membership]
      8 
      9 - [radoszewski2021hardness] for hardness under [3SUM_conjecture] of testing membership of a string to some [formal_languages]
     10 
     11 Up: [formal_language_computational_problem]
     12 
     13 Aliases: formal language membership problem, formal language membership