Gewisse Eigenschaften deterministischer Automaten und ihre Komplexität

Abstract

In dieser Arbeit wird untersucht, wie sich die Ergebnisse von Cho und Huynh [CH91] zur Komplexität der Probleme gegeben ein deterministischer endlicher Automat: ist die von diesem Automat akzeptierte Sprache sternfrei bzw. piecewise testable bzw. dot-depth-one'' auf andere Klassen von Sprachen übertragen lassen. Es kann gezeigt werden, dass alle Klassen, die durch Omega-Gleichungen charakterisierbar sind, in PSPACE entscheidbar und NL-schwer sind. Wir geben Verfahren an, dass zu jeder Gleichung, die eine gewisse Bedingung erfüllt, ein Verbotsmuster erzeugt, das in NL entscheidbar ist, und zeigen, dass das Schnittproblem bereits für die Klasse der deterministische endliche Automaten, die locally testable Sprachen akzeptieren, PSPACE-vollständig ist, wodurch der PSPACE-Vollständigkeitsbeweis für die Klasse der sternfreien Spachen vereinfacht werden kann.