wiki_research

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

matching_patterns_with_variables_automata (466B)

      1 # Pattern matching automata
      2 
      3 [matching_patterns_with_variables] on [automata]: given an [automaton] A and a [pattern_with_variables] p, does A accept a word that matches p
      4 
      5 The [decision_problem] is [PSPACE_complete] in [combined_complexity]
      6 
      7 studied in [anderson2009detecting] and [rampersad2010detecting]
      8 
      9 Up: [matching_patterns_with_variables], [automata]
     10 
     11 Aliases: DFA pattern acceptance, NFA pattern acceptance, automaton pattern acceptance, pattern acceptance