research
∙
06/28/2022
Extending Shinohara's Algorithm for Computing Descriptive (Angluin-Style) Patterns to Subsequence Patterns
The introduction of pattern languages in the seminal work [Angluin, “Fin...
share
research
∙
06/28/2022
Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
We consider subsequences with gap constraints, i.e., length-k subsequenc...
research
∙
01/25/2021
Spanner Evaluation over SLP-Compressed Documents
We consider the problem of evaluating regular spanners over compressed d...
research
∙
01/06/2021
Fine-Grained Complexity of Regular Path Queries
A regular path query (RPQ) is a regular expression q that returns all no...
research
∙
10/26/2020
A Purely Regular Approach to Non-Regular Core Spanners
The regular spanners (characterised by vset-automata) are closed under t...
research
∙
05/14/2020
Shortest Distances as Enumeration Problem
We investigate the single source shortest distance (SSSD) and all pairs ...
research
∙
12/19/2019
Conjunctive Regular Path Queries with String Variables
We introduce the class CXRPQ of conjunctive xregex path queries, which a...
research
∙
06/17/2019
Matching Patterns with Variables
A pattern p (i.e., a string of variables and terminals) matches a word w...
research
∙
03/14/2019
Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
Regular expressions with backreferences (regex, for short), as supported...
research
∙
02/28/2019
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
We investigate the locality number, a recently introduced structural par...
research
∙
02/05/2018
Deterministic Regular Expressions With Back-References
Most modern libraries for regular expression matching allow back-referen...
research
∙
06/19/2017