The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Bauland, Michael, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used....
The Complexity of Propositional Implication (2008)
Beyersdorff, Olaf, Meier, Arne, Thomas, Michael, Vollmer, Heribert
The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a...
The Complexity of Reasoning for Fragments of Default Logic (2008)
Beyersdorff, Olaf, Meier, Arne, Thomas, Michael, Vollmer, Heribert
Default logic was introduced by Reiter in 1980. In 1992, Gottlob classified the complexity of the extension existence problem for propositional default logic as SigmaP2-complete, and the complexity...
Extensional Uniformity for Boolean Circuits (2008)
McKenzie, Pierre, Thomas, Michael, Vollmer, Heribert
Imposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class L. By contrast, the usual intensional uniformity conditions...
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments (2008)
Bauland, Michael, Mundhenk, Martin, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries ⋆ (2008)
Michael Baul, Nadia Creignou, Miki Hermann, Heribert Vollmer
Abstract. Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more...
Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees (2008)
Bodo Manthey, Zur Erlangung Der, Bodo Manthey, Berichterstatter Prof, Dr. Rüdiger Reischuk, ...
the years. I also thank the current and former members of the Institut für Theoretische Informatik at the Universität zu Lübeck for many valuable discussions, not only about computer science. In...
Playing with Boolean blocks, part II: Constraint satisfaction problems (2008)
Elmar Böhler, Nadia Creignou, Steffen Reith, Heribert Vollmer
In the previous column we played with Boolean functions as “building blocks ” in the construction of switching circuits. In the meantime we got to know a child, having a great collection of...
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation ⋆ (2008)
Michael Baul, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer
Abstract. We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a...
Computational Complexity of Constraint Satisfaction (2008)
Abstract. The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate...
Heribert Vollmer, Theoretische Informatik
Abstract. In recent years generalized acceptance criteria for different nondeterministic computation models have been examined. Instead of the common definition where an input word is said to be...
Exploiting Practical Limitations of UML Diagrams for Model Validation and Execution (2008)
Friedrich Steimann, Lehrgebiet Programmiersysteme, Heribert Vollmer, ...
Abstract. We suggest a framework for UML diagram validation and execution that takes advantage of some of the practical restrictions induced by diagrammatic representations (as compared to Turing...
Michael Thomas, Prof Dr, Heribert Vollmer, Prof Dr, Kurt Schneider, Gottfried Wilhelm, ...
Hiermit versichere ich, dass ich die vorliegende Masterarbeit selbstständig verfasst und keine anderen Quellen und Hilfsmittel als die angegebenen
Hans-jörg Burtschick, Heribert Vollmer, Theoretische Informatik
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...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
The Complexity of Generalized Satisfiability forLinearTemporalLogic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
Lindstr om Quantifiers and Leaf Language Definability (2007)
Heribert Vollmer, Theoretische Informatik
D-97072 W urzburg We show that examinations of the expressive power of logical formulae enriched by Lindstrom quantifiers over ordered finite structures have a well-studied complexity-theoretic...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
On Balanced vs. Unbalanced Computation Trees (2007)
Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
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 Th'erien...
On the Power of Polynomial Time Bit-Reductions (Extended Abstract) (2007)
Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
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...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
Pierre Mckenzie, Thomas Schwentick, Heribert Vollmer
Abstract. First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic nite transducers (NFTs). It is shown here that this...
Todd Ebert, Wolfgang Merkle, Heribert Vollmer
Abstract. A binary sequence A = A(0)A(1) : : : is called i.o. Turingautoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs...
Generic separations and leaf languages (2007)
Matthias Galota, Matthias Galota, Sven Kosub, Sven Kosub, Heribert Vollmer, ...
Nachdruck auch auszugsweise verboten
Abstract A language A f0; 1g (2007)
is called i.o. autoreducible if A is Turing-reducible to itself via a machine M such that, for innitely many input words w, M does not query its oracle A about w. We examine the question if...
Pierre Mckenzie, Thomas Schwentick, Heribert Vollmer
Abstract. First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this...
Katja Cronauer, Ulrich Hertrampf, Abteilung Theoretische Informatik, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik, ...
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), \PhiP and all other...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
vollmerATthi.uni-hannover.de Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete,...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of...
06451 Executive Summary -- Circuits, Logic, and Games (2007)
Schwentick, Thomas, Thérien, Denis, Vollmer, Heribert
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.
06451 Abstracts Collection -- Circuits, Logic, and Games (2007)
Schwentick, Thomas, Thérien, Denis, Vollmer, Heribert
From 08.11.06 to 10.11.06, the Dagstuhl Seminar 06451 ``Circuits, Logic, and Games'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...
06401 Executive Summary -- Complexity of Constraints (2006)
Creignou, Nadia, Kolaitis, Phokion, Vollmer, Heribert
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.
06401 Abstracts Collection -- Complexity of Constraints (2006)
Creignou, Nadia, Kolaitis, Phokion, Vollmer, Heribert
From 01.10.06 to 06.10.06, the Dagstuhl Seminar 06401 ``Complexity of Constraints'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
Bases for Boolean co-clones (2005)
Elmar Böhler, Steffen Reith, Henning Schnoor, Heribert Vollmer
The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
Birgit Schelm, Doktorin Der Naturwissenschaften, Berichter Prof, Dr. Heribert Vollmer, Arfst Nickelsen, Ulf Niebling, ...
This thesis would not have been finished without the help of a number of people, and I would like to express my gratitude to all of them. Danilo Beuche,
The Complexity of Boolean Constraint Isomorphism (2003)
Böhler, Elmar, Hemaspaandra, Edith, Reith, Steffen, Vollmer, Heribert
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usually called Boolean...
Friedrich Steimann, Heribert Vollmer
Abstract. We suggest a framework for UML diagram validation and execution that takes advantage of some of UML’s restrictions (as compared to Turing equivalent programming languages) by exploiting...
Equivalence and Isomorphism for Boolean Constraint Satisfaction (2002)
Boehler, E., Hemaspaandra, E., Reith, Steffen, Vollmer, Heribert
A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fixed set B of Boolean functions. We consider the problem of...
Lecture Notes for Logic and Interaction (2002)
E. Böhler, H. Vollmer, Heribert Vollmer
Introduction Let B be a class of Boolean functions. By [B] we denote the class of all Boolean functions that can be obtained from functions from B by superposition, i.e., essentially arbitrary...
Partially-Ordered Two-Way Automata: A New Characterization of DA (2001)
Thomas Schwentick, Heribert Vollmer
Abstract. In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it. Equivalently we may assume that the states set is partially...
Partially-Ordered Two-Way Automata: A New Characterization of DA (2001)
Thomas Schwentick, Heribert Vollmer
In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it. This is equivalent to the property that the states set is partially...
On the Autoreducibility of Random Sequences (2001)
A language A ` f0; 1g is called i.o. autoreducible if A is Turing-reducible to itself via a machine M such that, for infinitely many input words w, M does not query its oracle A about w. We examine...
Generic Separations and Leaf Languages (2001)
Matthias Galota, Sven Kosub, H. Vollmer, Matthias Galota, Sven Kosub, Heribert Vollmer
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)...
Partially-ordered Two-way Automata: (2001)
New Characterization Of, Thomas Schwentick, Heribert Vollmer
In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it.
On the Autoreducibility of Random Sequences (2001)
Todd Ebert And, Todd Ebert, Heribert Vollmer
A language A f0; 1g is called i.o. autoreducible if A is Turing-reducible to itself via a machine M such that, for in nitely many input words w, M does not query its oracle A about w. We examine the...
Generic Separations and Leaf Languages (2001)
Matthias Galota, Sven Kosub, Heribert Vollmer
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)...
A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem (2001)
Matthias Galota, Heribert Vollmer
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...
Equivalence Problems for Boolean Constraint Satisfaction (2001)
E. Böhler, E. Hemaspaandra, S. Reith, H. Vollmer, Edith Hemaspaandra, Steffen Reith, ...
A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fi xed set C of Boolean functions. We consider the problem of...
Finite Automata with Generalized Acceptance Criteria (2001)
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....
Uniform characterizations of complexity classes of functions (2000)
Sven Kosub, Heinz Schmitz, Heribert Vollmer
We introduce a general framework for the denition of function classes. Our model, which is based on nondeterministic polynomial-time Turing transducers, allows uniform characterizations of FP, FP
A Polynomial-Time Approximation Scheme for Base Station Positioning in UMTS Networks (2000)
Matthias Galota, Christian Glaßer, Steffen Reith, Heribert Vollmer
We consider the following optimization problem for UMTS networks: For a specified teletraffic demand and possible base station locations, choose positions for base stations such that 1) the...
The Complexity of Base Station Positioning in Cellular Networks (2000)
Christian Glaßer, Steffen Reith, Heribert Vollmer, Theoretische Informatik
We consider two optimization problems for cellular telephone networks, that arise in a recently discussed ITU proposal for a traffic load model. These problems address the positioning of base...
The Many Faces of a Translation (2000)
Pierre Mckenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts...
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems (2000)
Steffen Reith, Heribert Vollmer
We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulas for different restricted classes of formulas. It turns out that for each...
The Complexity of Base Station Positioning in Cellular Networks (2000)
Christian Glaßer, Steffen Reith, Heribert Vollmer, Theoretische Informatik
We consider two optimization problems for cellular telephone networks, that arise in a recently discussed ITU proposal for a traffic load model. These problems address the positioning of base...
On the autoreducibility of random sequences (2000)
Todd Ebert, Wolfgang Merkle, Heribert Vollmer
Abstract. A binary sequence A = A(0)A(1)... is called infinitely often (i.o.) Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the...
The Many Faces of a Translation (2000)
Pierre Mckenzie, Thomas Schwentick, Denis Therien, Heribert Vollmer
First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic nite transducers (NFTs). It is shown here that this characterization lifts...
A Polynomial-Time Approximation Scheme for Base Station Positioning in UMTS Networks (2000)
Matthias Galota, Christian Glaßer, Steffen Reith, Heribert Vollmer
We consider the following optimization problem for UMTS networks: For a specified teletrac demand and possible base station locations, choose positions for base stations such that -- the construction...
On the autoreducibility of random sequences (2000)
Todd Ebert, Wolfgang Merkle, Heribert Vollmer
Abstract. A binary sequence A = A(0)A(1)... is called infinitely often (i.o.) Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the...
The many faces of a translation (2000)
Pierre Mckenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts...
Finite Automata with Generalized Acceptance Criteria. Januar (1999)
Timo Peichl, Heribert Vollmer, Theoretische Informatik, Am Hubl
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...
Finite Automata with Generalized Acceptance Criteria. Januar (1999)
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...
The Descriptive Complexity Approach to LOGCFL (1999)
Clemens Lautemann Pierre, Thomas Schwentick, Heribert Vollmer
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...
Arithmetic Circuits and Polynomial Replacement Systems (1999)
Pierre Mckenzie, Heribert Vollmer, Klaus W. Wagner
This paper addresses the problems of counting proof trees (as introduced by Venkateswaran and Tompa) and counting proof circuits, a related but seemingly more natural question. These problems lead to...
Approximation Algorithms for Cellular Network Optimization (1999)
Christian Glaer Steffen, Steffen Reith, Heribert Vollmer, Theoretische Informatik
We consider two optimization problems for cellular telephone networks with interferences, which address the positioning of base stations (on given locations) with the aim to maximize the number of...
Approximation Algorithms for Cellular Network Optimization (1999)
Christian Glaßer, Steffen Reith, Heribert Vollmer, Theoretische Informatik
We consider two optimization problems for cellular telephone networks with interferences, which address the positioning of base stations (on given locations) with the aim to maximize the number of...
Arithmetic Circuits and Polynomial Replacement Systems (1999)
Pierre Mckenzie, Heribert Vollmer, Klaus W. Wagner
This paper addresses the problems of counting proof trees (as introduced by Venkateswaran and Tompa) and counting proof circuits, a related but seemingly more natural question. These problems lead to...
A Note on Closure Properties of Logspace MOD Classes (1999)
Ulrich Hertrampf, Abteilung Theoretische Informatik, Steffen Reith, Heribert Vollmer, Theoretische Informatik
Introduction The classes MOD k L for k 2 consist of those languages A, for which there exists a nondeterministic Turing machine M working on logarithmically bounded space such that, for all inputs x,...
The Descriptive Complexity Approach to LOGCFL (1999)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...
Finite Automata with Generalized Acceptance Criteria (1999)
. We examine the power of nondeterministic finite automata with acceptance of an input word defined by a so called leaf language, i. e., a condition on the sequence of leaves in the automaton's...
A Note on Closure Properties of Logspace MOD Classes (1999)
Ulrich Hertrampf, Abteilung Theoretische Informatik, Steffen Reith, Heribert Vollmer, Theoretische Informatik
Introduction The classes MOD k L for k 2 consist of those languages A, for which there exists a nondeterministic Turing machine M working on logarithmically bounded space such that, for all inputs x,...
The Descriptive Complexity Approach to LOGCFL (1999)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
Building upon the known generalized-quanti er-based rst-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from...
Uniform Characterizations of Complexity Classes (1999)
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...
Arithmetic Circuits and Polynomial Replacement Systems (1999)
Pierre Mckenzie, Heribert Vollmer, Klaus W. Wagner
This paper addresses the problems of counting proof trees (as introduced by Venkateswaran and Tompa) and counting proof circuits, a related but seemingly more natural question. These problems lead to...
A Generalized Quantifier Concept in Computational Complexity Theory (1998)
A notion of generalized quantifier in computational complexity theory is explored and used to give a unified treatment of leaf language definability, oracle separations, type 2 operators, and...
The descriptive complexity approach to LOGCFL (1998)
Lautemann, Clemens, McKenzie, Pierre, Schwentick, Thomas, Vollmer, Heribert
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae (1998)
Reith, Steffen, Vollmer, Heribert
We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns out that for each...
The chain method to separate counting classes (1998)
Katja Cronauer, Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik, Theoretische Informatik, ...
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), \PhiP and all other...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (1998)
Manindra Agrawal Dept, Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
Lindström Quantifiers and Leaf Language Definability (1998)
Hans-Jörg Burtschick, Heribert Vollmer, Theoretische Informatik
We show that examinations of the expressive power of logical formulae enriched by Lindstrom quantifiers over ordered finite structures have a well-studied complexity-theoretic counterpart: the leaf...
Probabilistic Type-2 Operators and "Almost"-Classes (1998)
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner
We define and examine several probabilistic operators ranging over sets (i.e., operators of type 2), among them the formerly studied ALMOST-operator. We compare their power and prove that they all...
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae (1998)
Steffen Reith, Heribert Vollmer
We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns out that for each...
Relating Polynomial Time to Constant Depth (1998)
Heribert Vollmer, Theoretische Informatik
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...
Nondeterministic NC¹ computation (1998)
Hervé Caussinus, Pierre Mckenzie, Denis Thérien, Heribert Vollmer
We define the counting classes #NC 1 , GapNC 1 , PNC 1 and C=NC 1 . We prove that boolean circuits, algebraic circuits, programs over nondeterministic finite automata, and programs over constant...
Lindstr om Quantifiers and Leaf Language Definability (1998)
Hans-jorg Burtschick, Tu Berlin, Heribert Vollmer, Theoretische Informatik
We introduce second-order Lindstrom quantifiers and examine analogies to the concept of leaf language definability. The quantifier structure in a secondorder sentence defining a language and the...
Probabilistic Type-2 Operators and "Almost"-Classes (1998)
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner
. We define and examine several probabilistic operators ranging over sets (i.e., operators of type 2), among them the formerly studied ALMOST-operator. We compare their power and prove that they all...
Uniformly Defining Complexity Classes of Functions (1998)
Sven Kosub, Heinz Schmitz, Heribert Vollmer, Theoretische Informatik
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, FP...
Lindström Quantifiers and Leaf Language Definability (1998)
Hans-Jörg Burtschick, Tu Berlin, Heribert Vollmer, Theoretische Informatik
We introduce second-order Lindstrom quantifiers and examine analogies to the concept of leaf language definability. The quantifier structure in a secondorder sentence defining a language and the...
Generalized Quantifiers in Computational Complexity Theory (1998)
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...
Gap-Languages and Log-Time Complexity Classes (1997)
Kenneth W. Regan, Heribert Vollmer
This paper shows that classical results about complexity classes involving "delayed diagonalization" and "gap languages," such as Ladner's Theorem and Schoning's Theorem...
Succinct Inputs, Lindström Quantifiers, and a General Complexity Theoretic Operator Concept (1997)
Heribert Vollmer, Theoretische Informatik
We address the question of the power of several logics with Lindstrom quantifiers over finite ordered structures. We will see that in the first-order case this nicely fits into the framework of...
On Operators of Higher Types (1997)
Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
We discuss the use of operators of higher types in complexity theory. These are operators ranging over sets of words, i. e. over oracles. Depending on different oracle access mechanisms we consider...
Gap-Languages and Log-Time Complexity Classes (1997)
Kenneth W. Regan, Heribert Vollmer
This paper shows that classical results about complexity classes involving "delayed diagonalization" and "gap languages," such as Ladner's Theorem and Schoning's Theorem...
Measure One Results In Computational Complexity Theory (1997)
Heribert Vollmer, Klaus W. Wagner
This paper is dedicated to Ronald V. Book on the occasion of his 60th birthday.
Complements of multivalued functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it...
Complements of multivalued functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
Universitat Wurzburg We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of...
Complements of multivalued functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
Universitat Wurzburg We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of...
Succinct Inputs, Lindstrom Quantifiers, and a General Complexity Theoretic Operator Concept (1996)
Heribert Vollmer, Theoretische Informatik
We address the question of the power of several logics with Lindstrom quantifiers over finite ordered structures. We will see that in the first-order case this nicely fits into the framework of...
Complements of multivalued functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
Wurzburg We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing...
Relations among parallel and sequential computation models (1996)
Abstract. This paper relates uniform small-depth circuit families as a parallel computation model with the complexity of polynomial time Turing machines. Among the consequences we obtain are: (a) a...
Classes of Counting Functions and Complexity Theoretic Operators (1996)
Heribert Vollmer, Klaus W. Wagner
Introduction Most of the naturally arising classes in structural complexity theory, like P, NP, PP, all the other classes of the polynomial time hierarchy and the counting hierarchy, UP, XP...
Complements of Multivalued Functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it...
Complements of Multivalued Functions (1996)
Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it...
Complexity Classes of Optimization Functions (1995)
Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
In this paper, complexity classes of functions defined via taking maxima or minima (cf. the work of Krentel) or taking middle elements (cf. the work of Toda) are examined. A number of axioms for a...
On the Power of Number-Theoretic Operations with Respect to Counting (1995)
Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
We investigate function classes h#Pi f which are defined as the closure of #P under the operation f and a set of known closure properties of #P, e.g. summation over an exponential range. First, we...
The Satanic Notations: Counting Classes Beyond #P and Other Definitional Adventures (1994)
Hemaspaandra, Lane A., Vollmer, Heribert
We explore the potentially ``off-by-one'' nature of the definitions of counting (#P versus #NP), difference (DP versus DNP), and unambiguous (UP versus UNP; FewP versus FewNP) classes, and make...
Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages (1994)
Bernd Borchert, Gutachter Prof, Dr. Klaus Ambos-spies, Thomas Schwentick, ...
this paper were shown in the preceeding Chapters 3 and 4. In this chapter some other models of nondeterministic computation will be considered. For each model the notion of a predicate class is...
The Satanic Notations: Counting Classes Beyond #P and Other Definitional Adventures (1994)
Lane A. Hemaspaandra, Heribert Vollmer
We explore the potentially "off-by-one" nature of the definitions of counting (#P versus #NP), difference (DP versus DNP), and unambiguous (UP versus UNP; FewP versus FewNP) classes, and...
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions (1994)
Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik
There has been a great effort in giving machine independent, algebraic characterizations of complexity classes, especially of functions. Astonishingly, no satisfactory characterization of the...
Komplexitätsklassen von Funktionen / (1994)
Würzburg, Universiẗat, Diss., 1994.
On the Power of Polynomial Bit-Reductions (1993)
Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner
We examine the notion of definability of complexity classes via leaf languages, introduced by Bovet, Crescenzi and Silvestri (Theoretical Computer Science 104 (1992), 263--283). For a...
On the Power of Polynomial Bit-Reductions (1993)
Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner
We examine the notion of definability of complexity classes via leaf languages, introduced by Bovet, Crescenzi and Silvestri (Theoretical Computer Science 104 (1992), 263--283). For a...
On Different Reducibility Notions for Function Classes (1993)
. This paper continues research of Toda (The Complexity of Finding Medians, 31 st Symposium on Foundations of Computer Science (1990), pp. 778--787) on problems complete for function classes like FP...
The Complexity Of Finding Middle Elements (1993)
Heribert Vollmer, Klaus W. Wagner
Seinosuke Toda introduced the class MidP of functions that yield the middle element in the set of output values over all paths of nondeterministic polynomial time Turing machines. We define two...