regexen.pdf (416.73 kB)

Extended regular expressions: succinctness and decidability

Download (416.73 kB)
journal contribution
posted on 19.09.2017 by Dominik Freydenberger
Most modern implementations of regular expression engines allow the use of variables (also called backreferences). 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, 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. © 2012 Springer Science+Business Media, LLC.

History

School

  • Science

Department

  • Computer Science

Published in

Theory of Computing Systems

Volume

53

Issue

2

Pages

159 - 193

Citation

FREYDENBERGER, D.D., 2013. Extended regular expressions: succinctness and decidability. Theory of Computing Systems, 53 (2), pp.159-193

Publisher

© Springer Science+Business Media, LLC

Version

AM (Accepted Manuscript)

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

2013

Notes

A preliminary version of this paper appeared in the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pp.507-518.

ISSN

1432-4350

eISSN

1433-0490

Language

en

Exports

Logo branding

Keyword(s)

Exports