Das uniforme Wortproblem für Automatengruppen beschränkter Aktivität

Abstract

Endliche Automaten sind für viele Bereiche der Informatik von enormer Bedeutung. Neben den praktischen Anwendungen dieser Maschinenmodelle sind vor allem die, von ihnen erzeugten Automaten(halb)gruppen und ihre algebraischen sowie algorithmischen Eigenschaften von Interesse für die theoretische Informatik. Die Klassifizierung von Automatengruppen nach ihrer Aktivität durch Said N. Sidki und später durch Bartholdi et al. ermöglicht zusätzlich eine spezifischere Untersuchung dieser Eigenschaften. Die Aktivität ist hierbei das Wachstum der Sprache der Wörter, auf denen ein Automat nichttrivial operiert. In dieser Arbeit gehen wir vor allem auf die Komplexität des (uniformen) Wortproblems von Automatengruppen finitärer und Automatenmonoiden beschränkter Aktivität ein. Weiterhin ordnen wir eine Variante des uniformen Wortproblems, das komprimierte uniforme Wortproblem von Automatengruppen finitärer Aktivität, komplexitätstheoretisch ein. Dazu erweitern wir einen Beweis von Volodymyr V. Nekrashevych und Ievgen V. Bondarenko auf Automatenmonoide und zeigen, dass jedes Automatenmonoid beschränkter Aktivität auch kontrahierend ist. Basierend hierauf ist es möglich, das Wortproblem dieser Automatenmonoide in deterministisch logarithmischem Platz zu entscheiden. Für den Beweis der coNP-Vollständigkeit des uniformen Wortproblems finitärer Automatengruppen nutzen wir die Technik der balancierten Kommutatoren, die ursprünglich von Anatolij I. Mal'cev eingeführt und von David A. Mix Barrington verwendet wurde. Dieses Resultat kann direkt auf Automatengruppen beschränkter Aktivität übertragen werden und zeigt, dass das uniforme Wortproblem dieser Automatenklasse coNP-schwer ist. Schließlich betrachten wir das komprimierte uniforme Wortproblem finitärer Automatengruppen, bei dem das Zustandswort durch ein sogenanntes Straight-Line-Programm, also eine deterministisch kontextfreie Grammatik die nur ein Wort erzeugt, eingegeben wird. Analog zum vorangegangenen Beweis verwenden wir hier die Technik der balancierten Kommutatoren um zu zeigen, dass das genannte Problem PSPACE-vollständig ist.