2 citations · 9 across the 12 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
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.CC2017
A universal tree balancing theorem
Moses Ganardi, Markus Lohrey
We present a general framework for balancing expressions (terms) in form of so called tree straight-line programs. The latter can be seen as circuits over the free term algebra ext…
cs.CC2016
Circuit Evaluation for Finite Semirings
Moses Ganardi, Danny Hucke, Daniel König +1
The computational complexity of the circuit evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or multiplicative identity. T…