May 6: J.Hromkovic, Las Vegas Computations for Finite Automatas


Subject: May 6: J.Hromkovic, Las Vegas Computations for Finite Automatas
From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Wed May 05 1999 - 14:44:43 MET DST


Österreichische Mathematische Gesellschaft
"Osterreichische Computergesellschaft

Einladung zum Vortrag

Über die Stärke von Las Vegas probabilistischen Berechnungen für endliche
Automaten

Juraj Hromkovic

RWTH Aachen

Zeit: Donnerstag, 6. Mai 1999, 17 Uhr c. t.
Ort: Technische Universität Wien,
Wiedner Hauptstraße 8-10, A-1040 Wien,
Seminarraum SEM114A,
Turm A (grüner Bereich), 3. Obergeschoß

Inhalt:

Weil man heute die praktische Lösbarkeit von algorithmischen Aufgaben mit
probabilistischen polynomialzeit Algorithmen verknüpft, ist die Bestimmung
der Berechnungsstärke der randomisierten Verfahren eine der Kernaufgaben
der
Algorithmen- und Komplexitätstheorie. Insbesondere die Vergleiche zwischen
Determinismus, Nichtdeterminismus und Randomisierung für unterschiedliche
Berechnungsmodelle sind gefragt.

In diesem Vortrag beschäftigen wir uns mit diesen Fragen für endliche
Automaten. Wir geben vollständige Antworten für die klassischen endlichen
ein-Weg Automaten, wo exponentielle Unterschiede in der Anzahl der
Zustände
zwischen Las Vegas (Determinismus) und Nichtdeterminismus auftreten
können,
aber höchstens quadratische Unterschiede zwischen Las Vegas und
Determinismus möglich sind.

Im zwei-Weg Fall ist die Situation viel komplizierter. Es ist ein
bekanntes
altes Problem, ob überhaupt ein grosser Unterschied zwischen Determinismus
und Nichtdeterminismus möglich ist. Außer quadratischen Unterschieden
zwischen allen betrachteten Modellen zeigen wir ein teilweise
überraschendes
Resultat: kleine nichtdeterministische endliche Automaten für eine Sprache
L
und deren Komplement sichern die Existenz eines kleinen endlichen zwei-Weg
Las Vegas Automaten.

Im Anschluß an den Vortrag findet eine Nachsitzung statt.

Österreichische Mathematische Gesellschaft
Sekretariat: Technische Universität 118/2, Wiedner Hauptstraße 8-10,
A-1040
Wien
Tel. 02 58801 11823 DW



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST