Skip to main content
Kent Academic Repository

Simplifying Regular Expressions Further

Kahrs, Stefan, Runciman, Colin (2022) Simplifying Regular Expressions Further. Journal of Symbolic Computation, 109 . pp. 124-143. ISSN 0747-7171. (doi:10.1016/j.jsc.2021.08.003) (KAR id:91292)


We describe a cumulative series of transformations to simplify regular expressions, and investigate their effectiveness and cost. Transformations depending on increasingly powerful comparisons of expressions give results clearly superior to commonly used algebraic simplifications. Early in the series, efficient transformations enabled by language-invariant attributes are surprisingly effective. Later in the series, transformations depending on comparisons of expressed languages are made feasible by bounding the size of subexpressions to which they are applied. We set out the principles of our transformations, address some key implementation issues, and evaluate the results of systematic test measurements.

Item Type: Article
DOI/Identification number: 10.1016/j.jsc.2021.08.003
Uncontrolled keywords: Regular expression, Algebraic simplification, Semantic simplification
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Stefan Kahrs
Date Deposited: 03 Nov 2021 12:12 UTC
Last Modified: 26 Aug 2022 23:00 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.