det_JCSS.pdf (661.2 kB)
Download file

Deterministic regular expressions with back-references

Download (661.2 kB)
journal contribution
posted on 03.05.2019, 09:06 by Dominik FreydenbergerDominik Freydenberger, Markus L. Schmid
Most modern libraries for regular expression matching allow back-references (i. e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between expressiveness and tractability, we combine these with the notion of determinism for regular expressions used in XML DTDs and XML Schema. This includes the definition of a suitable automaton model, and a generalization of the Glushkov construction. We demonstrate that, compared to their non-deterministic superclass, these deterministic regular expressions with back-references have desirable algorithmic properties (i. e., efficiently solvable membership problem and some decidable problems in static analysis), while, at the same time, their expressive power exceeds that of deterministic regular expressions without back-references.

History

School

  • Science

Department

  • Computer Science

Published in

Journal of Computer and System Sciences

Volume

105

Pages

1-39

Citation

FREYDENBERGER, D.D. and SCHMID, M.L., 2019. Deterministic regular expressions with back-references. Journal of Computer and System Sciences, 105, pp.1-39.

Publisher

© Elsevier BV

Version

AM (Accepted Manuscript)

Publisher statement

This paper was accepted for publication in the journal Journal of Computer and System Sciences and the definitive published version is available at https://doi.org/10.1016/j.jcss.2019.04.001.

Acceptance date

18/04/2019

Publication date

2019-04-25

Copyright date

2019

ISSN

0022-0000

Language

en