| Title: |
On the Complexity of Computing Strahler Numbers |
| Authors: |
Ganardi, Moses; Lohrey, Markus |
| Contributors: |
Moses Ganardi and Markus Lohrey |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Strahler number; circuit complexity classes; context-free grammars |
| Description: |
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 NC¹. For several variants, where the binary tree is given by a pointer structure or in a succinct form by a directed acyclic graph or a tree straight-line program, the complexity of computing the Strahler number is determined as well. The problem, whether a given context-free grammar in Chomsky normal form produces a derivation tree (resp., an acyclic derivation tree), whose Strahler number is at least a given number k is shown to be P-complete (resp., PSPACE-complete). |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.41 |
| DOI: |
10.4230/LIPIcs.STACS.2026.41 |
| Availability: |
https://doi.org/10.4230/LIPIcs.STACS.2026.41; https://nbn-resolving.org/urn:nbn:de:0030-drops-255301; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.41 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.39AD766 |
| Database: |
BASE |