All reports by Author Stephen Travers:

__
TR06-090
| 22nd June 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang#### Non-Mitotic Sets

__
TR06-069
| 11th May 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner#### The Complexity of Unions of Disjoint Sets

__
TR05-147
| 5th December 2005
__

Christian Glaßer, Stephen Travers#### Machines that can Output Empty Words

__
TR05-035
| 24th March 2005
__

Christian Glaßer, Stephen Travers, Klaus W. Wagner#### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

This paper is motivated by the open question

whether the union of two disjoint NP-complete sets always is

NP-complete. We discover that such unions retain

much of the complexity of their single components. More precisely,

they are complete with respect to more general reducibilities.

Christian Glaßer, Stephen Travers

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

Christian Glaßer, Stephen Travers, Klaus W. Wagner

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 >>>