Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

Einführung

Der Blattsprachenansatz ist ein Konzept der Komplexitätstheorie, ein Teilbereich der theoretischen Informatik.

Blattsprachen sind eine Methode zur Charakterisierung von Komplexitätsklassen; die Grundidee ist die folgende: Die Akzeptanz eines Wortes als Eingabe einer nichtdeterministischen Maschine hängt nur von den Werten an den Blättern des Berechnungsbaumes ab. Genauer, sei M eine nichtdeterministische Turingmaschine, deren Verzweigungen einer festgelegten Reihenfolge unterliegen, die auf jedem Pfad anhält und ein Symbol eines festgelegten Alphabetes ausgibt. Dann ist leafstringM(x) die Konkatenation der Symbole, die an den Blättern des Berechnungsbaumes von M bei Eingabe x ausgegeben werden. Nun sei eine Sprache A gegeben. Diese Sprache definiert die Klasse LeafP(A) aller Sprachen B, für die eine nichtdeterministische Polynomialzeitmaschine M wie oben existiert, sodass wir für alle x erhalten: x ist in B genau dann wenn leafstringM(x) in A ist. Ähnliche Notationen existieren für die Spezialfälle so genannter balancierter oder vollständiger Berechnungsbäume, für andere Ressourcen-Grenzen (logspace, logtime) und für andere Maschinenmodelle (NC1-Schaltkreise, endliche Automaten).

Seit den späten 70er Jahren gibt es das Konzept der Blattsprachen (laut Ch. Papadimitriou), aber die ersten Veröffentlichungen mit exakten Definitionen von Bovet, Crescenzi und Silvestri sowie unabhängig von Vereshchagin (siehe Verweise unten) erschienen erst Anfang der 90er Jahre.

Eng verbunden mit Obigem ist das Modell der lokal definierbaren Akzeptanztypen. Hier betrachten wir Klassen der Form (F)P, wobei F eine Klasse von Funktionen mit k-wertiger Logik ist (für irgendein k). Diese Klasse enthält alle Sprachen, die von nichtdeterministischen polynomiellen Turingmaschinen akzeptiert werden, wobei auf die Knoten des Berechnungsbaumes eine bestimmte Funktion aus F angewendet wird. Dieses Modell stammt ursprünglich von Goldschlager und Parberry. Sie beantworten die Frage der Mächtigkeit des Modells vollständig im Fall der zweiwertigen (d.h. booleschen) Logik.

Obige Notationen zeigen nur Möglichkeiten um Komplexitätsklassen einfacher zu beschreiben, sodass aus ihnen resultierende Schlussfolgerungen leichter zu ziehen sind. In der Tat halfen sie, um außergewöhnliche Resultate zu erzielen, unter anderem

  • die Identifizierung aller relativierbaren funktionalen Abschlusseigenschaften von #P
  • untere Schranken für Schaltkreisklassen, z.B. die Trennung von TC0 von PP
  • die Entwicklung einer neuen Sicht auf prägnante Repräsentationen (succinct represantations)
  • die Charakterisierung der Berechnungskraft so genannter Bottleneck-Maschinen.

Im Anschluss präsentieren wir eine ausführliche Liste von Publikationen, von denen die meisten online verfügbar sind. Sie können die Autoren dieser Seite über die unten angegebenen E-Mail-Adressen kontaktieren.

(Die chronologische Reihenfolge bezieht sich auf das Publikationsdatum entweder als technischer Bericht, Proceedings-Beitrag oder Journalartikel, diese Daten müssen sich nicht notwendig mit den angegebenen Daten decken. Wir hoffen, dass diese Angabe die wirkliche Chronologie besser reflektiert. Beim Suchen nach bestimmten Veröffentlichungen benutzen Sie bitte die Suchfunktion Ihres Browsers.)

Diese Seite wurde von Bernd Borchert und Heribert Vollmer erstellt und wird derzeit gewartet von Heribert Vollmer. Wenn Sie Veröffentlichungen einzufügen wüschen, schicken Sie bitte eine E-Mail an Heribert Vollmer.

Veröffentlichungen in chronologischer Reihenfolge

Leslie M. Goldschlager, Ian Parberry.
On the Construction of Parallel Computers from Various Bases of Boolean Functions.
Theoretical Computer Science 43, 1986, pp. 43-58.
Abstract. The effects of bases of two-input Boolean functions are characterized in terms of their impact on some questions in parallel computation. It is found that a certain set of bases (called the P-complete set), which are not necessarily complete in the classical sense, apparently makes the circuit value problem difficult, and renders extended Turing machines and networks of Boolean gates equal to general parallel computers. A class of problems called EP naturally arises from this study, relating to the parity of the number of solutions to a problem, in contrast to previously defined classes concerning the count of the number of solutions (#P) of the existence of solutions (NP). Tournament isomorphism is a member of EP.
Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri.
A Uniform Approach to Define Complexity Classes.
Theoretical Computer Science 104, 1992, pp. 263-283.
Abstract. Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and, therefore, they somehow hide the essential properties which insure the obtained results. In order to obtain more general results, a uniform family of computation models which encompasses most of the complexity classes of interest is introduced. As a first initial set of results derivable from the proposed approach, we will give a sufficient and necessary condition for proving separations of relativized complexity classes with complete languages and a sufficient condition for proving strong separations of relativized complexity classes. Examples of applications of these results to some specific complexity classes are then given. Additional results related to separations by sparse oracles can be found in Bovet et al. (1991).
Nicolai Vereshchagin.
Relativizable and Nonrelativizable Theorems in the Polynomial Theory of Algorithms.
Russian Acad. Sci. Izv. Math. 42, 1994, pp. 261-298. Die originale russische Version erschien 1993.
Abstract. Starting with the paper of Baker, Gill, and Solovay (1975) in complexity theory, many results have been proved that separate certain relativized complexity classes or show that they have no complete language. All results of this kind were, in fact, based on lower bounds for Boolean decision trees of a certain type or for machines with polylogarithmic restrictions on time. The following question arises: Are these methods of proving ``relativized'' results universal? In the first part of the present paper a general framework is proposed in which assertions of universality of this kind may be formulated and proved as convenient criteria. Using these criteria we obtain, as easy consequences of the known results on Boolean decision trees, some new ``relativized'' results and new proofs of some known results. In the second part of the paper, these general criteria are applied to many particular cases. For example, for many of the complexity classes studied in the literature all relativizable inclusions between the classes are found.
Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri.
Complexity Classes and Sparse Oracles.
Journal of Computer and System Sciences 50, 1995, pp. 382-390. Eine Vorabversion erschien in: Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 102-108.
Abstract. Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which insure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As a first initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in literature. In particular, our goal is to prove statements of the kind: ``Given two complexity classes C and D, C = D if and only if for every sparse set S, C(S) = D(S)''. We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously along with new ones can be immediately derived.
Ulrich Hertrampf.
Locally Definable Acceptance Types for Polynomial Time Machines.
Proc. 9th Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 577, Springer Verlag, 1992, pp.199-207.
Abstract. We introduce m-valued locally definable acceptance types, a new model generalizing the idea of alternating machines and their acceptance behaviour. The model can be described as follows: Consider polynomial time nondeterministic machines, and augment the nodes of the tree associated with a computation by functions from {0,...,m-1}r into {0,...,m-1}, where r is the number of successor nodes and m is some fixed positive integer. The leaves of the tree are labeled with constants (less than m), deterministic nodes take the unchanged value from their successor nodes. Thus from the leaves to the root we can compute a value for every node in the tree, and we say the tree accepts, if and only if the root value is 1. If all the functions appearing in nondeterministic nodes of a computation tree are from some set of functions F, then F is called an m-valued locally definable acceptance type. The class of languages recognizable by such machines with acceptance type F is denoted by (F)P. The case m=2 was (in some different context) investigated by Goldschlager and Parberry [GP86]. The only classes appearing as (F)P for 2-valued acceptance types F are P, NP, coNP, PARITYP, and PSPACE. In [H92] (see the next paper in this list) a complete classification of the classes (F)P is given, when F consists of only one binary 3-valued function. That case leads to the characterization of 20 complexity classes, among them the whole second level of the polynomial time hierarchy. In the current paper we justify the restriction to the case of one binary function by proving a normal form theorem stating that for every finite acceptance type (m-valued) there exists a finite acceptance type (m'-valued, with possibly m' > m) that characterizes the same class, but consists only of one binary function. Further we use the normal form theorem to show that if a class C is characterizable, then also exists-C, forall-C, parity-C, and similar classes built from C by certain kinds of operators can be characterized by finite locally definable acceptance types. In a similar fashion we show that all levels of boolean hierarchies over characterizable classes are characterizable. As corollaries from these results we obtain characterizations of all levels of the polynomial time hierarchy and the boolean hierarchy over NP.
Ulrich Hertrampf.
Locally Definable Acceptance Types - the Three Valued Case.
1st Latin American Symposium in Theoretical Informatics, Lecture Notes in Computer Science 583, Springer Verlag, 1992, pp. 262-271.
Abstract. We consider polynomial time nondeterministic machines, and augment the nodes of the tree associated with a computation by functions from {0,...,m-1}r into {0,...,m-1}, where r is the number of successor nodes and m is some fixed positive integer. The leaves of the tree are labeled with constants (less than m), deterministic nodes take the unchanged value from their successor nodes. Thus from the leaves to the root we can compute a value for every node in the tree, and we say the tree accepts, if and only if the root value is 1. If all the functions appearing in nondeterministic nodes of some computation tree are from some set of functions F, then F is called an m-valued locally definable acceptance type. The class of languages recognizable by such machines with acceptance type F is denoted by (F)P. The case m=2 was (in some different context) investigated by Goldschlager and Parberry [GP86]. The only classes appearing as (F)P for 2-valued acceptance types F are P, NP, coNP, PARITYP, and PSPACE. m-valued acceptance types for m > 2 were introduced in [H92] (see the previous paper in this list). There it is proved that for all finite m-valued acceptance types F there exists an m'-valued acceptance type G (with possibly different constant m'), such that (F)P = (G)P, and G consists of only one binary function. In the current paper we completely classify all classes (G)P where G is some 3-valued acceptance type consisting of only one binary function. It turns out that 20 classes are characterized by such acceptance types, trivially including the five classes appearing in the two-valued case, further the complete second level of the polynomial time hierarchy, some interesting very new classes (like Nabla-P and coNabla-P), and some classes that are well known, but did not have such a closed machine characterization before (like PNP[1]). The proof technique for the main result is the following: first some criteria are given that a function refers to a trivial class (i.e. a class already appearing in the two-valued case), then a computer program is designed to pick out only the relevant cases, and finally the remaining 104 functions are investigated in detail.
Riccardo Silvestri.
Complexity Classes and Relativizations.
Dissertation, University of Rome ``La Sapienza'', 1992.
Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus Wagner.
On the Power of Polynomial Time Bit-Reductions.
Proc. 8th Structure in Complexity Theory Conference, 1993, pp. 200-207.
Abstract. For a nondeterministic polynomial time Turing machine M and an input string x, the leaf string of M on x is the 0-1-sequence of leaf-values (0 - reject, 1 - accept) of the computation tree of M with input x. The set A is said to be bit-reducible to B if there exists an M as above such that for every input x, x is in A if and only if the leaf string of M on x is in B. A class C is definable via leaf language B, if C is the class of all languages that are bit-reducible to B. We are interested in the question how complex a leaf language must be in order to characterize some given class C. This question leads to the examination of the closure of different language classes under bit-reducibility. We settle this question for subclasses of regular languages, context free languages, and a number of time and space bounded classes. As consequences we get a number of surprising characterizations for PSPACE.
Rolf Niedermeier, Peter Rossmanith.
Extended Locally Definable Acceptance Types.
Erschienen unter dem Titel `Unambiguous computations and locally definable acceptance types', Theoretical Computer Science 194, 1998, pp. 137-161.
Abstract. Hertrampf's locally definable acceptance types showed that many complexity classes can be defined in terms of polynomially time bounded NTM's with simple local conditions on the nodes of its computation tree, rather than global concepts like number of accepting paths etc. We introduce extended locally definable acceptance types as a generalization of Hertrampf's concept in order to formally capture exactly all classes that are definable by simple local conditions in an intuitive sense. Among the new characterizable classes are UP and MODZk P. We show how different types of oracle access, e.g. guarded access, can be characterized by this model. This sheds new light on the discussion on how to access unambiguous computation. We present simple functions that describe precisely objects of current research as the unambiguous oracle, alternation, and promise hierarchies. We exhibit the new class UAP which seems to be an unambiguous analogue of Wagner's NablaP. UAP (and thus NablaP) contains Few and is currently the smallest class known with this property.
Bernd Borchert.
On the Acceptance Power of Regular Languages.
Theoretical Computer Science 148, 1995, pp. 207-225. Eine Vorabversion erschien in: Proc. 11th Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 775, Springer Verlag, 1994, pp. 533-542.
Abstract. Hertrampf, Lautemann, Schwentick, Vollmer & Wagner in [HLSVW93] looked at complexity classes which are characterized (say accepted) by a regular language for the words of output bits produced by nondeterministic polynomial-time computations. A number of well-known complexity classes between P and PSPACE are accepted by regular languages. For example, NP is accepted by the regular language which consists of the words which contain at least one letter 1. The main result will be that the inclusion order on the complexity classes accepted by regular languages has the following property: if a class accepted by a nontrivial regular language is not equal to P then it contains at least one of the classes NP, coNP and MODpP for p prime. This will be interpreted as a non-density result in two ways: (1) on the assumption that the Polynomial Time Hierarchy does not collapse, and (2) for the relativized case.
Bernd Borchert, Riccardo Silvestri.
A Characterization of the Leaf Language Classes.
Information Processing Letters 63, 1997, pp. 153-158. Eine Vorabversion erschien als: B. Borchert. Predicate classes and promise classes, Proc. 9th Structure in Complexity Theory Conference, 1994, pp. 235-241.
Abstract. Bovet, Crescenzi, and Silvestri [BCS91,BCS92], and independently Vereshchagin [Ve94], showed that many complexity classes in the polynomial time setting are leaf language classes, i.e. classes which are determined by two disjoint languages. They gave many examples but they did not characterize the set of leaf language classes. This will be done in this paper. It will be shown that the set of leaf language classes equals the set of countable complexity classes which, with respect to polynomial-time many-one reducibility, are closed downward and closed under join. Moreover, the set of classes characterized by two complementary leaf languages will be shown to be equal to the set of complexity classes which, with respect to polynomial-time many-one reducibility, have a complete set and are closed downward.
Bernd Borchert.
Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages.
Dissertation, Universität Heidelberg, 1994.
Abstract. Bovet, Crescenzi, and Silvestri [BCS91,BCS92], and independently Vereshchagin [Ve94], showed that many complexity classes in the polynomial time setting are leaf language classes, i.e. classes which are determined by two disjoint languages. They gave many examples but they did not characterize the set of leaf language classes. This will be done in this paper. It will be shown that the set of leaf language classes equals the set of countable complexity classes which, with respect to polynomial-time many-one reducibility, are closed downward and closed under join. Moreover, the set of classes characterized by two complementary leaf languages will be shown to be equal to the set of complexity classes which, with respect to polynomial-time many-one reducibility, have a complete set and are closed downward.
Birgit Jenner, Pierre McKenzie, Denis Therien.
Logspace and Logtime Leaf Languages.
Information and Computation 141, 1996, pp. 21-33.
Abstract. The computation tree of a nondeterministic machine M with input x gives rise to a leaf string formed by concatenating the outcomes of all the computations in the tree in lexicographical order. We may characterize problems by considering, for a particular ``leaf language'' Y, the set of all x for which the leaf string of M is contained in Y. In this way, in the context of polynomial time computation, leaf languages were shown to capture many complexity classes. In this paper, we study the expressibility of the leaf language mechanism in the contexts of logarithmic space and of logarithmic time computation. We show that logspace leaf languages yield a much finer classification scheme for complexity classes than polynomial time leaf languages, capturing also many classes within P. In contrast, logtime leaf languages basically behave like logtime reducibilities. Both cases are more subtle to handle than the polynomial time case. We also raise the issue of balanced versus non-balanced computation trees underlying the leaf language. We indicate that it is a non-trivial problem to obtain information about the leaf string of a non-balanced computation tree and present conditions under which it doesn't matter whether the computation tree is balanced or not.
Ulrich Hertrampf.
Complexity Classes with Finite Acceptance Types.
Proc. 11th Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 775, Springer Verlag, 1994, pp. 543-553.
Ulrich Hertrampf.
Complexity Classes Defined via k-Valued Functions.
Proc. 9th Structure in Complexity Theory Conference, 1994, pp. 224-234.
Ulrich Hertrampf.
Über Komplexitätsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden.
Habilitationsschrift, Universität Würzburg, 1994 (in deutsch).
Christos H. Papadimitriou.
Computational Complexity.
Addison Wesley, 1994, see pp. 504-505.
Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner.
On Balanced vs. Unbalanced Computation Trees.
Mathematical Systems Theory 29, 1996, pp. 411-421.
Abstract. A great number of complexity classes between P and PSPACE can be defined via leaf languages for computation trees of nondeterministic polynomial time machines. Jenner, McKenzie, and Therien (Proceedings of the 9th Conference on Structure in Complexity Theory, 1994) raised the issue of whether considering balanced or unbalanced trees makes any difference. For a number of leaf language classes, coincidence of both models was shown, but for the very prominent example of leaf language classes from the alternating logarithmic time hierarchy the question was left open. It was only proved that in the balanced case these classes exactly characterize the classes from the polynomial time hierarchy. Here, we show that balanced trees apparently make a difference: In the unbalanced case, a class from the logarithmic time hierarchy characterizes the corresponding class from the polynomial time hierarchy with a PP-oracle. Along the way, we get an interesting normal form for PP computations.
Katja Cronauer, Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner.
The Chain Method to Separate Counting Classes.
Theory of Computing Systems 31(1), 1998, pp. 93-108.
Abstract. We introduce a new method to separate counting classes of a special type by oracles. Among the classes, for which this method is applicable, are NP, coNP, US (also called 1-NP), ParityP and all other MOD-classes, PP and C=P, classes of Boolean Hierarchies over the named classes, classes of finite acceptance type, and many more. As an important special case, we completely characterize all relativizable inclusions between classes NP(k) from the Boolean Hierarchy over NP and other classes defined by what we will call bounded counting.
Helmut Veith.
Succinct Representation, Leaf Languages and Projection Reductions.
Information and Computation 142, 1998, pp. 207-236. Eine Vorabversion mit dem Titel "Succinct Representation and Leaf Languages" wurde präsentiert auf der 11th Annual IEEE Conference on Computational Complexity (CCC), 1996, pp. 118-126.
Abstract. 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 quantifier-free projection reductions from descriptive complexity theory. In particular, we show that the succinct upgrading technique can be improved to completeness under monotone projection reductions. Moreover, we show that for each problem A the succinct problem sA is complete for the leaf language leaf(A) under monotone projection reductions. Thus, we obtain a precise characterization of the complexity gap obtained by succinct representation. Furthermore, iterative application of the complexity upgrading technique becomes possible.
Hans-Jörg Burtschick, Heribert Vollmer.
Lindström Quantifiers and Leaf Language Definability.
International Journal of Foundations of Computer Science 9, 1998, pp. 277-294.
Abstract. We show that examinations of the expressive power of logical formulae enriched by Lindström quantifiers over ordered finite structures have a well-studied complexity-theoretic counterpart: the leaf language approach to define complexity classes. Model classes of formulae with Lindström quantifiers are nothing else than leaf language definable sets. Along the way we tighten the best up to now known leaf language characterization of the classes of the polynomial time hierarchy and give a new model-theoretic characterization of PSPACE.
Bernd Borchert, Antoni Lozano.
Succinct Circuit Representations and Leaf Language Classes are Basically the Same Concept.
Information Processing Letters 58, 1996, pp. 211-215.
Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson [GW83], and the topic of leaf language classes initiated by Bovet et al. [BCS92]. It will be shown for any language that its succinct version is polynomial-time many-one complete for the leaf language class determined by it.
Herve Caussinus, Pierre McKenzie, Denis Therien, Heribert Vollmer.
Nondeterministic NC1 Computation.
Journal of Computer and System Sciences 57, 1998, pp. 200-212.
Abstract. We define the counting classes #NC1, GapNC1, PNC1 and C=NC1. We prove that boolean circuits, algebraic circuits, programs over nondeterministic finite automata, and programs over constant integer matrices yield equivalent definitions of the latter three classes. We investigate closure properties. We observe that #NC1 subset #L and that C=NC1 subset L. Then we exploit our finite automaton model and extend the padding techniques used to investigate leaf languages. Finally, we draw some consequences from the resulting body of leaf language characterizations of complexity classes, including the unconditional separations of ACC0 from ModPH and that of TC0 from the counting hierarchy. Moreover we obtain that if dlogtime-uniformity and logspace-uniformity for AC0 coincide then the polynomial time hierarchy equals PSPACE.
Eric Allender.
The Permanent Requires Large Uniform Threshold Circuits.
Chicago Journal of Theoretical Computer Science, Article 7, 1999.
Abstract. A very recent paper by Caussinus, McKenzie, Therien, and Vollmer [CMTV] shows that ACC0 is properly contained in ModPH, and TC0 is properly contained in the counting hierarchy. Thus, [CMTV] shows that there are problems in ModPH that require superpolynomial-size uniform ACC0 circuits, and problems in the counting hierarchy that require superpolynomial-size uniform TC0 circuits. The proof in [CMTV] uses ``leaf languages'' as a tool in obtaining their separations, and their proof does not immediately yield larger lower bounds for the complexity of these problems. In this paper, we give a simple direct proof of these same separations, and use it to provide ``sub-subexponential'' size lower bounds on the size of uniform circuits for these problems.
Bernd Borchert, Dietrich Kuske, Frank Stephan.
On Existentially First-Order Definable Languages and their Relation to NP.
Theoretical Informatics and Applications 33, 1999, pp. 259-269.
Abstract. 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 if L is existentially but not quantifier-free definable in FO[<,min,max,-1,+1].
Bernd Borchert, Riccardo Silvestri.
Dot Operators.
Theoretical Computer Science 262(1), 2001, pp. 501-523.
Abstract. Well-known examples of dot-operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot-operator so that every language A will determine an operator A dot. In fact we will introduce the more general notion of promise dot-operators for which the BP-operator is an example. Dot-operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A dot P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot-operators. We show that two languages determine the same dot-operator if and only if they are reducible to each other by polylog-time uniform monotone projections.
Heribert Vollmer.
Relating polynomial time to constant depth.
Theoretial Computer Science 207, 1998, pp. 159-170
Abstract. Going back to the seminal paper [FSS84] by Furst, Saxe, and Sipser, analogues between polynomial time classes and constant depth circuit classes have been considered in a number of papers. Oracles separating polynomial time classes have been obtained by diagonalization making essential use of lower bounds for circuit classes. In this note we show how separating oracles can be obtained uniformly from circuit lower bounds without the need of carrying out a particular diagonalization. Our technical tool is the leaf language approach to the definition of complexity classes.
Sven Kosub, Heinz Schmitz, Heribert Vollmer.
Uniformly defining complexity classes of functions.
International Journal of Foundations of Computer Science 11(4), 2000, pp. 525-551.
Abstract. We introduce a general framework for the definition of function classes. Our model, which is based on polynomial time nondeterministic Turing transducers, allows uniform characterizations of FP, FPNP, counting classes (#P, #.NP, #.coNP, GapP, GapPNP), optimization classes (max.P, min.P, max.NP, min.NP), promise classes (NPSV, #few.P, c#.P), multivalued classes (FewFP, NPMV) and many more. Each such class is defined in our model by a scheme how to evaluate computation trees of nondeterministic machines. We study a reducibility notion between such evaluation schemes, which leads to a necessary and sufficient criterion for relativizable inclusion between function classes. As it turns out, this criterion is easily applicable and we get as a consequence, e.g., that there is an oracle A such that min.PA not subset #.NPA (note that no structural consequences are known to follow from the corresponding positive inclusion).
Heinz Schmitz, Klaus Wagner.
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy.
Technical Report No. 201, University of Würzburg, Department of Computer Science, 1998.
Matthias Galota.
Blattsprachen und endliche Automaten.
Technical Report No. 205, University of Würzburg, Department of Computer Science, 1998. .
Heribert Vollmer
Introduction to Circuit Complexity: A Uniform Approach.
Springer Verlag, 1999, see Sect. 6.2.
Heribert Vollmer.
Relating polynomial time to constant depth.
Theoretial Computer Science 207, 1998, pp. 159-170
Abstract. Going back to the seminal paper [FSS84] by Furst, Saxe, and Sipser, analogues between polynomial time classes and constant depth circuit classes have been considered in a number of papers. Oracles separating polynomial time classes have been obtained by diagonalization making essential use of lower bounds for circuit classes. In this note we show how separating oracles can be obtained uniformly from circuit lower bounds without the need of carrying out a particular diagonalization. Our technical tool is the leaf language approach to the definition of complexity classes.
Heribert Vollmer.
Generalized quantifiers in computational complexity theory.
In: Komplexität, Graphen und Automaten - Sammelband mit wissenschaftlichen Beiträgen, Gerd Wechsung zum 60. Geburtstag; 1999.
Abstract. A notion of generalized quantifier in computational complexity theory is developed and used to give a unified treatment of leaf language definability, oracle separations, type 2 operators, and circuits with monoidal gates. Relations to Lindström quantifiers are pointed out.
Heribert Vollmer.
Uniform characterizations of complexity classes.
ACM SIGACT-Newsletter 30(1), 1999, pp. 17-27.
Abstract. In the past few years, generalized operators (a.k.a. leaf languages) in the context of polynomial-time machines, and gates computing arbitrary groupoidal functions in the context of Boolean circuits, have raised much interest. We survey results from both areas, point out connections between them, and present relationships to a generalized quantifier concept from finite model theory.
Timo Peichl, Heribert Vollmer.
Finite automata with generalized acceptance criteria.
Discrete Mathematics and Theoretical Computer Science 4, 2001, pp. 179-192.
Abstract. We examine the power of nondeterministic finite automata with acceptance of an input word defined by a leaf language, i.e., a condition on the sequence of leaves in the automaton's computation tree. We study leaf languages either taken from one of the classes of the Chomsky hierarchy, or taken from a time- or space-bounded complexity class. We contrast the obtained results with those known for leaf languages for Turing machines and Boolean circuits.
Sven Kosub.
On NP-partitions over posets with an application to reducing the set of solutions of NP problems.
Proc. 25th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science Vol. 1893, 2000, pp. 467-476.
Abstract. The boolean hierarchy of k-partitions over NP for k at least 2 was introduced as a generalization of the well-known boolean hierarchy of sets. The classes of this hierarchy are exactly those classes of NP-partitions which are generated by finite labeled lattices. We refine the boolean hierarchy of NP-partitions by considering partition classes which are generated by finite labeled posets. Since we cannot prove it absolutely, we collect evidence for this refined boolean hierarchy to be strict. Based on the leaf language approach to define complexity classes, we are able to give an exhaustive answer to the question of which relativizable inclusions between partition classes can occur depending on the relation between their defining posets. The study of the refined boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the extended boolean hierarchy of k-partitions over NP is strict, we give a complete characterization when such solution reductions are possible.
Matthias Galota, Heribert Vollmer.
A generalization of the Büchi-Elgot-Trakhtenbrot theorem.
Proc. 15th Computer Science Logic 2001, Lecture Notes in Computer Science Vol. 2142, 2001, pp. 355-368.
Abstract. We consider the power of nondeterministic finite automata with generalized acceptance criteria and the corresponding logics. In particular, we examine the expressive power of monadic second-order logic enriched with monadic second-order generalized quantifiers for algebraic word-problems. Extending a well-known result by Büchi, Elgot, and Trakhtenbrot, we show that considering monoidal quantifiers, the obtained logic captures the class of regular languages. We also consider monadic second-order groupoidal quantifiers and show that these are powerful enough to define every language in LOGCFL.
Viktor L. Selivanov.
Relating automata-theoretic hierarchies to complexity-theoretic hierarchies.
Proc. 13th Fundamentals of Computation Theory 2001, Lecture Notes in Computer Science Vol. 2138, 2001, pp. 323-334.
Abstract. We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial hierarchy. This extends a result of H.-J. Burtschick and H. Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the boolean hierarchy and the plus-hierarchy.
Matthias Galota, Sven Kosub, Heribert Vollmer.
Generic Separations and Leaf Languages.
Mathematical Logic Quaterly 49(4), 2003, pp. 353--362.
Abstract. In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e.g., simultaneous separations and universal oracles, resource-bounded genericity, and type-2 complexity.
Matthias Galota, Heribert Vollmer.
Functions computable in polynomial space.
Electronic Colloquium on Computational Complexity,TR03-018, 2003.
Abstract. 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 that on input x outputs a 3x3 matrix with entries from {-1,0,1} on each of its paths such that f(x) is exactly the upper left entry in the product of all these matrices. This implies that the succinct version of this restricted form of matrix multiplication is complete for PSPACE under first-order projections. Along the way we obtain characterizations of FPSPACE in terms of arithmetic circuits and straight-line programs.