wiki_research

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

membership_problem (600B)

      1 # Membership problem
      2 
      3 given [formal_language] L description and [word] w, test if w belongs to L
      4 
      5 - [automaton_membership]
      6 - [regular_language_membership]
      7 - [pattern_language_membership]
      8 - [context_free_language_membership]
      9 
     10 - [radoszewski2021hardness] for hardness under [3SUM_conjecture] of testing membership of a [word] to some [formal_languages]
     11 
     12 Generalizations:
     13 - [probabilistic_membership_problem]
     14 
     15 Up: [formal_language_computational_problem]
     16 
     17 Aliases: formal language membership problem, formal language membership, language membership, language membership problem
     18 
     19 See also: [word_problem]