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

Jez, Artur

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

pdf-format:
22.pdf (0.8 MB)

Abstract

In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is introduced: the SLPs are recompressed, so that substrings of the input text are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.

Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter [Plandowski Rytter 1999] and extending the partial result of Lohrey and Mathissen [Lohrey and Mathissen 2011];
as this problem is known to be NP-hard, we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard.

BibTeX - Entry

@InProceedings{jez:LIPIcs:2012:3406,
  author =	{Artur Jez},
  title =	{{Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{136--147},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3406},
  URN =		{urn:nbn:de:0030-drops-34068},
  doi =		{10.4230/LIPIcs.STACS.2012.136},
  annote =	{Keywords: Compressed membership problem, SLP, Finite Automata, Algorithms for compressed data}
}

Keywords: Compressed membership problem, SLP, Finite Automata, Algorithms for compressed data
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

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