 Fr,25.10.2002
|
Pierre McKenzie, DIRO, Université de Montréal
The complexity of evaluating circuits over the natural numbers
|
|
We will examine the complexity of evaluating circuits and formulas
when the operators are plus and times, together with the set operations (where,
for example, the sum of two sets is defined as the set comprising all the sums
of one number from the first set and one number from the second set). We will
see that restrictions of this problem defined by restricting the available
operators are complete for a wide range of complexity classes, ranging from
NEXPTIME down to classes well below P. This is joint work with Klaus Wagner
from Würzburg.
|
|
|
Mi,27.11.2002
|
Michal Mnuk
Über eine algebraische Beschreibung der Färbbarkeit planarer Graphen
|
|
Im Vortrag wird eine idealtheoretische
Formulierung des Beweises des Vier-Farben
Satzes präsentiert. Die Verbindung zwischen
Graphtheorie und Polynomidealen liefert eine
alternative Sichtweise auf das Problem der
Färbbarkeit, die zum besseren Verständnis der
auftretenden Phänomene führen könnte.
|
|
|
Mi,4.12.2002
|
|
|
Mi,11.12.2002
|
Klaus Holzapfel
Google & Co
|
|
Dieser Vortrag soll einen Einblick in die Grundideen von text-
und linkbasierten Suchmaschinen geben. Neben den theoretischen
Grundlagen werden auch praktische Aspekte wie Datenerhebung,
Spaming und Gruppierung beleuchtet.
|
|
|
Mi,18.12.2002
|
Markus Holzer und Barbara
König
On Deterministic Finite Automata and Syntactic Monoid Size
|
|
We investigate the relationship between regular languages and
syntactic monoid size. In particular, we consider the transformation
monoid of $n$-state (minimal) deterministic finite automata. We show
tight upper bounds on the syntactic monoid size, proving that an
$n$-state deterministic finite automata with singleton input
alphabet (input alphabet with at least three letters, \resp) induces
a linear ($n^n$, \resp) size syntactic monoid. In case of two letter
input alphabet, we can show a lower bound of $n^n-{n\choose
\ell}\ell!n^k-{n\choose \ell}k^k\ell^\ell$, for some natural
numbers~$k$ and~$\ell$ close to $\frac{n}{2}$, for the size of the
syntactic monoid of a language accepted by an $n$-state
deterministic finite automaton. This induces a family of
deterministic finite automata such that the fraction of the size of
the induced syntactic monoid and~$n^n$ tends to~$1$ as~$n$ goes to
infinity.
|
|
|
Mi,15.1.2003
|
Moritz Maaß
k-Characteristic Strings
|
|
The \CSP is defined as follows. Given a set $S$ of strings and a
non-empty set $T \subsetneq S$, find a shortest string $u$, s.t. $u$
is a substring of all strings in $T$ and $u$ is not a substring of
any string in $S \setminus T$.
The \ICSP is an extension of the \CSP, where we allow $k$ errors
when trying to match strings from $S \setminus T$.
The problem is motivated by applications in computational
biology, in particular in probe design and DNA
sequencing with a technique called ``chromosome walking''.
We present a new algorithm to solve the \ICSP using Hamming distance
as a measure. We embed our new algorithm and
the previously known algorithm for Levenshtein distance (by Ito et
al. 1994) in a common framework which reveals an additional
improvement to the Levenshtein distance algorithm.
The \ICSP can thus be solved in time \moof{||T|| + l\cdot||S
\setminus T||} for Hamming distance and in time \moof{||T|| +
k\cdot{}l\cdot{}||S\setminus{}T||} for Levenshtein distance, where $S
\subseteq \Sigma^*$, $T \subsetneq S$ ($T\neq\emptyset$) is the
target set (with $||T||$ being the size of all strings in $T$), and
$l$ is the length of a shortest string in $T$.
Both algorithms need to solve the \CSubSP for more than two
strings. We present an improved algorithm for this problem being
simpler and faster in practice by a constant factor than the
previous algorithm by Hui (1992).
|
|
|
Di,21.1.2003, 13:15 Uhr
|
Matthew Devos (Princeton Univ.)
A Kneser's critical problem
|
|
In 1953 Martin Kneser proved the following theorem for every additive
abelian group G. If A,B are finite nonempty subsets of G, then either
|A+B| > |A| + |B| - 2 or there exists an element g so that A+B+g = A+B.
Shortly afterward he posed the problem of characterizing those sets A,B
for which |A+B| < |A| + |B|. In this talk we give a solution to Kneser's
problem, and we discuss the relationship between this area of additive
number theory and some unsolved problems in graph theory and
combinatorics.
|
|
|
