State Space Reduction For Parity Automata
The work
| Authors | Christof Löding; Andreas Tollkötter |
|---|---|
| Editors | |
| Type | inproceedings |
| Year | 2020 |
| Citekey | loding2020state |
Where it appeared
| Published in | 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) |
|---|---|
| Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Series | Leibniz International Proceedings in Informatics |
| Number in series | 152 |
| Volume | 152 |
| Pages | 27:1--27:16 |
Identifiers
| DOI | 10.4230/lipics.csl.2020.27 |
|---|
Abstract
Exact minimization of ω-automata is a difficult problem and heuristic algorithms are a subject of current research. We propose several new approaches to reduce the state space of deterministic parity automata. These are based on extracting information from structures within the automaton, such as strongly connected components, coloring of the states, and equivalence classes of given relations, to determine states that can safely be merged. We also establish a framework to generalize the notion of quotient automata and uniformly describe such algorithms. The description of these procedures consists of a theoretical analysis as well as data collected from experiments.
Cite it as
@inproceedings{loding2020state,
title = {State Space Reduction For Parity Automata},
author = {Christof Löding and Andreas Tollkötter},
year = {2020},
booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
series = {Leibniz International Proceedings in Informatics},
volume = {152},
pages = {27:1--27:16},
doi = {10.4230/lipics.csl.2020.27},
}
This record lives at https://refs.drheap.org/loding2020state/ and will keep doing so.