Prague Stringology Conference 2011
Radosław Głowinski and Wojciech Rytter
Observations On Compressed Pattern-Matching with Ranked Variables in Zimin Words
| Abstract: |
| Zimin words are very special finite words which are closely related to the pattern-avoidability problem. This problem consists in testing if an instance of a given pattern with variables occurs in almost all words over any finite alphabet. The problem is not well understood, no polynomial time algorithm is known and its NP-hardness is also not known. The pattern-avoidability problem is equivalent to searching for a pattern (with variables) in a Zimin word. The main difficulty is potentially exponential size of Zimin words. We use special properties of Zimin words, especially that they are highly compressible, to design efficient algorithms for special version of the pattern-matching, called here ranked matching. It gives a new interpretation of Zimin algorithm in compressed setting. We discuss the structure of rankings of variables and compressed representations of values of variables. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |