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 technique ... more >>>

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 polynomial-time many-one complete for the leaf language ... more >>>

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 only ... more >>>

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

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 classes are ... more >>>

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