License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.400
URN: urn:nbn:de:0030-drops-28816
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2881/
Go to the corresponding LIPIcs Volume Portal

Schewe, Sven

Beyond Hyper-Minimisation---Minimising DBAs and DPAs is NP-Complete

pdf-format:
35.pdf (0.4 MB)

Abstract

In this paper we study the problem of minimising deterministic automata over finite and infinite words. Deterministic finite automata are the simplest devices to recognise regular languages, and deterministic \buchi, \cobuchi, and parity automata play a similar role in the recognition of $\omega$-regular languages. While it is well known that the minimisation of deterministic finite and weak automata is cheap, the complexity of minimising deterministic \buchi\ and parity automata has remained an open challenge. We establish the NP-completeness of these problems. A second contribution of this paper is the introduction of almost equivalence, an equivalence class for strictly between language equivalence for deterministic \buchi\ or \cobuchi\ automata and language equivalence for deterministic finite automata. Two finite automata are almost equivalent if they, when used as a monitor, provide a different answer only a bounded number of times in any run, and we call the minimal such automaton relatively minimal. Minimisation of DFAs, hyper-minimisation, relative minimisation, and the minimisation of deterministic \buchi\ (or \cobuchi) automata are operations of increasing reduction power, as the respective equivalence relations on automata become coarser from left to right. Besides being a natural equivalence relation for finite automata, almost equivalence is language preserving for weak automata, and can therefore also be viewed as a generalisation of language equivalence for weak automata to a more general class of automata. From the perspective of \buchi\ and \cobuchi\ automata, we gain a cheap algorithm for state-space reduction that also turns out to be beneficial for further heuristic or exhaustive state-space reductions put on top of it.

BibTeX - Entry

@InProceedings{schewe:LIPIcs:2010:2881,
  author =	{Sven Schewe},
  title =	{{Beyond Hyper-Minimisation---Minimising DBAs and DPAs is NP-Complete}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{400--411},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2881},
  URN =		{urn:nbn:de:0030-drops-28816},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.400},
  annote =	{Keywords: Automata Theory, Complexity,  B{\"u}chi Automata, Parity Automata}
}

Keywords: Automata Theory, Complexity, Büchi Automata, Parity Automata
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

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