Abstract We develop decision procedures for extended regular expressions in the new $$\textbf{ERE} \texttt {\#}$$ ERE # framework that uses span semantics , utilizing the power of symbolic derivatives . We prove a normal form theorem in Lean for $$\textbf{ERE} \texttt {\#}$$ ERE # that is closed under all Boolean operations and provides the basis for the given decision procedures. The tool is evaluated on existing SMT benchmarks for regexes that shows it to be the fastest solver to date – often orders of magnitude faster than state-of-the-art – albeit specialized for the single-variable fragment of string theory.

We present a tool and theory RE # for regular expression matching that is built on symbolic derivatives, does not use backtracking, and, in addition to the classical operators, also supports complement, intersection and restricted lookarounds. We develop the theory formally and show that the main matching algorithm has input-linear complexity both in theory as well as experimentally. We apply thorough evaluation on popular benchmarks that show that RE # is over 71% faster than the next fastest regex engine in Rust on the baseline, and outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude.

We describe a model-based construction of an online tester for black-box testing of the implementation under test(IUT). The external behaviour of the IUT is modelled as an output observable nondeterministic EFSM with the assumption that all transition paths are feasible. A test purpose is attributed to the IUT model by a set of Boolean variables called traps that are used to measure the progress of the test run. These variables are associated with the transitions of the IUT model. The situation where all traps have been reached means that the test purpose has been achieved. We present a way to construct a tester that at runtime selects a suboptimal test path from trap to trap by finding the shortest path to the next unvisited trap. The principles of reactive planning are implemented in the form of the decision rules of selecting the shortest paths at runtime. The decision rules are constructed in advance from the IUT model and the test purpose. Preliminary experimental results confirm that this method clearly out performs random choice and is better than the anti-ant algorithm in terms of resultant test sequence length to achieve the test purpose