Loughborough University
Browse
47.pdf (645.71 kB)

Extended regular expressions: succinctness and decidability

Download (645.71 kB)
conference contribution
posted on 2017-09-05, 14:00 authored by Dominik FreydenbergerDominik Freydenberger
Most 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, LIPIcs

Volume

9

Pages

507 - 518

Citation

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-518

Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Version

  • 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

2011

Notes

This conference paper was presented at the 28th Symposium on Theoretical Aspects of Computer Science (STACS’11).

ISBN

9783939897255

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics (LIPIcs); 9

Language

  • en

Usage metrics

    Loughborough Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC