2026-07-21T09:45:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4841 2024-03-06T10:35:24Z ddc:004 open_access

Symbolic Solving of Extended Regular Expression Inequalities Keil, Matthias Thiemann, Peter Extended regular expression containment infinite alphabet infinite character set effective boolean algebra 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Keil and Peter Thiemann 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.175 urn:nbn:de:0030-drops-48411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.175 eng https://creativecommons.org/licenses/by/3.0/legalcode