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.FSTTCS.2020.56
URN: urn:nbn:de:0030-drops-132973
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13297/
Go to the corresponding LIPIcs Volume Portal

Schewe, Sven

Minimising Good-For-Games Automata Is NP-Complete

pdf-format:
LIPIcs-FSTTCS-2020-56.pdf (0.5 MB)

Abstract

This paper discusses the hardness of finding minimal good-for-games (GFG) Büchi, Co-Büchi, and parity automata with state based acceptance. The problem appears to sit between finding small deterministic and finding small nondeterministic automata, where minimality is NP-complete and PSPACE-complete, respectively. However, recent work of Radi and Kupferman has shown that minimising Co-Büchi automata with transition based acceptance is tractable, which suggests that the complexity of minimising GFG automata might be cheaper than minimising deterministic automata.
We show for the standard state based acceptance that the minimality of a GFG automaton is NP-complete for Büchi, Co-Büchi, and parity GFG automata. The proofs are a surprisingly straight forward generalisation of the proofs from deterministic Büchi automata: they use a similar reductions, and the same hard class of languages.

BibTeX - Entry

@InProceedings{schewe:LIPIcs:2020:13297,
  author =	{Sven Schewe},
  title =	{{Minimising Good-For-Games Automata Is NP-Complete}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{56:1--56:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13297},
  URN =		{urn:nbn:de:0030-drops-132973},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.56},
  annote =	{Keywords: Good-for-Games Automata, Automata Minimisation}
}

Keywords: Good-for-Games Automata, Automata Minimisation
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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