
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1996  Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V  
85156

The complexity of TwoDimensional Compressed PatternMatching
Piotr Berman, Marek Karpinski, Lawrence Larmore, Wojciech Plandowski, Wojciech Rytter [Download PostScript] [Download PDF] We consider the complexity of problems for highly compressed 2dimensional texts: {\em compressed} patternmatching (when the pattern is not compressed and the text is compressed) and {\em fully compressed} patternmatching (when also the pattern is compressed). First we consider 2dimensional compression in terms of straightline programs, see \cite{KRS}. It is a natural way for representing very highly compressed images, by describing larger parts in terms of smaller (earlier described) ones. For 1dimensional strings there exist polynomialtime deterministic algorithms for similar types of compression \cite{ABF1,FT,GKPR,KRS}. We show that the complexity {dramatically} increases in a 2dimensional setting: \begin{itemize} \item %\hspace*{0.6cm} {\em Compressed matching} for two dimensional compressed images is {\em NPcomplete}. \item %\hspace*{0.6cm} {\em Fully compressed matching} for two dimensional compressed images is {\em $\Sigma_2P$complete}. \item %\hspace*{0.6cm} Testing a given occurrence of a two dimensional compressed pattern is {\em coNPcomplete}. \end{itemize} %\vskip 0.1cm \noindent On the other hand we show efficient algorithms for some related problems: \begin{itemize} \item %\hspace*{0.6cm} Testing equality of two compressed two dimensional patterns %can be done efficiently by a randomized algorithm (an application of algebraic techniques). \item %\hspace*{0.6cm} Testing a given occurrence of an uncompressed pattern in a two dimensional compressed image. %can be done efficiently by a deterministic algorithm. \end{itemize} %\noindent We also show the surprising fact that the compressed size of a subrectangle of a compressed two dimensional array can grow exponentially, unlike the one dimensional case. 

Last Change:
08/18/99 at 13:00:38
English 
Universität Bonn > Institut für Informatik > Abteilung V 