License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.175
URN: urn:nbn:de:0030-drops-48411
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4841/
Go to the corresponding LIPIcs Volume Portal

Keil, Matthias ; Thiemann, Peter

Symbolic Solving of Extended Regular Expression Inequalities

pdf-format:
17.pdf (0.4 MB)

Abstract

This paper presents a new algorithm for the containment problem for extended regular expressions that contain intersection and complement operators and that range over infinite alphabets. The algorithm solves extended regular expressions inequalities symbolically by term rewriting and thus avoids the translation to an expression-equivalent automaton.

Our algorithm is based on Brzozowski's regular expression derivatives and on Antimirov's term-rewriting approach to check containment. To deal with large or infinite alphabets effectively, we generalize Brzozowski's derivative operator to work with respect to (potentially infinite) representable character sets.

BibTeX - Entry

@InProceedings{keil_et_al:LIPIcs:2014:4841,
  author =	{Matthias Keil and Peter Thiemann},
  title =	{{Symbolic Solving of Extended Regular Expression Inequalities}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{175--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4841},
  URN =		{urn:nbn:de:0030-drops-48411},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.175},
  annote =	{Keywords: Extended regular expression, containment, infinite alphabet,   infinite character set, effective boolean algebra}
}

Keywords: Extended regular expression, containment, infinite alphabet, infinite character set, effective boolean algebra
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI