Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Jez, Artur

dblp



BibTeX cite key*:

Jez2012STACS

Title

Title*:

The Complexity of Compressed Membership Problems for Finite Automata

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://link.springer.com/journal/224

Download URL
for the article:

http://link.springer.com/content/pdf/10.1007%2Fs00224-013-9443-6.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://link.springer.com/

Publisher's
Address:

New York

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

55

Number:

4

Publishing Date:

November 2014

Pages*:

685-718

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1007/s00224-013-9443-6

Note, Abstract, ©

Note:


(LaTeX) 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 employed: the SLPs are recompressed, so that substrings of the input
word 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
(Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999) and extending the partial
result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp. 275–288, Springer,
Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter,
Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999), 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 (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3–6,
2004; Beaudry et al., SIAM J. Comput. 26(1):138–152, 1997).

URL for the Abstract:


Categories,
Keywords:

Compressed membership problem, SLP, Finite automata, Algorithms for compressed data

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Jez2012STACS,
AUTHOR = {Jez, Artur},
TITLE = {The Complexity of Compressed Membership Problems for Finite Automata},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2014},
NUMBER = {4},
VOLUME = {55},
PAGES = {685--718},
ADDRESS = {New York},
MONTH = {November},
ISBN = {1432-4350},
DOI = {10.1007/s00224-013-9443-6},
}


Entry last modified by Artur Jez, 12/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/24/2014 04:31:02 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
11/24/2014 04:33:59 PM
11/24/2014 04:31:02 PM