4 papers
On the complexity of computing Strahler numbers
Moses Ganardi, Markus Lohrey
It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform . For several var…
Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
Kilian Lichtner, Pascal BergsträÃer, Moses Ganardi +2
Ramsey quantifiers have recently been proposed as a unified framework for handling properties of interests in program verification involving proofs in the form of infinite cliques,…
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
The complexity of knapsack problems in wreath products
Michael Figelius, Moses Ganardi, Markus Lohrey +1
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we s…