research
∙
04/21/2023
Revisiting Membership Problems in Subclasses of Rational Relations
We revisit the membership problem for subclasses of rational relations o...
share
research
∙
10/27/2022
Existential Definability over the Subword Ordering
We study first-order logic (FO) over the structure consisting of finite ...
research
∙
09/29/2022
Low-Latency Sliding Window Algorithms for Formal Languages
Low-latency sliding window algorithms for regular and context-free langu...
research
∙
05/18/2022
Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
Automatic structures are infinite structures that are finitely represent...
research
∙
11/09/2021
Pattern Matching on Grammar-Compressed Strings in Linear Time
The most fundamental problem considered in algorithms for text processin...
research
∙
07/01/2021
Compression by Contracting Straight-Line Programs
In grammar-based compression a string is represented by a context-free g...
research
∙
02/19/2020
The complexity of knapsack problems in wreath products
We prove new complexity results for computational problems in certain wr...
research
∙
09/23/2019
Sliding window property testing for regular languages
We study the problem of recognizing regular languages in a variant of th...
research
∙
02/10/2019
Balancing Straight-Line Programs
It is shown that a context-free grammar of size m that produces a single...
research
∙
06/01/2018
The Complexity of Bisimulation and Simulation on Finite Systems
In this paper the computational complexity of the (bi)simulation problem...
research
∙
02/21/2018
