Martin Avanzini & Georg Moser (2010):
Closing the Gap Between Runtime Complexity and Polytime Computability.
In: Christopher Lynch: 21st RTA,
LIPIcs 6.
Schloss Dagstuhl,
Germany,
pp. 33–48,
doi:10.4230/LIPIcs.RTA.2010.33.
Franz Baader & Tobias Nipkow (1998):
Term Rewriting and All That.
Cambridge University Press,
New York, NY, USA.
Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski & Wojciech Rytter (2002):
On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
J. Comput. Syst. Sci. 65(2),
pp. 332–350,
doi:10.1006/jcss.2002.1852.
Giorgio Busatto, Markus Lohrey & Sebastian Maneth (2005):
Efficient Memory Representation of XML Documents.
In: Proceedings of DBPL 2005,
LNCS 3774,
pp. 199–216,
doi:10.1007/11601524_13.
Giorgio Busatto, Markus Lohrey & Sebastian Maneth (2008):
Efficient Memory Representation of XML Document Trees.
Information Systems 33(4–5),
pp. 456–474,
doi:10.1016/j.is.2008.01.004.
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison & M. Tommasi (1997):
Tree Automata Techniques and Applications.
Available at http://www.grappa.univ-lille3.fr/tata.
Release October 2002.
Adrià Gascón, Guillem Godoy & Manfred Schmidt-Schauß (2008):
Context Matching for Compressed Terms.
In: 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008).
IEEE Computer Society,
pp. 93–102,
doi:10.1109/LICS.2008.17.
Adrià Gascón, Guillem Godoy & Manfred Schmidt-Schauß (2011):
Unification and matching on compressed terms.
ACM Trans. Comput. Log. 12(4),
pp. 26:1–26:37.
Available at http://doi.acm.org/10.1145/1970398.1970402.
Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski & Wojciech Rytter (1996):
Efficient Algorithms for Lempel-Ziv Encoding (Extended Abstract).
In: Rolf G. Karlsson & Andrzej Lingas: SWAT,
Lecture Notes in Computer Science 1097.
Springer,
pp. 392–403,
doi:10.1007/3-540-61422-2_148.
Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski & Wojciech Rytter (1996):
Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract).
In: 7th CPM 96,
Lecture Notes in Computer Science 1075.
Springer,
pp. 39–49,
doi:10.1007/3-540-61258-0_3.
Artur Jez (2012):
Faster Fully Compressed Pattern Matching by Recompression.
In: ICALP (1),
Lecture Notes in Computer Science 7391.
Springer,
pp. 533–544,
doi:10.1007/978-3-642-31594-7_45.
Marek Karpinski, Wojciech Rytter & Ayumi Shinohara (1995):
Pattern-matching for strings with short description.
In: CPM '95,
LNCS 937.
Springer-Verlag,
pp. 205–214,
doi:10.1007/3-540-60044-2_44.
Jordi Levy, Manfred Schmidt-Schauß & Mateu Villaret (2006):
Bounded Second-Order Unification is NP-complete.
In: Term Rewriting and Applications (RTA-17),
LNCS 4098.
Springer,
pp. 400–414,
doi:10.1007/11805618_30.
Jordi Levy, Manfred Schmidt-Schauß & Mateu Villaret (2008):
The Complexity of Monadic Second-Order Unification.
SIAM J. of Computing 38(3),
pp. 1113–1140,
doi:10.1137/050645403.
Markus Lohrey (2012):
Algorithmics on SLP-compressed strings. A survey.
Groups Complexity Cryptology 4(2),
pp. 241–299,
doi:10.1515/gcc-2012-0016.
Markus Lohrey, Sebastian Maneth & Manfred Schmidt-Schauß (2009):
Parameter Reduction in Grammar-Compressed Trees.
In: 12th FoSSaCS,
LNCS 5504.
Springer,
pp. 212–226,
doi:10.1007/978-3-642-00596-1_16.
Markus Lohrey, Sebastian Maneth & Manfred Schmidt-Schauß (2012):
Parameter reduction and automata evaluation for grammar-compressed trees.
J. Comput. Syst. Sci. 78(5),
pp. 1651–1669,
doi:10.1016/j.jcss.2012.03.003.
Wojciech Plandowski (1994):
Testing equivalence of morphisms in context-free languages.
In: ESA 94,
Lecture Notes in Computer Science 855,
pp. 460–470,
doi:10.1007/BFb0049431.
Wojciech Plandowski & Wojciech Rytter (1999):
Complexity of Language Recognition Problems for Compressed Words.
In: Jewels are Forever.
Springer,
pp. 262–272,
doi:10.1007/978-3-642-60207-8_23.
Wojciech Rytter (2004):
Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input.
In: J. Diaz et. al.: ICALP 2004,
LNCS 3142.
Springer-Verlag,
pp. 15–27,
doi:10.1007/978-3-540-27836-8_5.
Manfred Schmidt-Schauß (2005):
Polynomial Equality Testing for Terms with Shared Substructures.
Frank report 21.
Institut für Informatik. FB Informatik und Mathematik. Goethe-Universität Frankfurt.
Manfred Schmidt-Schauss (2013):
Linear Pattern Matching of Compressed Terms and Polynomial Rewriting.
Accepted for publication, 2013.
Manfred Schmidt-Schauss & Georg Schnitger (2012):
Fast Equality Test for Straight-Line Compressed Strings.
Information processing letters,
doi:10.1016/j.ipl.2012.01.008.
Jacob Ziv & Abraham Lempel (1977):
A Universal Algorithm for Sequential Data Compression.
IEEE Transactions on Information Theory 23(3),
pp. 337–343,
doi:10.1109/TIT.1977.1055714.