On the complexity of pattern matching for highly compressed two-dimensional texts.

DOI10.1006/jcss.2002.1852zbMath1059.68098OpenAlexW2066012259WikidataQ29028269 ScholiaQ29028269MaRDI QIDQ1872708

Marek Karpinski, Wojciech Plandowski, Wojciech Rytter, Piotr Berman, Lawrence L. Larmore

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a4d1a1876a37cc5e72307e09022f3642e8e99b36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Pattern recognition, speech recognition (68T10) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Equality Testing of Compressed Strings ⋮ Context-free commutative grammars with integer counters and resets ⋮ Processing succinct matrices and vectors ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Linear pattern matching of compressed terms and polynomial rewriting ⋮ Rewriting recursive aggregates in answer set programming: back to monotonicity ⋮ Application of Lempel-Ziv factorization to the approximation of grammar-based compression. ⋮ Fast equality test for straight-line compressed strings ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Protecting elections by recounting ballots ⋮ The complexity of compressing subsegments of images described by finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Optimal Two-Dimensional Compressed Matching
• Efficient algorithms for Lempel-Ziv encoding

This page was built for publication: On the complexity of pattern matching for highly compressed two-dimensional texts.