Peter Clote
Professor im Institut für Informatik an der
Ludwig-Maximilians-Univerität München
Address
Lehrstuhl für Theoretische Informatik
Institut für Informatik
Ludwig-Maximilians-Universität München
Oettingenstr. 67
D-80538 München
Email: clote@informatik.uni-muenchen.de
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
-
RegularLanguagePermutations
-
Institut
Universität
Peter Clote, clote@informatik.uni-muenchen.de