Regular Sets and Expressions

Alexander Krauss ๐ŸŒ and Tobias Nipkow ๐ŸŒ with contributions from Manuel Eberl ๐ŸŒ and Christian Urban ๐ŸŒ

May 12, 2010

Abstract

This is a library of constructions on regular expressions and languages. It provides the operations of concatenation, Kleene star and derivative on languages. Regular expressions and their meaning are defined. An executable equivalence checker for regular expressions is verified; it does not need automata but works directly on regular expressions. By mapping regular expressions to binary relations, an automatic and complete proof method for (in)equalities of binary relations over union, concatenation and (reflexive) transitive closure is obtained.

Extended regular expressions with complement and intersection are also defined and an equivalence checker is provided.

License

BSD License

History

May 10, 2012
Tobias Nipkow added equivalence checking with partial derivatives
August 26, 2011
Christian Urban added a theory about derivatives and partial derivatives of regular expressions

Topics

Related publications

Session Regular-Sets