Straight-Line Programs (SLP) are widely used compressed representations of words. In this work we study the rational transformations and the literal shuffle of words compressed via SLP, proving that the first preserves the compression rate, while the second does not. As a consequence, we prove a tight bound for the descriptional complexity of 2D texts compressed via SLP. Finally, we observe that the Pattern Matching Problem for texts expressed by the literal shuffle of compressed words is NP-complete. However, we present a parameter-tractable algorithm for this problem, working in polynomial time whenever the length of the pattern is polynomially related to that of the text.
Literal shuffle of compressed words / A. Bertoni, C. Choffrut, R. Radicioni - In: Fifth IFIP international conference on theoretical computer science - TCS 2008 : IFIP 20th world computer congress, TC1, foundations of computer science, september 7-10, 2008, Milano, Italy / [a cura di] G. Ausiello [et al.]. - Berlin : Springer, 2008. - ISBN 9780387096797. - pp. 87-110 (( Intervento presentato al 5th. convegno Ifip International Conference On Theoretical Computer Science tenutosi a Milano nel 2008 [10.1007/978-0-387-09680-3].
Literal shuffle of compressed words
A. BertoniPrimo
;R. RadicioniUltimo
2008
Abstract
Straight-Line Programs (SLP) are widely used compressed representations of words. In this work we study the rational transformations and the literal shuffle of words compressed via SLP, proving that the first preserves the compression rate, while the second does not. As a consequence, we prove a tight bound for the descriptional complexity of 2D texts compressed via SLP. Finally, we observe that the Pattern Matching Problem for texts expressed by the literal shuffle of compressed words is NP-complete. However, we present a parameter-tractable algorithm for this problem, working in polynomial time whenever the length of the pattern is polynomially related to that of the text.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
