47.pdf (645.71 kB)
Extended regular expressions: succinctness and decidability
conference contribution
posted on 2017-09-05, 14:00 authored by Dominik FreydenbergerDominik FreydenbergerMost modern implementations of regular expression engines allow the use of variables (also called back references). The resulting extended regular expressions (which, in the literature, are also called practical regular expressions, rewbr, or regex) are able to express non-regular languages. The present paper demonstrates that extended regular-expressions cannot be minimized effectively (neither with respect to length, nor number of variables), and that the tradeoff in size between extended and "classical" regular expressions is not bounded by any recursive function. In addition to this, we prove the undecidability of several decision problems (universality, equivalence, inclusion, regularity, and cofiniteness) for extended regular expressions. Furthermore, we show that all these results hold even if the extended regular expressions contain only a single variable. © Dominik D. Freydenberger.
History
School
- Science
Department
- Computer Science
Published in
Leibniz International Proceedings in Informatics, LIPIcsVolume
9Pages
507 - 518Citation
FREYDENBERGER, D.D., 2011. Extended regular expressions: succinctness and decidability. IN: Schwentick, T. and Dürr, C. (eds). Leibniz International Proceedings in Informatics: 28th Symposium on Theoretical Aspects of Computer Science (STACS’11), Dortmund, Germany, 10th-12th March, pp.507-518Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, GermanyVersion
- VoR (Version of Record)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2011Notes
This conference paper was presented at the 28th Symposium on Theoretical Aspects of Computer Science (STACS’11).ISBN
9783939897255ISSN
1868-8969Publisher version
Book series
Leibniz International Proceedings in Informatics (LIPIcs); 9Language
- en