Definability and Compression

• Autorzy: Afrati F. , Leiß H. , Rougemont M. de
• Języki publikacji: EN

Abstrakty

EN

A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic L, we study the definability of property P on the class K'. We consider two compression schemes on unary ordered structures (strings), compression by run-length encoding and the classical Lempel-Ziv-78 scheme. First-order properties of strings are first-order on run-length compressed strings, but this fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv-78 compression scheme. We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass F of the first-order properties of strings such that if P is a property in F, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings, i.e. regular languages, are dyadic second-order definable on Lempel-Ziv compressed strings.

Słowa kluczowe

EN

logic; definability; string compression; Lempel-Ziv-78

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 155--180
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Afrati F.

autor

Leiß H.

autor

Rougemont M. de

• LRI, Bâtiment 490, Université Paris-Sud, F-91405 Orsay Cedex, France,

Bibliografia

• [1] Afrati, F., Leiß, H., de Rougemont, M.: Definability and Compression, 15th Annual IEEE Symposium on Logic In Computer Science, LICS’2000. Santa Barbara, CA, June 22-26, 2000, Computer Society Press, 2000.
• [2] de Agostino, S.: P-complete problems in data compression, Theoretical Computer Science, 127, 1994, 181-186.
• [3] Bell, T. C., Cleary, J. G., Witten, I. H.: Text Compression, Prentice Hall, Englewood Cliffs, NJ, 1990.
• [4] Bryant, R.: Graph-based algorithms for boolean function manipulation, IEEE Transactions on Computers, 35(8), 1986, 677-691.
• [5] B¨uchi, J. R.: On a decision method in restricted second order arithmetic, International Congress on Logic, Information and the Philosophy of Science (E. Nagel, Ed.), 1, Stanford University Press, 1962.
• [6] Cover, T., Thomas, J.: Elements of Information Theory, John Wiley, 1991.
• [7] Crochemore, M., Mignoni, F., Restive, A., Salemi, S.: Text compression using antidictionaries, 26th International Colloquium on Automata, Languages and Programming, ICALP’99, Prague, July 11-15, 1999, LNCS 1644, Springer Verlag, 1999.
• [8] Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, Springer-Verlag, 1991.
• [9] Elgot, C.: Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, 98, 1961, 21-52.
• [10] Farach, M., Thorup, J.: String matching in Lempel-Ziv compressed strings, ACM Symposium on the Theory of Computing, 1995.
• [11] Feigenbaum, J., Kannan, S., Vardi, M. Y., and, M. V.: The Complexity of Problems on Graphs Represented as OBDDs, Chicago Journal of Theoretical Computer Science, 1999.
• [12] Galperin, H., Wigderson, A.: Succinct representations of Graphs, Information and Control, 56, 1983, 183-198.
• [13] Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient Algorithms for Lempel-Ziv Encoding, 5th Scandinavian Workshop on Algorithm Theory (SWAT’96), LNCS 1097, Springer Verlag, 1996.
• [14] Kida, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: A Unifying Framework for Compressed Pattern Matching, 6th International Symposium on String Processing and Informational Retrieval, IEEE Computer Society, 1999.
• [15] Laplante, S., Lassaigne, R., Magniez, F., Peyronnet, S., de Rougemont, M.: Probabilistic abstraction for model checking: An approach based on property testing, 17th Annual IEEE Symposium on Logic In Computer Science, LICS’2002, Copenhagen, Computer Society Press, 2002.
• [16] Leiß, H., de Rougemont, M.: Automata on Lempel-Ziv Compressed Strings, Computer Science Logic, CSL’03, Wien, 2003 (to appear).
• [17] Manber, U.: A text compression scheme that allows fast searching directly in the compressed file, 5th Annual Symposium on Combinatorial Pattern Matching, CPM’94, LNCS 807, Springer Verlag, 1994
• [18] McNaughton, R.: Elementary computability, formal languages, and automata, Prentice-Hall, Englewood Cliffs, N.J., 1982.
• [19] Navarro, G.: Regular Expression Searching on Compressed Text, Journal of Discrete Algorithms, 2003 (to appear).
• [20] Navarro, G., Raffinot, M.: A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text, 10th Annual Symposium on Combinatorial Pattern Matching, CPM’99, LNCS 1645, Springer Verlag, 1999.
• [21] Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Pattern Matching in Text Compression by Using Antidictionaries, 10th Annual Symposium on Combinatorial Pattern Matching, CPM’99, LNCS 1645, Springer Verlag, 1999.
• [22] Ziv, J., Lempel, A.: A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, 1977, 337-343.
• [23] Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, 1978, 530-536