Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-147 | 5th December 2005 00:00

Machines that can Output Empty Words

RSS-Feed




TR05-147
Authors: Christian Gla├čer, Stephen Travers
Publication: 6th December 2005 21:57
Downloads: 2085
Keywords: 


Abstract:

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 to prove strong gap theorems: For any class C that is definable in the e-model, either $coUP \subseteq C$ or $C \subseteq NP$. For the existing models, gap theorems, where they exist at all, only identify gaps for the definability by regular languages. We prove gaps for the general case, i.e., for the definability by arbitrary languages. We obtain such general gaps for NP, coNP, 1NP, and co1NP. For the regular case we prove further gap theorems for Sigma_2, Pi_2, and Delta_2. These are the first gap theorems for Delta_2.

This work is related to former work by Bovet, Crescenzi, and Silvestri, Vereshchagin, Hertrampf et al., Burtschick and Vollmer, and Borchert et al.



ISSN 1433-8092 | Imprint