AbstractThe power of weighted finite automata to describe very complex images was widely studied, see [5, 6, 8]. Finite automata can be used as an effective tool for compression of two-dimensional images. There are some software packages using this type of compression, see [6, 13]. We consider the complexity of some pattern-matching problems for two-dimensional images which are highly compressed using finite deterministic and weighted automata as small descriptions of images. Our basic problems are compressed pattern-matching, where the pattern is given explicitly and the text is compressed, and fully compressed pattern-matching (when also the pattern is compressed). We consider also fully compressed pattern-checking: testing of a given occurrence of the compressed pattern in a given position. We prove:
1. Compressed matching for deterministic automata is in P.
2. Compressed matching for weighted automata is NP-complete.
3. Fully compressed pattern-checking for deterministic automata is in P.
4.Fully compressed matching for deterministic automata is NP-complete.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; E.4 [Coding and Information Theory]
Additional Key Words and Phrases: pattern-matching, compression, automata, two-dimensional texts
Selected references
- Amihood Amir, Gary Benson, and Martin Farach. Let sleeping files lie: Pattern matching in Z-compressed files. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 705-714, Arlington, Virginia, 23-25 January 1994.
- Amihood Amir, Gary Benson, and Martin Farach. Optimal two-dimensional compressed matching. In Serge Abiteboul and Eli Shamir, editors, Automata, Languages and Programming, 21st International Colloquium, volume 820 of Lecture Notes in Computer Science, pages 215-226, Jerusalem, Israel, 11-14 July 1994. Springer-Verlag.
- Karel Culik II and Juhani Karhumäki. Finite automata computing real functions. SIAM Journal on Computing, 23(4):789-814, August 1994.
- Martin Farach and Mikkel Thorup. String matching in Lempel-Ziv compressed strings. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 703-712, Las Vegas, Nevada, 29 May-1 June 1995.
- Marek Karpinski, Wojciech Rytter, and Ayumi Shinohara. Pattern-matching for strings with short descriptions. In Zvi Galil and Esko Ukkonen, editors, Combinatorial Pattern Matching, 6th Annual Symposium, volume 937 of Lecture Notes in Computer Science, pages 205-214, Espoo, Finland, 5-7 July 1995. Springer.