Peter Clote

Professor im Institut für Informatik an der Ludwig-Maximilians-Univerität München


Lehrstuhl für Theoretische Informatik
Institut für Informatik
Ludwig-Maximilians-Universität München
Oettingenstr. 67
D-80538 München
Tel: +49 89 2178 2241, Fax: +49 89 2178 2238

Recent papers

How optimal is the genetic code?, with S. Schönauer.
Computer Science and Biology, Proceedings of the German Conference on Bioinformatics (GCB'97), pp. 65--67, eds. D. Frishman and H.W. Mewes, Sep 21--24, 1997.
Extending work of Haig-Hurst on optimality of the natural genetic code, in this paper we use Monte-Carlo (with simulated annealing) to consider general (rather than block-structured or codon-shuffle) codes and study the optimality of natural genetic code is with respect to fault tolerance using the WAC similarity matrix of Wei-Altman-Chang (amino acid microenvironments in 1 Angstrom shells).
A safe recursion scheme for exponential time.
Logical Foundations of Computer Science (LFCS'97), Fourth International Symposium, Yaroslavl (Russia), 4--15 July 1997, Springer Lecture Notes in Computer Science 1234, pp. 44--52 eds. S.~Adian and A.~Nerode (1997).
Using a function algebra characterization of exponential time due to Monien, in the style of Bellantoni-Cook, we characterize exponential time functions of linear growth via a safe course-of-values recursion scheme.
On PHP, st-connectivity and odd charged graphs , with A. Setzer.
Proof Complexity and Feasible Arithmetics, 93--118, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 39, eds. Paul W. Beame and Samuel R. Buss, 1998.
W. Degen showed that for m fixed, over ZF set theory without the axiom of choice, a set theoretic analogue of the statement D(m,k) is properly weaker than D(m+1,k), where D(m,k) states that any mapping from a domain of size mk+1 into a range of size k must have a subset of size at least m+1 mapped to the same image. The pigeonhole principle, Ajtai's parity principle, and various modular counting principles have been investigated in boolean circuit complexity and in propositional proof theory, the idea being that counting is a difficult notion to capture in finite depth circuits or proofs. In this paper, we establish that Degen's principle is of the same strength as the pigeonhole principle, then consider a propositional logic formulation of st-connectivity, and using the Karchmer-Wigderson lower bound for monotonic fan-in 2 circuits, furnish an example where tree-like resolution is weaker than resolution. Finally, we prove some fragmentary results concerned with Tseitin's odd-charged graph tautologies, and with a monotonic polynomial calculus for monotonic Gentzen sequent calculus.
Evolution as a computational engine with Rolf Backofen.
Computer Science Logic, Aarhus (Denmark), Aug 25--29, 1997.
Consider the following problem. Given a finite set K of lethal genes, a starting genome x and a desired target gene y, is there a sequence of base insertions, deletions, and substitutions, which from x produces a genome z which contains the desired gene y, and such that no intermediate genome contains a lethal gene. The main result of this paper is that, appropriately formulated, this problem is undecidable, even when the underlying alphabet has only 2 symbols (e.g. two of the bases A,C,G,T). The proof yields that for any Turing machine M, there is a finite set K of lethal genes, which can guide the computation, in the sense that all intermediate genomes are prefixes of configurations in the computation of M. From this perspective, evolution can be seen as a computational engine.
Nondeterministic stack register machines.
Nondeterministic stack register machines Theoretical Computer Science, 178 (June 1997) 37-76. (To appear in Theoretical Computer Science )
A stack register machine, introduced by Bel'tyukov in 1979, allows branching instructions, assignments to the work register R, and incremental instructions of the form t_i := t_i + 1, which add 1 to a stack register AND simultaneously set to 0 all stack registers t_j of smaller index j < i. This paper investigates nondeterministic stack register machines, and shows that in most cases, nondeterminism provides no additional strength.
A note on the relation between polynomial time functionals and Constable's class K
Computer Science Logic, Springer Lecture Notes in Computer Science 1092, ed. Hans Kleine-Büning, 145--160 (1996).
In 1973 Constable defined K(f) to be the smallest class of functions containing certain initial functions including f, and closed under the operations of substitution, explicit transformation, length bounded addition and length bounded multiplication. It was claimed that for nondecreasing f, K(f) = L(f), the collection of functions polytime computable in f. This paper presents a counterexample to the claim.
Cutting planes, connectivity, and threshold logic
(with S.R. Buss, in Archive of Mathematical Logic {\bf 121}(1), 33--62 1995.)
Originating from work in operations research the cutting plane refutation system CP is an extension of resolution. Polynomial size CP proofs are given for the undirected s-t connectivity principle. The subsystems CP_q of CP, for q > 1, are shown to be polynomially equivalent to CP. A normal form theorem for CP_2-proofs and thereby for arbitrary CP-proofs is presented. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extension CPLE+ is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.
Computation models and function algebras
Survey of sequential, parallel and circuit complexity classes, and machine-independent characterizations of those classes using function algebras. In addition to bounded recursion schemes, unbounded tiering schemes and higher type recursion is included.

Program to generate invariance groups for regular languages


Institut          Universität
Peter Clote,