We develop decision procedures for extended regular expressions in the new \(\textbf{ERE} \texttt {\#}\) framework that uses span semantics, utilizing the power of symbolic derivatives. We prove a normal form theorem in Lean for \(\textbf{ERE} \texttt {\#}\) 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Regex Decision Procedures in Extended RE#

  • Ian Erik Varatalu,
  • Margus Veanes,
  • Ekaterina Zhuchko,
  • Juhan Ernits

摘要

We develop decision procedures for extended regular expressions in the new \(\textbf{ERE} \texttt {\#}\) framework that uses span semantics, utilizing the power of symbolic derivatives. We prove a normal form theorem in Lean for \(\textbf{ERE} \texttt {\#}\) 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.