Deterministic regular expressions with back-references
Dominik Freydenberger
Markus L. Schmid
2134/37693
https://repository.lboro.ac.uk/articles/journal_contribution/Deterministic_regular_expressions_with_back-references/9401195
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.
2019-05-03 09:06:15
Deterministic regular expression
Regex
Glushkov automaton
Computation Theory and Mathematics
Information and Computing Sciences not elsewhere classified
Distributed Computing