Module Make

Classes and predicates that create an NFA and various algorithms for working with it.

Gets a state for which there exists a transition in the NFA from `s’.

Gets the minimum length of a path from r to some an end state end.

Gets a char that is matched by all the edges s1, s2, and s3.

Gets the tuple (pivot, pumpEnd, pumpEnd) from the product automaton.

Gets a message for why term can cause polynomial backtracking.

Holds if tuple is an end state in our search. That means there exists a pair of loops (pivot, pumpEnd) such that tuple = (pivot, pumpEnd, pumpEnd).

Holds if matching repetitions of pump can: 1) Transition from pivot back to pivot. 2) Transition from pivot to pumpEnd. 3) Transition from pumpEnd to pumpEnd.

Holds if states starting in state can have polynomial backtracking with the string pump.

Holds if pivot and pumpEnd are a pair of loops that could be the beginning of a quadratic blowup.

Gets the minimum and maximum characters that intersect between a and b. This predicate is used to limit the size of getAThreewayIntersect.

Holds if repetitions of pump at t will cause polynomial backtracking.

Holds if there are transitions from the components of q to the corresponding components of r labelled with s1, s2, and s3, respectively.

Holds if there are transitions from the components of q to r1, r2, and r3 labelled withs1,s2, ands3`, respectively.

Holds if there exists a transition from r to q in the product automaton. Notice that the arguments are flipped, and thus the direction is backwards.

A term that may cause a regular expression engine to perform a polynomial number of match attempts, relative to the input length.

A state in the product automaton. The product automaton contains 3-tuples of states.

A list of tuples of input symbols that describe a path in the product automaton starting from some start state.