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

Raskin, Mikhail

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

pdf-format:
LIPIcs-ICALP-2018-138.pdf (0.4 MB)

Abstract

Unambiguous non-deterministic finite automata (UFA) are non-deterministic automata (over finite words) such that there is at most one accepting run over each input. Such automata are known to be potentially exponentially more succinct than deterministic automata, and non-deterministic automata can be exponentially more succinct than them.
In this paper we establish a superpolynomial lower bound for the state complexity of the translation of an UFA to a non-deterministic automaton for the complement language. This disproves the formerly conjectured polynomial upper bound for this translation. This lower bound only involves a one letter alphabet, and makes use of the random graph methods.
The same proof also shows that the translation of sweeping automata to non-deterministic automata is superpolynomial.

BibTeX - Entry

@InProceedings{raskin:LIPIcs:2018:9142,
  author =	{Mikhail Raskin},
  title =	{{A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{138:1--138:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9142},
  URN =		{urn:nbn:de:0030-drops-91428},
  doi =		{10.4230/LIPIcs.ICALP.2018.138},
  annote =	{Keywords: unambiguous automata, language complement, lower bound}
}

Keywords: unambiguous automata, language complement, lower bound
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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