state_set_simulation_faster (869B)
1 # State set simulation faster 2 3 idea: decompose [thompson_automaton] into a tree of small [TNFAs] 4 - two [TNFAs] overlap in at most two states 5 - do [state_set_simulation] inside each [TNFA] twice: [state_set_simulation_tabulation] 6 - uses the fact that each simple path has at most one back-edge to say that doing it twice suffices 7 (myers1992, bille2006) 8 9 ## Word-level parallelism 10 11 other idea: word-level parallelism, reading a block that corresponds to a machine word 12 - main problem: epsilon transitions 13 14 idea: separator that splits [TNFA] in two halves of roughly equal size such that paths have to go through the separator 15 16 [bille2010regular] 17 18 Limits: cannot do better than Omega(nm/w) for w the word size 19 20 Can go faster: [bille2009faster], divided by log^{1.5}, 4 traversals over the [TNFAs] 21 22 "2D Decomposition algorithm" 23 24 Up: [state_set_simulation], [log_shaving]