 Mi,11.11.1998
|
Richard Mayr
Lossy Counter Machines
|
We consider lossy counter machines, i.e. counter machines
with counters whose contents can spontaneously decrease
at any time. They are not Turing-powerful, since reachability
is decidable for them, but they still have interesting undecidable
properties: For a lossy counter machine it is undecidable if
there exists an initial configuration s.t. there is an infinite run.
Lossy counter machines can be used as a general tool to show the
undecidability of many problems for lossy and non-lossy systems,
e.g. verification of lossy FIFO-channel systems, model checking
lossy Petri nets, problems for reset and transfer Petri nets,
and parametric problems like fairness of broadcast communication
protocols.
|
|
|
Mi,18.11.1998
|
Tony Kucera
Weak Bisimilarity with Infinite-State
Systems Can be Decidable in Polynomial Time
|
|
We prove that weak bisimilarity between BPA and finite-state
processes, and between normed BPP and finite-state processes is
decidable in polynomial time. To the best of our knowledge, it is
the first result on tractability of weak bisimilarity with infinite-state
systems. Possible practical use and further applicability will also
be discussed.
|
|
|
Mi,25.11.1998
|
Thomas Schickinger
Lastbalancierung mittels Bisektionen - eine scharfe Average-Case-Analyse
|
Bei rechenintensiven Anwendungen, z. B. im Bereich der Numerik, besteht
zuweilen die Möglichkeit, ein großes Problem mittels eines
Bisektions-Verfahrens in zwei kleinere Probleme zu zerteilen. Auf diese Weise
kann das ursprüngliche Problem durch N-1 Bisektionen auf
N Maschinen verteilt werden.
Um die Gesamtlaufzeit zu minimieren, sollte ein Verfahren, das diese Zerlegung
durchführt, möglichst gleichgroße Teilprobleme erzeugen. Eine naheliegende
Strategie besteht hierbei darin, das Bisektionsverfahren auf das größte
bislang generierte Teilproblem anzuwenden (Heaviest-First-Algorithmus oder
HF-Algorithmus). Wir zeigen, daß der HF-Algorithmus im Mittel sehr gute
Ergebnisse liefert, die sich nur um einen Faktor zwei vom theoretischen
Optimum unterscheiden.
Dazu modellieren wir das Bisektionsverfahren durch die Gleichverteilung,
d. h. ein Problem mit Gewicht w wird in zwei Probleme mit
Gewicht a w
und (1 - a)w zerteilt, wobei a auf [0,1] gleichverteilt sei.
An der von uns durchgeführten Analyse ist bemerkenswert, daß die theoretischen
Resultate sehr genau mit Ergebnissen von Simulationen übereinstimmen und
deshalb die Leistungsfähigkeit des HF-Algorithmus deutlich wiederspiegeln.
|
|
|
Mi,2.12.1998
|
Anca Muscholl (Universität Stuttgart)
Verifying races and confluence of message sequence graphs
|
Message sequence charts (MSCs) are often used in the specification of
communication protocols. Syntactically they can be composed to message
sequence graphs, which allow nondeterministic branching, composition
and iteration. Depending on the implementation, MSCs have an
associated semantics which yields partial orders corresponding to
Mazurkiewicz (semi-) traces.
We consider two basic verification problems for MSC graphs, the race
problem and the confluence problem. Both problems are shown to be
undecidable. However, they become tractable if we restrict the iteration
operation. In the trace setting we show that the universality problem
for loop-connected automata is EXPSPACE-complete. This implies
the same complexity bounds for the race and the confluence
problem for restricted MSC graphs.
|
|
|
Di,8.12.1998
|
Yuri Matiyasevich (Steklov Institute of Mathematics, St. Petersburg)
Window-Accumulation Subsequence Problem
|
The problem of the title is stated as follows. Given an alphabet and
two words in it, a "text" and a "pattern", and a number w called
"window size",
we are interested to calculate the number of "windows", that is factors of the
text, of the length w from which the pattern can be obtained by deleting
some letters.
Two algorithms are proposed for this problem running on-line on the text
after some pre-processing of the pattern. The first algorithm runs on
standard RAM with unbounded locations and requires exponential amount
of time and space for preprocessing. The second algorithm requires linear
time and space for preprocessing but runs on RAM equipped with two
extra basic operations.
Joint work of Luc Boasson, Patrick Cegielski, Irčne Guessarian,
and Yuri Matiyasevich
|
|
|
Mi,16.12.1998
|
Christian Scheideler (Universität-GH Paderborn)
Eine erste algorithmische Version des allgemeinen Lovasz Local Lemma
|
Das Lovasz Local Lemma (LLL) ist eine allgemeine Methode, die es
ermöglicht, die Existenz von Strukturen mit gewissen Eigenschaften zu
beweisen. Viele Anwendungen des LLL liefern leider keine
Polynomialzeitalgorithmen, um diese Strukturen zu finden. Beck war der
erste, der eine Methode fand, um einige dieser Existenzbeweise in
effiziente Algorithmen umzuformen. Er wandte seine Technik auf das
2-Färbungsproblem von uniformen Hypergraphen an -- ein Problem, für das
eine vereinfachte Version des LLL ausreicht.
Wir werden zeigen, daß es auch effiziente Algorithmen für die 2-Färbung
von nichtuniformen Hypergraphen gibt, d.h. Hypergraphen, für die die
allgemeine Version des LLL angewendet werden muß. Damit beantworten wir
eine offene Frage von Beck. Weiterhin zeigen wir, wie unser Algorithmus
auch auf andere Probleme angewendet werden kann, die die allgemeine
Version des LLL benötigen.
|
|
|
Mi,13.1.1999
|
Volker Heun
Approximative Proteinfaltung im
HP-Seitenketten-Modell auf erweiterten kubischen Gittern
|
|
Eines der bedeutendsten offenen Probleme der Biochemie ist die Bestimmung
der dreidimensionalen Struktur eines Proteins aus seiner Aminosäuresequenz,
da diese die Funktionalität des Proteins bestimmt. Die klassischen Methoden
zur Bestimmung räumlicher Konformationen, wie Röntgenkristallographie und
NMR-Spektroskopie, haben sich als zu aufwendig und zeitintensiv erwiesen.
Im Gegensatz dazu ist heutzutage die Sequenzierung von Proteinen bereits
sehr schnell und einfach durchführbar und es wird allgemein angenommen,
daß die räumliche Struktur von Proteinen bereits in der Aminosäuresequenz
kodiert ist. Damit läßt sich mit Hilfe des sogenannten HP-Modell von
Kenneth Dill die Proteinfaltung kombinatorisch modellieren. Im allgemeinen
ist es jedoch die Strukturvorhersage im HP-Modell NP-hart. In ersten Teil des
Vortrags soll das HP-Modell und die dafür nötigen biologischen Grundlagen
erläutert werden. Im zweiten Teil werden neue Approximationsalgorithmen zur
Bestimmung der Konformation von Proteinen im HP-Modell auf erweiterten
würfelartigen Gittern vorgestellt.
|
|
|
Mi,20.1.1999
|
Peter Rossmanith
Ein schnellerer Algorithmus für Vertex Cover
|
|
Gegeben ein ungerichteter Graph und eine Zahl k, gibt es ein
Vertex Cover der Groesse k? Es wird ein Algorithmus präsentiert,
der dieses Problem in O(kn+1.29175^k) Schritten
löst, wobei n die Größe des Graphen ist. Der bisher beste Algorithmus brauchte
O(kn+1.31951^k) Schritte.
|
|
|
Mi,27.1.1999
|
Artur Czumaj (Universität-GH Paderborn)
Coupling approach for bounding the convergence rates of Markov chains
|
|
Coupling is a classical technique in probability theory used typically
to show similarity of random variables. Recently the coupling technique
has also been used to estimate convergence rates of Markov chains. The
first result in this area have suggested that this approach is useful
only to study highly symmetric Markov chains. However very recently
some authors have showed that suitable use of coupling can be applied
successfully to more complicated chains (for example, to estimate the
volume of convex bodies). In this talk we present two recent approaches
to efficiently apply the coupling method to certain Markov chains.
First we describe the path coupling technique developed by Bubley and
Dyer. We demonstrate this method on certain Markov chains related to
the problem of allocating balls into bins. Next we present the delayed
path coupling technique and apply it to certain ``parallel'' Markov
chains generating random permutations. At the end we shall discuss
further possible applications of these two techniques.
|
|
Mo,8.2.1999,
13:15 Uhr
|
Klaus Reinhardt (Universität Tübingen)
Entscheidbarkeitsfragen bei Codes
|
|
Erstaunlicherweise finden sich in der Literatur kaum Ergebnisse der
folgenden Art:
Ist $\cal A$ eine Klasse von Automaten und $\cal C$ eine Klasse von
Codes, gibt es einen Algorithmus für die Frage, ob $L(A)$ in ${\cal
C}$ liegt bei gegebenem Automaten $A\in {\cal A}$?
Wir beantworten in diesem Vortrag diese Fragen für verschiedene
Varianten von Zähler- und Kellerautomaten sowie für die Klassen der
Codes, $\omega$-Codes, Codes mit endlicher bzw. beschränkter
Dekodierverzögerung sowie Präfix-, Suffix- und Bifixcodes.
Abschlieäend erläutern wir den Bezug dieser Ergebnisse zu
Fragestellungen aus dem Bereich der Fraktalen Geometrie.
Diese Arbeit enstand in Zusammenarbeit mit Ludwig Staiger (Halle)
und Henning Fernau.
|
|
|
Mi,10.2.1999
|
Volker Diekert (Universität Stuttgart)
Neue Entwicklungen auf dem Gebiet der Wortgleichungen
|
Die Beschäftigung mit Gleichungen ist ein grundlegender Gegenstand
mathematischer Untersuchungen. In der Informatik spielen Wortgleichungen
eine besondere Rolle. Man kann sie als Prototyp und Spezialfall von
Unifikationsproblemen auffassen. Gegeben sei ein Paar von Sequenzen
über Konstanten und Variablensymbolen. Die Frage ist, ob sich die
Variablensymbole so substituieren lassen, daß die resultierenden
Wörter über dem Konstantenalphabet identisch werden.
Makanin hat vor mehr als 20 Jahren in einer berühmten Arbeit diese
Frage als entscheidbar nachgewiesen. Erste Komplexitätsbetrachtungen
führten jedoch auf so hohe Schranken, daß dies vielfach als
Abschreckung für praktische Anwendbarkeit gedeutet wurde.
Neue Untersuchungen zeigen, daß die Komplexität erheblich
überschätzt wurde. Es gibt eine Vermutung, nach der das Lösen von
Wortgleichungen nicht schwieriger ist, als das Lösen linearer
Diophantischer Systeme (NP-vollständig).
In dem Vortrag gehe ich insbesondere auf den Spezialfall
quadratischer Wortgleichungen ein. Die vorliegenden Ergebnisse wurden
gemeinsam mit J. M. Robson erzielt und werden auf der STACS'99 in
Trier vorgestellt.
|
|
|
Mi,17.2.1999
|
Tom Friedetzky
Randomized and Adversarial Load-Balancing
|
Wir betrachten ein System von n Prozessoren, die pro Schritt jeweils
eine gewisse Anzahl Tasks generieren bzw. konsumieren, und stellen einen
randomisierten Algorithmus vor, der für Lastausgleich sorgt, d.h. zu
gewissen Zeitpunkten kann er Last von einem Prozessor zu einem anderen
schicken. Ziel ist es, die maximale Last eines Prozessors zu minimieren
bzw. zu beschränken. Hauptaugenmerk wird dabei auf Langzeitstabilität
gelegt, d.h. auf die Entwicklung der Lastverteilung bei fortlaufender
Zeit.
Es werden zwei verschiedene Generierungsmodelle untersucht. Eines davon
ist probabilistischer Natur, d.h. Tasks werden mit einer gewissen
Wahrscheinlichkeit erzeugt und konsumiert; das andere ist "arbitrary",
d.h. ein Prozessor kann pro Schritt seine Last beliebig um eine
konstante Anzahl Tasks verändern (nach oben oder unten).
|
|
|
