wiki_research

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

state_set_simulation_tabulation (461B)

      1 # State set simulation tabulation
      2 
      3 Doing [state_set_simulation_faster] on a [TNFA] which is small relative to the word size
      4 
      5 - Encode state-set as bit string
      6   - to read a letter, do "[shift_and] technique" [bit_tricks]
      7   - to move forward with [epsilon_edges], do [universal_tabulation] for each possible [TNFA]
      8 
      9 you get complexity O(nm/log n) with n the [word] size and m the [regular_expression] size
     10 
     11 cf [bille2008faster]
     12 
     13 Up: [state_set_simulation_faster]