3 papers
cs.DS2026
Ranked MSO-enumeration over compressed words
Markus Lohrey
It is shown that the ranked query enumeration problem for a fixed MSO-query on strings can be solved with linear preprocessing and constant delay in the grammar-compressed setting,…
math.GR2025
Parameterized Complexity of Factorization Problems
Markus Lohrey, Andreas Rosowski
We study the parameterized complexity of the following factorization problem: given elements of a monoid and a parameter , can be written as the product…
math.GR2025
Finding cycle types in permutation groups with few generators
Markus Lohrey, Andreas Rosowski
The problem whether a given permutation group contains a permutation with a given cycle type is studied. This problem is known to be NP-complete. In this paper it is shown that the…