The Complexity of Simplifying $\omega$-Automata through the Alternating Cycle Decomposition

Autor:	Casares, Antonio, Mascle, Corto
Rok vydání:	2024
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Logic in Computer Science 68Q45 F.4.3
Druh dokumentu:	Working Paper
Popis:	In 2021, Casares, Colcombet and Fijalkow introduced the Alternating Cycle Decomposition (ACD), a structure used to define optimal transformations of Muller into parity automata and to obtain theoretical results about the possibility of relabelling automata with different acceptance conditions. In this work, we study the complexity of computing the ACD and its DAG-version, proving that this can be done in polynomial time for suitable representations of the acceptance condition of the Muller automaton. As corollaries, we obtain that we can decide typeness of Muller automata in polynomial time, as well as the parity index of the languages they recognise. Furthermore, we show that we can minimise in polynomial time the number of colours (resp. Rabin pairs) defining a Muller (resp. Rabin) acceptance condition, but that these problems become NP-complete when taking into account the structure of an automaton using such a condition. Comment: Full version of a paper accepted at MFCS 2024. v2: Results updated to apply to both automata with single and multiple colours per transition
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2401.03811 Zobrazit plný text záznamu View this record from Arxiv