 Mi,6.12.2000
|
Stefan Schwoon
Ein Modelchecker für rekursive Programme
|
|
Pushdown-Systeme können als ein Modell
für sequentielle Programme mit (rekursiven) Prozeduren betrachtet
werden. In meinem letztjährigen Vortrag wurden effiziente
Algorithmen zur Analyse von Pushdown-Systemen vorgestellt, die die
Grundlage eines Modelcheckers für besagte Programme sind. Der
Modelchecker benutzt eine Mischung von Operationen auf
Pushdown-Systemen und Binary Decision Diagrams (BDDs), um
Kontrollfluß bzw. Variablenübergänge effizient
darzustellen. Es werden einige Beispiele gezeigt und vorläufige Ergebnisse präsentiert.
|
|
|
Mi,13.12.2000
|
Jens Ernst
A Spectral Approach to Clustering Gene Expression Profiles
|
|
Modern DNA microarray-based methods of gene
expression profiling have advanced to the point where the simultaneous
monitoring of tens of thousands of genes has become feasible. Studying
gene expression levels in genomic-scale timecourse experiments may
yield valuable information on gene function. But at the same time this
induces hard computational problems, cluster analysis on
noise-contaminated data being among the most prominent. We present an
$\tilde{O}(n^2)$-algorithm for clustering objects non-hierarchically
by their pairwise similarity, along with a complete probabilistic analysis.
|
|
|
Mi,24.1.2001
|
Markus Holzer
The Complexity of Tensor Calculus
|
|
Tensor calculus over semirings is shown
relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas
with explicit tensor entries is shown complete for $\oplus\P$, for
$\NP$, and for $\#\P$ as the semiring varies. Indeed the permanent of
a matrix is shown expressible as the value of a tensor formula in much
the same way that Berkowitz' theorem expresses its determinant.
Second, restricted tensor formulas are shown to capture the classes
$\LOGCFL$ and $\NL$, their parity counterparts $\oplus\LOGCFL$ and
$\oplus\L$, and several other counting classes. Finally, the known
inclusions $\NP/\poly \subseteq \oplus\P/\poly$, $\LOGCFL/\poly
\subseteq \oplus\LOGCFL/\poly$, and $\NL/\poly \subseteq
\oplus\L/\poly$, which have scattered proofs in the literature
(Valiant \& Vazirani 1986; G{\'a}l \& Wigderson 1996), are shown to
follow from the new characterizations in a single blow. As an
intermediate tool, we define and make use of the natural notion of an
algebraic Turing machine over a semiring $\mathcal{S}$.
|
|
Mi,31.1.2001
10:00
|
Sven Kosub
(Universität Würzburg)
Komplexität von Partitionen
|
|
Die klassische Komplexitätstheorie
untersucht in erster Linie die Komplexität von Mengen, d.h. von Zerlegungen (Partitionen) einer
Grundmenge in zwei Teile. Häufig werden aber natürliche
Fragestellungen viel angemessener durch Zerlegungen in mehr als zwei Teile
abgebildet. Eine besonders interessante Klasse solcher Fragestellungen sind
Klassifikationsprobleme für Relationen. Zum Beispiel definiert eine
Binärrelation R typischerweise eine Zerlegung der Menge aller Paare (x,y)
in vier Teile, klassifizierbar danach, ob R(x,y) und R(y,x), R(x,y) aber nicht
R(y,x), nicht R(x,y) aber dafür R(y,x) oder weder R(x,y) noch R(y,x)
gilt. Anhand von Klassifikationsproblemen für konkrete Relationen, wie der
Einbettbarkeit von Graphen und der (Nicht-)Folgerbarkeit für
aussagenlogische Formeln, werden im Vortrag Instrumente für eine
qualitative Analyse der Komplexität von Partitionen, die von NP-Relationen
erzeugt werden, in Form der Booleschen Hierarchie der NP-Partitionen und ihrer
Erweiterungen vorgestellt.
|
|
Fr,2.2.2001
10:00
|
|
|
Mi,7.2.2001
|
Martin Kutrib (Universtität Giessen)
Zeit, Dimension, Nichtdeterminismus:
Hierarchien zwischen Real- und Linearzeit
|
Viele Ergebnisse für Turingmaschinen mit höchstens linearer
Zeitbeschränkung stammen aus den Anfangszeiten der
Komplexitätstheorie. Während für fast alle nichtdeterministischen
Modelle und deterministische Einband-Maschinen bekannt ist, daß die
Realzeit- und Linearzeitklassen zusammenfallen, ergeben sich
signifikante Unterschiede für deterministische Maschinen mit
mindestens zwei Bändern: Hier sind die Realzeitklassen jeweils echt
in den Linearzeitklassen enthalten.
Für den Bereich dazwischen liefern die Zeithierarchiesätze keine
Antwort. Z.B.\ ist für $k$-Band-Turingmaschinen die echte Inklusion
$\dtime_k(t_1)\subset \dtime_k(t_2)$ bekannt, sofern $k\geq 2$,
$t_1\in o(t_2)$ und $t_2$ zeitkonstruierbar sind. (Für
Mehrband-Maschinen muß $t_1\cdot \log(t_1) \in o(t_2)$ gelten.) Die
Hierarchiebedingung $t_1\in o(t_2)$ wird aber aufgrund der
Möglichkeit zur linearen Beschleunigung zur
kleinst\-mög\-lich\-en. Es gilt bekanntlich
$\dtime(t)=\dtime(Lin(t))$ für Mehrband- und $k$-Band-Maschinen,
sofern $t\geq c\cdot n$ mit $c>1$ ist. Andererseits sind damit wegen
der Bedingung $c>1$ ebenfalls keine Aussagen über den Bereich
zwischen Real- und Linearzeit möglich.
Im Vortrag werden Zeitschranken der Form $n+r(n)$ mit sublinearen
Abbildungen $r$ betrachtet.
Für alle Dimensionen $d\in\N$ existiert eine unendliche, echte
Zeithierarchie über die $r$. Andererseits läßt sich für alle $r$
zwischen $1$ und $n^{\frac{1}{d}}$ eine echte Hierarchie über die
Dimensionen zeigen.
Als dritte Ressource neben Zeit und Dimension wird schließlich der
Grad des Nichtdeterminismus behandelt. Die bekannte
Realzeit-Hierarchie über die Anzahl der zulässigen
nichtdeterministischen Schritte wird auf beliebige Dimensionen
erweitert. Für einen fixierten Grad des Nichtdeterminismus zwischen
$1$ und $\log(n)$ existiert auch in diesem Fall eine echte Hierarchie
über die Dimensionen.
Das Verhältnis zwischen den Zeitschranken und dem Grad des
Nichtdeterminismus kann insofern gelöst werden, daß eine Hierarchie
über den Nichtdeterminismus für jedes $r$ zwischen $1$ und
$n^{\frac{1}{2}}$ nachgewiesen wird.
|
|
|
Mi,22.7.1998
|
Martin Beaudry
(Université Sherbrooke, Quebec, Canada)
Computing with groupoids and loops
|
|
Groupoids are unrestricted binary algebras. The subclass of
associative algebras (semigroups and monoids) has been extensively
studied; finite semigroups recognize exactly the regular languages.
For at least a decade it has been known that finite groupoids
recognize exactly the context-free languages; we survey research which
has been aimed at finding which languages are recognized by some
significant subclasses of groupoids. We concentrate in particular on
loops, which can be seen as the non-associative counterpart to groups:
they are defined in the same way, except that we lift the constraint
that the operation be associative; loops recognize exactly those
regular languages which are open for the Hall topology.
|
|
|
