17

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?

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
  • 1
    Mathematica documentation contains a detailed tutorial on [Working with String Patterns](http://reference.wolfram.com/mathematica/tutorial/WorkingWithStringPatterns.html). It may be a good place to start. – kglr Jan 14 '12 at 01:11
  • 2
    @kguler: All documentation I've found, including that tutorial, only considers using regular expressions for basic string matching and manipulation purposes. – Thomas Ahle Jan 14 '12 at 01:50
  • 4
    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 Jan 15 '12 at 19:44
  • 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 Jan 15 '12 at 21:13

1 Answers1

5

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.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
propaganda
  • 470
  • 2
  • 6
  • 14
  • 1
    I see. I thought there were systems for simplifying all algebras, like Knuth–Bendix for groups, but now clearly there aren't. This question: http://stackoverflow.com/questions/7540227/strategies-for-simplifying-math-expressions talks about rule based systems for simplifying standard arithmetic and this paper: http://alleystoughton.us/forlan/book-and-slides/slides-3.2-twoup.pdf gives a lot of good rules to get started. However I'm still wondering if I really need to write a term-rewriting system from scratch, or there are ones I can plug into. Perhaps some of those Automated_theorem_prover's?.. – Thomas Ahle Jan 21 '12 at 21:54