License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.27
URN: urn:nbn:de:0030-drops-116701
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11670/
Go to the corresponding LIPIcs Volume Portal

Löding, Christof ; Tollkötter, Andreas

State Space Reduction For Parity Automata

pdf-format:
LIPIcs-CSL-2020-27.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{lding_et_al:LIPIcs:2020:11670,
  author =	{Christof L{\"o}ding and Andreas Tollk{\"o}tter},
  title =	{{State Space Reduction For Parity Automata}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11670},
  URN =		{urn:nbn:de:0030-drops-116701},
  doi =		{10.4230/LIPIcs.CSL.2020.27},
  annote =	{Keywords: automata, ?-automata, parity, minimization, state space reduction, deterministic, simulation relations}
}

Keywords: automata, ω-automata, parity, minimization, state space reduction, deterministic, simulation relations
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020
Supplementary Material: https://github.com/atollk/master-thesis

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI