wiki_research

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

state_set_simulation (364B)

      1 # State set simulation
      2 
      3 [Algorithm] to test if a [word] is accepted by [automaton_epsilon_transitions]
      4 
      5 complexity O(nm) time and O(m) space
      6 
      7 Already mentioned in [thompson1968regular], cf [thompsons_automaton]
      8 
      9 accelerate it: [state_set_simulation_faster]
     10 
     11 Lower bounds from [backurs2016which]
     12 
     13 See also: [regular_expression_matching]
     14 
     15 Up: [automaton_acceptance]