Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GAP THEOREMS:
Reports tagged with gap theorems:
TR05-147 | 5th December 2005
Christian Gla├čer, Stephen Travers

Machines that can Output Empty Words

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




ISSN 1433-8092 | Imprint