2 papers
cs.CC2026
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…
cs.FL2025
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 …