4 papers · 1 filter
Conjunctive Regular Path Queries with String Variables
Markus L. Schmid
We introduce the class CXRPQ of conjunctive xregex path queries, which are obtained from conjunctive regular path queries (CRPQs) by adding string variables (also called backrefere…
Deterministic Regular Expressions With Back-References
Dominik D. 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 intractabili…
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
Daniel Reidenbach, Markus L. Schmid
In the present paper, we study the match test for extended regular expressions. We approach this NP-complete problem by introducing a novel variant of two-way multihead automata, w…
Two-Dimensional Pattern Languages
Henning Fernau, Markus L. Schmid, K. G. Subramanian
We introduce several classes of array languages obtained by generalising Angluin's pattern languages to the two-dimensional case. These classes of two-dimensional pattern languages…