Recompression: Word Equations and Beyond

1. Charatonik, W., Pacholski, L.: Word equations with two variables. In: Abdulrab, H., Pécuchet, J.P. (eds.) IWWERT 1991. LNCS, vol. 677, pp. 43–56. Springer, Heidelberg (1993)

   Chapter  Google Scholar 

2. Dąbrowski, R., Plandowski, W.: Solving two-variable word equations. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 408–419. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

3. Dąbrowski, R., Plandowski, W.: On word equations in one variable. Algorithmica 60(4), 819–828 (2011)

   Article  MathSciNet  Google Scholar 

4. Jeż, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 533–544. Springer, Heidelberg (2012)

   Chapter  Google Scholar 

5. Jeż, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 165–176. Springer, Heidelberg (2013)

   Google Scholar 

6. Jeż, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1–34 (2013), http://dx.doi.org/10.1007/s00224-013-9443-6

7. Jeż, A.: One-variable word equations in linear time. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS. Springer, Heidelberg (to appear, 2013)

   Google Scholar 

8. Kościelski, A., Pacholski, L.: Complexity of Makanin’s algorithm. J. ACM 43(4), 670–684 (1996)

   Article  MathSciNet  MATH  Google Scholar 

9. Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296–305. IEEE Computer Society (1999)

   Google Scholar 

10. Lifshits, Y.: Processing compressed texts: A tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 228–240. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

11. Lohrey, M.: Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology 4(2), 241–299 (2012)

    MathSciNet  Google Scholar 

12. Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol. 6651, pp. 275–288. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

13. Makanin, G.S.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik 2(103), 147–236 (1977) (in Russian)

    Google Scholar 

14. Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183–198 (1997)

    Article  MathSciNet  MATH  Google Scholar 

15. Obono, S.E., Goralcik, P., Maksimenko, M.N.: Efficient solving of the word equations in one variable. In: Prívara, I., Rovan, B., Ruzicka, P. (eds.) MFCS 1994. LNCS, vol. 841, pp. 336–341. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

16. Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM 51(3), 483–496 (2004)

    MathSciNet  MATH  Google Scholar 

17. Plandowski, W.: An efficient algorithm for solving word equations. In: Kleinberg, J.M. (ed.) STOC, pp. 467–476. ACM (2006)

    Google Scholar 

18. Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of words equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 731–742. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

19. Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms 3(2-4), 416–430 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references