Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with leaf-languages:
TR05-035 | 24th March 2005
Christian Gla├čer, Stephen Travers, Klaus W. Wagner

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

We introduce the polynomial-time tree reducibility
(ptt-reducibility). Our main result states that for
languages $B$ and $C$ it holds that
$B$ ptt-reduces to $C$ if and only if
the unbalanced leaf-language class of $B$ is robustly contained in
the unbalanced leaf-language class of $C$.
... more >>>

ISSN 1433-8092 | Imprint