research
∙
06/26/2023
Semënov Arithmetic, Affine VASS, and String Constraints
We study extensions of Semënov arithmetic, the first-order theory of the...
share
research
∙
07/15/2022
Matching Patterns with Variables Under Edit Distance
A pattern α is a string of variables and terminal letters. We say that α...
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
∙
05/01/2022
Formal Languages via Theories over Strings
We investigate the properties of formal languages expressible in terms o...
research
∙
06/11/2021
Matching Patterns with Variables under Hamming Distance
A pattern α is a string of variables and terminal letters. We say that α...
research
∙
05/03/2020
Efficiently Testing Simon's Congruence
Simon's congruence ∼_k is defined as follows: two words are ∼_k-equivale...
research
∙
01/30/2020
Reconstructing Words from Right-Bounded-Block Words
A reconstruction problem of words from scattered factors asks for the mi...
research
∙
06/17/2019
Matching Patterns with Variables
A pattern p (i.e., a string of variables and terminals) matches a word w...
research
∙
06/03/2019
On Modelling the Avoidability of Patterns as CSP
Solving avoidability problems in the area of string combinatorics often ...
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
∙
10/17/2018
Fast and Longest Rollercoasters
For k≥ 3, a k-rollercoaster is a sequence of numbers whose every maximal...
research
∙
02/02/2018
The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability
The study of word equations (or the existential theory of equations over...
research
∙
01/25/2018