Uproszczenie wyrażeń regularnych w Mathematica

Question

Niedawno dowiedziałem się o Kleene algebra do manipulowania i upraszczania wyrażeń regularnych.

Zastanawiam się, czy zostało to wbudowane w jakiekolwiek oprogramowanie komputerowe, takie jak Mathematica? Byłoby wspaniale mieć narzędzie obliczeniowe do robienia związków i konkatenacji dużych wyrażeń i upraszczania ich przez komputer.

Jeśli nie znasz żadnych programów z wbudowaną algebrą, czy znasz jakieś programy, które umożliwiają rozszerzenie swoich silników o nowe algebry?

Answer 1

Na http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, stwierdza:

Jednym z podstawowych wyników teorii automatów skończonych jest znanym twierdzeniem Kleene, w którym stwierdza się, że język jest do zaakceptowania przez skończonego automatu wtedy i tylko wtedy, może być reprezentowany przez regularne wyrażenie .

i

Główną trudność algorytmicznego leczeniu regularnych wyrażeń jest jednak ich uproszczenie. Chociaż znanych jest kilka tożsamości dotyczących wyrażeń regularnych, np. Reguł algebry Kleene'a, nie istnieje skuteczny algorytm do rozwiązania problemu uproszczenia wyrażeń regularnych przez .

i

W tej sytuacji jedynym sposobem, w lewo jest opracowanie algorytmów heurystycznych dla uproszczenia wyrażeń regularnych. W przypadku pakietu , w tym dokumencie przedstawiono procedury klonowania Rsimplify, Rabsorb i Rexpand.

Zastanawiam się, czy istnieją algorytmy Kleene Algebra o otwartym kodzie źródłowym.