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:
TR95-048 | 5th October 1995
Helmut Veith

Succinct Representation and Leaf Languages

In this paper, we present stronger results in the theory of succinct
problem representation by boolean circuits, and establish a close
relationship between succinct problems and leaf languages. As
a major tool, we use quantifierfree projection reductions
from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

TR96-006 | 24th January 1996
Bernd Borchert, Antoni Lozano

Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

This note connects two topics of Complexity Theory: The
topic of succinct circuit representations initiated by
Galperin and Wigderson and the topic of leaf languages
initiated by Bovet, Crescenzi, and Silvestri. It will be
shown for any language that its succinct version is
more >>>

TR97-013 | 13th February 1997
Bernd Borchert, Dietrich Kuske, Frank Stephan

On Existentially First-Order Definable Languages and their Relation to NP

Pin & Weil [PW95] characterized the automata of existentially
first-order definable languages. We will use this result for the following
characterization of the complexity class NP. Assume that the
Polynomial-Time Hierarchy does not collapse. Then a regular language
L characterizes NP as an unbalanced polynomial-time leaf language
if and ... more >>>

TR03-018 | 28th March 2003
Matthias Galota, Heribert Vollmer

Functions Computable in Polynomial Space

We show that the class of integer-valued functions computable by
polynomial-space Turing machines is exactly the class of functions f
for which there is a nondeterministic polynomial-time Turing
machine with a certain order on its paths that on input x outputs a 3x3
matrix with entries from {-1,0,1} on each ... more >>>

TR04-011 | 16th January 2004
Christian Glaßer

Counting with Counterfree Automata

We study the power of balanced regular leaf-languages.
First, we investigate (i) regular languages that are
polylog-time reducible to languages in dot-depth 1/2 and
(ii) regular languages that are polylog-time decidable.
For both classes we provide

- forbidden-pattern characterizations, and
- characterizations in terms of regular expressions.

Both ... more >>>

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