Birgit Engels
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Rücksetz-Sequenzen für monotone Automaten

Eine Rücksetz-Sequenz für einen deterministischen endlichen Automaten (DEA) ist eine Zeichenkette aus dem Eingabealphabet des Automaten, die jeden seiner Zustaende in den Startzustand überführt. In dem Artikel von David Eppstein ('90), den ich vorstellen möchte, werden (verbesserte) Algorithmen für das Finden von Rücksetz-Sequenzen insbesondere von monotonen DEAs entwickelt, sowie Ausagen über die minimale Länge der Sequenzen und die Komplexität des Problems gemacht. Monotone Automaten modelllieren dabei bestimmte Werstück- Orientierer in der Fertigungstechnik und sind damit für die Anwendung interessant.