Generalized synchronization and intersection non-emptiness of finite-state automata

Autor: Wolf, Petra
Jazyk: angličtina
Rok vydání: 2022
Předmět:
DOI: 10.25353/bbxs-bv31ubtr-xxxx-0898-dfc2
Popis: The main focus of this work is to study the computational complexity of generalizations of the synchronization problem for deterministic finite automata (DFA). This problem asks for a given DFA, whether there exists a word w that maps each state of the automaton to one state. We call such a word w a synchronizing word. A synchronizing word brings a system from an unknown configuration into a well defined configuration and thereby resets the system. We generalize this problem in four different ways. First, we restrict the set of potential synchronizing words to a fixed regular language associated with the synchronization under regular constraint problem. The motivation here is to control the structure of a synchronizing word so that, for instance, it first brings the system from an operate mode to a reset mode and then finally again into the operate mode. The next generalization concerns the order of states in which a synchronizing word transitions the automaton. Here, a DFA A and a partial order R is given as input and the question is whether there exists a word that synchronizes A and for which the induced state order is consistent with R. Thereby, we study different ways for a word to induce an order on the state set. Then, we change our focus from DFAs to push-down automata and generalize the synchronization problem to push-down automata and in the following work, to visibly push-down automata. Here, a synchronizing word still needs to map each state of the automaton to one state but it further needs to fulfill some constraints on the stack. We study three different types of stack constraints where after reading the synchronizing word, the stacks associated to each run in the automaton must be (1) empty, (2) identical, or (3) can be arbitrary. We observe that the synchronization problem for general push-down automata is undecidable and study restricted sub-classes of push-down automata where the problem becomes decidable. For visibly push-down automata we even obtain efficient algorithms for some settings. The second part of this work studies the intersection non-emptiness problem for DFAs. This problem is related to the problem of whether a given DFA A can be synchronized into a state q as we can see the set of words synchronizing A into q as the intersection of languages accepted by automata obtained by copying A with different initial states and q as their final state. For the intersection non-emptiness problem, we first study the complexity of the, in general PSPACE-complete, problem restricted to subclasses of DFAs associated with the two well known Straubing-Thérien and Cohen-Brzozowski dot-depth hierarchies. Finally, we study the problem whether a given minimal DFA A can be represented as the intersection of a finite set of smaller DFAs such that the language L(A) accepted by A is equal to the intersection of the languages accepted by the smaller DFAs. There, we focus on the subclass of permutation and commutative permutation DFAs and improve known complexity bounds.
Das Hauptaugenmerk dieser Arbeit liegt auf der Untersuchung der Komplexität von Verallgemeinerungen des Synchronisationsproblems für deterministische endliche Automaten (DEAs). Dieses Problem fragt für einen gegebenen DEA, ob es ein Wort w gibt, das jeden beliebigen Zustand des Automaten in einen einzelnen Zustand überführt. Wir nennen ein solches Wort w ein synchronisierendes Wort. Ein synchronisierendes Wort bringt ein System aus einer unbekannten Konfiguration in eine wohldefinierte Konfiguration und setzt es damit zurück. Wir verallgemeinern dieses Problem auf vier verschiedene Arten. Zuerst beschränken wir die Menge potentiell synchronisierender Wörter auf eine feste reguläre Sprache, die dem so genannten Synchronisierungsproblem unter regulären Randbedingungen zugeordnet ist. Die Motivation dabei ist, die Struktur eines synchronisierenden Wortes zu kontrollieren, sodass dieses zum Beispiel das System zunächst aus einem Arbeitsmodus in einen Resetmodus bringt und nach vollendeter Synchronisierung wieder in den Arbeitsmodus überführt. Die nächste Verallgemeinerung betrifft die Reihenfolge der Zustände, in denen ein synchronisierendes Wort den Automaten durchläuft. Hierbei besteht die Eingabe aus einem DEA A und einer partiellen Ordnung R und die Frage ist, ob ein Wort existiert, das A synchronisiert und dessen induzierte Zustandsordnung mit der partiellen Ordnung R übereinstimmt. Dabei untersuchen wir verschiedene Möglichkeiten, wie ein Wort eine Ordnung auf der Zustandsmenge induzieren kann. Dann verlagern wir unseren Fokus von DEAs auf Kellerautomaten und verallgemeinern das Synchronisationsproblem auf Kellerautomaten, sowie in der vierten Arbeit auf sichtbare Kellerautomaten. Hierbei muss ein synchronisierendes Wort immer noch alle Zustände des Automatens auf einen einzelnen Zustand abbilden, aber zusätzlich müssen noch einige Bedingungen für dem Keller erfüllt sein. Wir untersuchen drei verschiedene Arten von Keller-Bedingungen, bei denen nach dem Lesen eines synchronisierenden Wortes, die jedem Lauf im Automaten zugeordneten Keller entweder (1) leer oder (2) identisch sein müssen, oder (3) beliebig sein dürfen. Wir beobachten, dass das Synchronisationsproblem für allgemeine Kellerautomaten unentscheidbar ist und untersuchen eingeschränkte Unterklassen von Kellerautomaten, bei denen das Problem entscheidbar wird. Für sichtbare Kellerautomaten erhalten wir für einige Varianten sogar effiziente Algorithmen. Der zweite Teil dieser Arbeit untersucht das Schnitt-Leerheitsproblem für DEAs. Dieses Problem ist verwandt mit dem Problem, ob ein gegebener DEA A in einen bestimmten Zustand q synchronisiert werden kann, da wir die Menge der Wörter, die A in q synchronisieren, ansehen können als den Schnitt der Sprachen, die von Automaten erkannt werden, die durch ein Kopieren von A mit unterschiedlichen Anfangszuständen und q als einzigem Endzustand erzeugt werden. Bei dem Schnitt-Leerheitsproblem untersuchen wir zunächst die Komplexität des Problems, welches im Allgemeinen PSPACE-vollständig ist, auf Teilklassen von DEAs, die mit den beiden bekannten Straubing-Thérien und Cohen-Brzozowski dot-depth Hierarchien assoziiert sind. Zum Schluss untersuchen wir noch das Problem, ob ein gegebener minimaler DEA A dargestellt werden kann als Schnitt kleinerer DEAs, sodass die von A erkannte Sprache L(A) identisch ist zu dem Schnitt der von den kleineren Automaten erkannten Sprachen. Hierbei fokussieren wir uns auf die Teilklassen der Permutations DEAs und kommutativen Permutations DEAs und verbessern die bisher bekannten Komplexitätsschranken für dieses Problem.
Databáze: OpenAIRE
Externí odkaz: