References

  1. 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.
  2. Franz Baader & Tobias Nipkow (1998): Term Rewriting and All That. Cambridge University Press, New York, NY, USA.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. Yury Lifshits (2007): Processing Compressed Texts: A Tractability Border. In: CPM 2007, LNCS 4580. Springer, pp. 228–240. Available at http://dx.doi.org/10.1007/978-3-540-73437-6_24.
  16. Markus Lohrey (2012): Algorithmics on SLP-compressed strings. A survey. Groups Complexity Cryptology 4(2), pp. 241–299, doi:10.1515/gcc-2012-0016.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. Manfred Schmidt-Schauss (2013): Linear Pattern Matching of Compressed Terms and Polynomial Rewriting. Accepted for publication, 2013.
  24. 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.
  25. 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.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org