UIB-1991-02 Compiler-Based Implementation of Syntax-Directed Functional Programming
Autoren: K. Gladitz and H. Fassbender and H. Vogler
We consider particular functional programs in which on the one hand the recursion is restricted to syntax-directed recursion and on the other hand simultaneous recursion and nesting of function calls in parameter positions of other functions is allowed. For such programs called syntax-directed functional programs, we formalize a compiler-based implementation of the call-by-name computation strategy. The machine involved in this implementation, called syntax-directed runtime-stack machine, is minimal in the sense that it computes exactly the class sdFun of functions which are expressible by syntax-directed functional programs. We verify this minimality property by showing a one-to-one correspondence between the implementation presented in this paper, and an interpreter-based implementation of syntax-directed functional programs on checking-tree nested-stack transducers. It is known from the literature that such transducers characterize in a formal sense the class sdFun.
UIB-1991-04 Graph Isomorphism is low for PP
Autoren: Johannes Köbler, Uwe Schöning and Jacobo Toran
UIB-1991-07 The Power of the Middle Bit
Autoren: Frederic Green, Johannes Köbler and Jacobo Toran
We study the class of languages which can be solved in polynomial time with the additional information of one bit from a #P function. In particular we show that the polynomial hierarchy and the classes ModkP are low for this class. We translate these results to the area of circuit complexity using the concept of a MidBit gate, which is defined to take binary inputs x_1,...,x_n and output the middle bit in the binary representation of the sum over the inputs. We show that every language in ACC can be computed by a family of depth-2 deterministic circuits of quasi-polynomial size with a MidBit gate at the root and AND-gates of poly-logarithmic fan-in at the leaves. This result improves the known upper bounds for the class ACC.
UIB-1991-08 Reductions to Sets of Low Information Content
Autoren: V. Arvind, Y. Han, L. Hamachandra, J. Köbler, A. Lozano, M. Mundhenk, A. Ogiwara, U. Schöning, R. Silvestri and T. Thierauf
This paper is concerned with three basic questions about sparse sets: (1) With respect to what types of reductions might NP have hard or complete sparse sets? (2) If a set A reduces to a sparse set, does it follow that A is reducible to some sparse set that is ``simple'' relative to A? (3) With respect to what types of reductions might NP have hard or complete sets of low instance complexity, and, relatedly, what is the structure of the class of sets with low instance complexity? With respect to the first and third questions, intuitively one would expect that even with respect to flexible reductions NP is unlikely to have complete sets whose information content is low. With respect to the second question, one might intuitively feel that the structure imposed on a set by the fact that it reduces to a sparse set makes it plausible that we can indeed find a simple sparse set that can masquerade as the original sparse set. These two intuitions are in many ways certified by the current literature, and by the results of this paper.