Simplify Regular Expression in Mathematica

17
votes

I recently found out about Kleene algebra for manipulating and simplifying regular expressions.

I'm wondering if this has been build into any computational software programs like Mathematica? It would be great to have a computational tool for doing unions and concatenations of large expressions and have the computer simplify them.

If you are not aware of any programs with this algebra built in, do you know any programs that allow extending their engines with new algebras?

1
regexalgorithmwolfram-mathematicaalgebra
Mathematica documentation contains a detailed tutorial on Working with String Patterns. It may be a good place to start. – kglr
@kguler: All documentation I've found, including that tutorial, only considers using regular expressions for basic string matching and manipulation purposes. – Thomas Ahle
Could you add an example of a specific problem that you would like to solve? It could be some toy example to illustrate the functionality needed. – Vitaliy Kaurov
Vitaliy: Mostly it would be simplifying expressions, calculating intersections and union, proving equality and relations. The kind of things you do with algebra I guess. It might also be able to transform things like a union over an infinite amount of terms into something based on * etc. – Thomas Ahle

1 Answers

5
votes

On http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, it states:

One of the basic results of the theory of finite automata is the famous Kleene theorem, which states that a language is acceptable by a finite automaton if and only if it can be represented by a regular expression.

and

The main difficulty of the algorithmic treatment of regular expressions is, however, their simplification. Although several identities are known concerning regular expressions, e.g., the rules of Kleene algebra, there does not exist an effective algorithm for solving the simplification problem of regular expressions.

and

Under the circumstances, the only way left is to develop heuristic algorithms for simplifying regular expressions. For the aut package, this paper outlines the Maple procedures Rsimplify, Rabsorb and Rexpand.

Im wondering if open-source implementations of Kleene Algebra algorithms exist.