P-COMPLETE PROBLEMS IN DATA-COMPRESSION

Authors
DEAGOSTINO S
Citation
S. Deagostino, P-COMPLETE PROBLEMS IN DATA-COMPRESSION, Theoretical computer science, 127(1), 1994, pp. 181-186
Citations number
13
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
127
Issue
1
Year of publication
1994
Pages
181 - 186
Database
ISI
SICI code
0304-3975(1994)127:1<181:PPID>2.0.ZU;2-Q
Abstract
In this paper we study the parallel computational complexity of some m ethods for compressing data via textual substitution. We show that the Ziv-Lempel algorithm and two standard variations are P-complete. Henc e an efficient parallelization of these algorithms is not possible unl ess P = NC.