DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2020.27

State Space Reduction For Parity Automata

Authors: Christof Löding and Andreas Tollkötter

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

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 as

Christof Löding and Andreas Tollkötter. State Space Reduction For Parity Automata. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{loding_et_al:LIPIcs.CSL.2020.27,
  author =	{L\"{o}ding, Christof and Tollk\"{o}tter, Andreas},
  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 =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.27},
  URN =		{urn:nbn:de:0030-drops-116701},
  doi =		{10.4230/LIPIcs.CSL.2020.27},
  annote =	{Keywords: automata, \omega-automata, parity, minimization, state space reduction, deterministic, simulation relations}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2016.88

Transformation Between Regular Expressions and omega-Automata

Authors: Christof Löding and Andreas Tollkötter

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract

We propose a new definition of regular expressions for describing languages of omega-words, called infinity-regular expressions. These expressions are obtained by adding to the standard regular expression on finite words an operator infinity that acts similar to the Kleene-star but can be iterated finitely or infinitely often (as opposed to the omega-operator from standard omega-regular expressions, which has to be iterated infinitely often). We show that standard constructions between automata and regular expressions for finite words can smoothly be adapted to infinite words in this setting: We extend the Glushkov construction yielding a simple translation of infinity-regular expressions into parity automata, and we show how to translate parity automata into infinity-regular expressions by the classical state elimination technique, where in both cases the nesting of the * and the infinity operators corresponds to the priority range used in the parity automaton. We also briefly discuss the concept of deterministic expressions that directly transfers from standard regular expressions to infinity-regular expressions.

Cite as

Christof Löding and Andreas Tollkötter. Transformation Between Regular Expressions and omega-Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 88:1-88:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{loding_et_al:LIPIcs.MFCS.2016.88,
  author =	{L\"{o}ding, Christof and Tollk\"{o}tter, Andreas},
  title =	{{Transformation Between Regular Expressions and omega-Automata}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{88:1--88:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.88},
  URN =		{urn:nbn:de:0030-drops-64962},
  doi =		{10.4230/LIPIcs.MFCS.2016.88},
  annote =	{Keywords: infinity regular expressions, parity automata}
}

Search Results

Documents authored by Tollkötter, Andreas

State Space Reduction For Parity Automata

Abstract

Cite as

Transformation Between Regular Expressions and omega-Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message