 |
Eberhard Karls Universität Tübingen Wilhelm-Schickard-Institut für Informatik (WSI) Arbeitsbereich für Theoretische Informatik/Formale Sprachen |
|
Eberhard Karls Universität Tübingen Wilhelm-Schickard-Institut für Informatik (WSI) Arbeitsbereich für Theoretische Informatik/Formale Sprachen |
Bernd Borchert
Department of Computer Science, University of Tuebingen, Germany| Address: | Sand
13, D-72076 Tuebingen, Room B116 |
| Email: | borchert
at informatik dot
uni-tuebingen dot de |
| Phone: | +49-7071-29-74036 |
| Mobile: | +49-175-4142431 |
| Office
Hours |
Wed 9-12 |
Research group Trojan-proof Online Accounts.
submitted.
to be submitted.
to be submitted.
LATA 2007
Abstract. Like the sequence of the classes of the dot-depth hierarchy the sequence of classes given by the n-fold iterated block product of DA has the class of starfree regular languages as its limit. It is shown that this DA-block-product hierarchy grows more slowly than the dot-depth hierarchy: in fact already Sigma-2 of the dot-depth hierarchy contains properness witnesses for all levels of the DA-block-product hierarchy.
to be submitted.
Abstract. The temporal logic operators atnext and atprevious are alternatives for the operators until and since. P atnext Q has the meaning: at the next position in the future where Q holds it holds P. We define an asymmetric but natural notion of depth for the expressions of this linear temporal logic. The sequence of classes at_n of languages expressible via such depth-n expressions gives a parametrization of the starfree regular languages which we call the atnext/atprevious hierarchy, or simply at hierarchy. It turns out that the at hierarchy equals the hierarchy given by the n-fold weakly iterated block product of DA. It is shown that the at hierarchy is situated properly between the until/since and the dot-depth hierarchy.
to be submitted.
Abstract. As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for constant w≥1, the corresponding search problem for such a path of length k in a given graph is NP-complete and fixed-parameter tractable in the parameter k, like this is known for the special case w=1, the LONGEST PATH problem. We state the FPT algorithm in terms of a guess and check protocol which uses witnesses of size polynomial in the parameter.
SOFSEM
06, LNCS 3831, 187-196
Abstract. It is well-known that the Sigma_k and Pi_k levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. We extend this correspondence to the Delta_k levels of these hierarchies: Leaf^P(Delta^L_k) = Delta^p_k. The same methods are used to give evidence against an earlier conjecture of Straubing and Thérien about a leaf-language upper bound for BPP.
International Journal of Foundations of Computer Science 16 (2005), 625-644
Abstract. Based on the notions of locality and recognizability for n-dimensional languages n-dimensionally colorable 1-dimensional languages are introduced. It is shown: A language L is in NP if and only if L is n-dimensionally colorable for some n. An analogous characterization in terms of deterministic n-dimensional colorability is obtained for P. The addition of one unbounded dimension for coloring leads to a characterization of PSPACE.
submitted.
Abstract. We show that given two Boolean circuits f and g the following three problems are Sigma^p_2-complete: (1) Is f a c-subfunction of g, i.e. can one set some of the variables of g to 0 or 1 so that the remaining circuit computes the same function as f? (2) Is f a v-subfunction of g, i.e. can one change the names of the variables of g so that the resulting circuit computes the same function as f? (3) Is f a cv-subfunction of g, i.e.\ can one set some variables of g to 0 or 1 and simultanously change some names of the other variables of g so that the new circuit computes the same function as f?
Unpublished manuscript
Abstract. Its maximal number of mind changes is a natural invariant of a Boolean function, this notion is studied and applied - under different names - in hardware design, computational complexity and cryptography. In this note it is shown that for each fixed k>1 the computational problem "Given a Boolean circuit f, is k the maximal number of mind changes of the Boolean function computed by f ?" is complete for the class DP of the Boolean Hierarchy over NP. If k is part of the input the corresponding problem is Theta^p_2 complete.
Unpublished manuscript
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 computable monotone projections.
Theoretical Computer Science 262 (2001), 501-523
Abstract. Rice's Theorem says that every nontrivial semantic property of programs is undecidable. In this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [Yap 1983] we show a perfect analogue of Rice's Theorem.
Mathematical Logic Quaterly 46 (2000), 489-504
Abstract. One way of suggesting that an NP problem may not be NP-complete is to show that it is in the promise class UP. We suggest an analogous new approach - weaker in strength of evidence but more broadly applicable - to suggesting that concrete NP problems are not NP-complete. In particular we introduce the class EP, the subclass of NP consisting of those languages accepted by NP machines that when they accept always have a number of accepting paths that is a power of two. We show that FewP, bounded ambiguity polynomial time (which contains UP), is contained in EP. The class EP applies as an upper bound to some concrete problems to which previous approaches have never been successful, for example the negation equivalence problem for OBDDs (ordered binary decision diagrams).
LMS Journal of Computation and Mathematics 3 (2000), 86-95
Abstract. Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals NP iff L is existentially but not quantifierfree definable in FO[<,min,max,-1,+1]. Furthermore, no such class lies properly between NP and co-1-NP or NP join co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.
Theoretical Informatics and Applications 33 (1999) 259-269
Abstract. The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions, one of them is the Boolean isomorphism relation. Most of these computational problems turn out to be between co-NP and Sigma-p-2.
Theory of Computing Systems 31 (1998) 679-693
Abstract. Bovet, Crescenzi, and Silvestri (1992,1995), and independently Vereshchagin (1994), 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.
Information Processing Letters 63 (1997) 153-158
Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson (1983), and the topic of leaf language classes initiated by Bovet et al. (1992). 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.
Information Processing Letters 59 (1996) 211-215
Abstract. Hertrampf et al. (1993) 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 MOD_pP 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.
Theoretical Computer Science 148 (1995) 207-225
Clubs and Societies I'm a member of.
