3 citations · 5 across the 7 of their papers we have counts for
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…
Matching Patterns with Variables
Florin Manea, Markus L. Schmid
A pattern p (i.e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of p by terminal words. The respective matching…
Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
Markus L. Schmid
Regular expressions with backreferences (regex, for short), as supported by most modern libraries for regular expression matching, have an NP-complete matching problem. We define a…
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
Katrin Casel, Joel D. Day, Pamela Fleischmann +3
We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two importa…