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.STACS.2018.47
URN: urn:nbn:de:0030-drops-84963
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8496/
Go to the corresponding LIPIcs Volume Portal

Kuperberg, Denis ; Majumdar, Anirban

Width of Non-deterministic Automata

pdf-format:
LIPIcs-STACS-2018-47.pdf (0.5 MB)

Abstract

We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width generalises the notion of good-for-games (GFG) automata, that correspond to NFAs of width 1, and where an accepting run can be built on-the-fly on any accepted input. We describe an incremental determinisation construction on NFAs, which can be more efficient than the full powerset determinisation, depending on the width of the input NFA. This construction can be generalised to infinite words, and is particularly well-suited to coBüchi automata in this context. For coBüchi automata, this procedure can be used to compute either a deterministic automaton or a GFG one, and it is algorithmically more efficient in this last case. We show this fact by proving that checking whether a coBüchi automaton is determinisable by pruning is NP-complete. On finite or infinite words, we show that computing the width of an automaton is PSPACE-hard.

BibTeX - Entry

@InProceedings{kuperberg_et_al:LIPIcs:2018:8496,
  author =	{Denis Kuperberg and Anirban Majumdar},
  title =	{{Width of Non-deterministic Automata}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8496},
  URN =		{urn:nbn:de:0030-drops-84963},
  doi =		{10.4230/LIPIcs.STACS.2018.47},
  annote =	{Keywords: width, non-deterministic automata, determinisation, good-for-games, complexity}
}

Keywords: width, non-deterministic automata, determinisation, good-for-games, complexity
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

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