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:
Compressed membership problem, SLP, Finite automata, Algorithms for compressed data
HyperLinks / References / URLs: