Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein.

Prof. Dr. Henning Fernau, Universität Trier: Warum ist das nur so schwer?

Beginn: 19.02.2015, 08:30 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. OG, Hörsaal M 161 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2015-02-19-fernau.html Kontakt: Prof. Dr.-Ing. Ina Schaefer

In meinem Vortrag gehe ich dieser Frage anhand zweier NP-harter Probleme für deterministische endliche Automaten (DEA) nach. (1) Wir betrachten wir die Aufgabe, ein möglichst kurzes synchronisierendes Wort für einen DEA zu finden, also ein Wort, nach dessen Abarbeitung der Automat in einen eindeutig bestimmten Zustand gelangt ist, unabhängig von seinem Startzustand. (2) Wir fragen bei Eingabe zweier disjunkter Wortmengen X und Y nach einem DEA kleinstmöglicher Zustandsanzahl, der alle Wörter aus X akzeptiert, aber keines der Wörter aus Y. Für diese Probleme beantworten wir die Eingangsfrage durch eine mehrparametrische Analyse.