# Oberseminar Theoretische Informatik WS 02/03

### Mittwochs um 14:00 Uhr s.t., Raum 03.11.018

[Zusammenfassung des nächsten Vortrags vom 21.01.03]

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
 Mihyun Kang, HU Berlin Generating random planar graphs …
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.

 Letzte Änderung: Moritz Maaß am 15.01.2003