Helmut Veith

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

Bernd Borchert, Antoni Lozano

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

Bernd Borchert, Dietrich Kuske, Frank Stephan

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

Matthias Galota, Heribert Vollmer

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

Christian Glaßer

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

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