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.2016.123
URN: urn:nbn:de:0030-drops-62589
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6258/
Go to the corresponding LIPIcs Volume Portal

Zetzsche, Georg

The Complexity of Downward Closure Comparisons

pdf-format:
LIPIcs-ICALP-2016-123.pdf (0.5 MB)

Abstract

The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models.

One advantage of abstracting a language by its downward closure is that then equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages K and L from classes C and D, respectively, does the downward closure of K include (equal) that of L?

These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order k, we prove hardness for complements of nondeterministic k-fold exponential time.

BibTeX - Entry

@InProceedings{zetzsche:LIPIcs:2016:6258,
  author =	{Georg Zetzsche},
  title =	{{The Complexity of Downward Closure Comparisons}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{123:1--123:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6258},
  URN =		{urn:nbn:de:0030-drops-62589},
  doi =		{10.4230/LIPIcs.ICALP.2016.123},
  annote =	{Keywords: Downward closures, Complexity, Inclusion, Equivalence}
}

Keywords: Downward closures, Complexity, Inclusion, Equivalence
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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