| Home |
| About |
| Submission |
| Updating Entries |
| Using Entries |
| Search |
| Statistics |
| Index |
| Download |
Regular Sets and Expressions
| Title: | Regular Sets and Expressions |
| Authors: | Alexander Krauss and Tobias Nipkow |
| Contributor: | Manuel Eberl |
| Submission date: | 2010-05-12 |
| 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. |
| Change history: | [2011-08-26]: Christian Urban added a theory about derivatives and partial derivatives of regular expressions [2012-05-10]: Tobias Nipkow added extended regular expressions [2012-05-10]: Tobias Nipkow added equivalence checking with partial derivatives |
| BibTeX: |
@article{Regular-Sets-AFP,
author = {Alexander Krauss and Tobias Nipkow},
title = {Regular Sets and Expressions},
journal = {Archive of Formal Proofs},
month = may,
year = 2010,
note = {\url{http://isa-afp.org/entries/Regular-Sets.html},
Formal proof development},
ISSN = {2150-914x},
}
|
| License: | BSD License |
| Used by: | Abstract-Rewriting, Coinductive_Languages, Containers, Finite_Automata_HF, Functional-Automata, Lambda_Free_KBOs, List_Update, Myhill-Nerode, Posix-Lexing, Quick_Sort_Cost, Regex_Equivalence, Transitive-Closure-II |
| Status: [ok] | This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations. |
|
Proof outline Proof document |
| Browse theories |
| Download this entry |