Simplifying regular expressions further. (March 2022)

• Record Type: Journal Article
• Authors: Kahrs, Stefan; Runciman, Colin
• Is Part Of: Journal of symbolic computation. Volume 109(2022)
• Page Start: 124
• Page End: 143
• Publication Date: 2022-03
• Subjects: 03D40; Regular expression -- Algebraic simplification -- Semantic simplification; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2021.08.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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.