nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Recompression: Technique for Word Equations and Compressed Data

verfasst von : Artur Jeż

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation \(u = v\), where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space.

The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Approaching Arithmetic Theories with Finite-State Automata

Nächstes Kapitel How to Prove that a Language Is Regular or Star-Free?

Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Shmoys, D.B. (ed.) SODA, pp. 819–828. ACM/SIAM (2000). https://doi.org/10.1145/338219.338645, http://dl.acm.org/citation.cfm?id=338219.338645

Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst. 33(4–5), 456–474 (2008)CrossRef

Büchi, J.R., Senger, S.: Definability in the existential theory of concatenation and undecidable extensions of this theory. Math. Log. Q. 34(4), 337–342 (1988). https://doi.org/10.1002/malq.19880340410MathSciNetCrossRefMATH

Charatonik, W., Pacholski, L.: Word equations with two variables. In: IWWERT, pp. 43–56 (1991). https://doi.org/10.1007/3-540-56730-5_30

Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554–2576 (2005). https://doi.org/10.1109/TIT.2005.850116MathSciNetCrossRefMATH

Ciobanu, L., Diekert, V., Elder, M.: Solution sets for equations over free groups are EDT0L languages. IJAC 26(5), 843–886 (2016). https://doi.org/10.1142/S0218196716500363MathSciNetCrossRefMATH

Comon, H.: Completion of rewrite systems with membership constraints. Part I: deduction rules. J. Symb. Comput. 25(4), 397–419 (1998). https://doi.org/10.1006/jsco.1997.0185CrossRefMATH

Comon, H.: Completion of rewrite systems with membership constraints. Part II: constraint solving. J. Symb. Comput. 25(4), 421–453 (1998). https://doi.org/10.1006/jsco.1997.0186CrossRefMATH

Creus, C., Gascón, A., Godoy, G.: One-context unification with STG-compressed terms is in NP. In: Tiwari, A. (ed.) 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). LIPIcs, vol. 15, pp. 149–164. Schloss Dagstuhl – Leibniz Zentrum fuer Informatik, Dagstuhl, Germany (2012). https://doi.org/10.4230/LIPIcs.RTA.2012.149, http://drops.dagstuhl.de/opus/volltexte/2012/3490

10.

Da̧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). https://doi.org/10.1007/978-3-540-27836-8_36CrossRef

11.

Da̧browski, R., Plandowski, W.: On word equations in one variable. Algorithmica 60(4), 819–828 (2011). https://doi.org/10.1007/s00453-009-9375-3MathSciNetCrossRefMATH

12.

Diekert, V., Elder, M.: Solutions of twisted word equations, EDT0L languages, and context-free groups. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) ICALP. LIPIcs, vol. 80, pp. 96:1–96:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.ICALP.2017.96

13.

Diekert, V., Gutiérrez, C., Hagenah, C.: The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. Comput. 202(2), 105–140 (2005). http://dx.doi.org/10.1016/j.ic.2005.04.002

14.

Diekert, V., Jeż, A., Plandowski, W.: Finding all solutions of equations in free groups and monoids with involution. Inf. Comput. 251, 263–286 (2016). https://doi.org/10.1016/j.ic.2016.09.009

15.

Diekert, V., Muscholl, A.: Solvability of equations in free partially commutative groups is decidable. Int. J. Algebr. Comput. 16, 1047–1070 (2006). https://doi.org/10.1142/S0218196706003372. Conference version in Proceedings of ICALP 2001, pp. 543-554, LNCS 2076CrossRefMATH

16.

Farmer, W.M.: Simple second-order languages for which unification is undecidable. Theor. Comput. Sci. 87(1), 25–41 (1991). https://doi.org/10.1016/S0304-3975(06)80003-4MathSciNetCrossRefMATH

17.

Gascón, A., Godoy, G., Schmidt-Schauß, M.: Context matching for compressed terms. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24–27 June 2008, Pittsburgh, PA, USA, pp. 93–102. IEEE Computer Society (2008). https://doi.org/10.1109/LICS.2008.17

18.

Gascón, A., Godoy, G., Schmidt-Schauß, M.: Unification and matching on compressed terms. ACM Trans. Comput. Log. 12(4), 26 (2011). https://doi.org/10.1145/1970398.1970402MathSciNetCrossRefMATH

19.

Gascón, A., Godoy, G., Schmidt-Schauß, M., Tiwari, A.: Context unification with one context variable. J. Symb. Comput. 45(2), 173–193 (2010). https://doi.org/10.1016/j.jsc.2008.10.005MathSciNetCrossRefMATH

20.

Gasieniec, L., Karpiński, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: SWAT, pp. 392–403 (1996). https://doi.org/10.1007/3-540-61422-2_148

21.

Gasieniec, L., Karpiński, M., Plandowski, W., Rytter, W.: Randomized efficient algorithms for compressed strings: the finger-print approach. In: CPM, pp. 39–49 (1996). https://doi.org/10.1007/3-540-61258-0_3

22.

Gasieniec, L., Rytter, W.: Almost optimal fully LZW-compressed pattern matching. In: DCC, pp. 316–325. IEEE Computer Society (1999)

23.

Gawrychowski, P.: Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 421–432. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23719-5_36CrossRef

24.

Gawrychowski, P.: Tying up the loose ends in fully LZW-compressed pattern matching. In: Dürr, C., Wilke, T. (eds.) STACS. LIPIcs, vol. 14, pp. 624–635. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012). https://doi.org/10.4230/LIPIcs.STACS.2012.624

25.

Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. ACM Trans. Algorithms 9(3), 25 (2013). https://doi.org/10.1145/2483699.2483705MathSciNetCrossRefMATH

26.

Goldfarb, W.D.: The undecidability of the second-order unification problem. Theor. Comput. Sci. 13, 225–230 (1981). https://doi.org/10.1016/0304-3975(81)90040-2MathSciNetCrossRefMATH

27.

Gutiérrez, C.: Satisfiability of word equations with constants is in exponential space. In: FOCS, pp. 112–119 (1998). https://doi.org/10.1109/SFCS.1998.743434

28.

Ilie, L., Plandowski, W.: Two-variable word equations. ITA 34(6), 467–501 (2000). https://doi.org/10.1051/ita:2000126MathSciNetCrossRefMATH

29.

Jaffar, J.: Minimal and complete word unification. J. ACM 37(1), 47–85 (1990)MathSciNetCrossRef

30.

Jeż, A.: The complexity of compressed membership problems for finite automata. Theory Comput. Syst. 55, 685–718 (2014). https://doi.org/10.1007/s00224-013-9443-6

31.

Jeż, A.: Context unification is in PSPACE. In: Koutsoupias, E., Esparza, J., Fraigniaud, P. (eds.) ICALP. LNCS, vol. 8573, pp. 244–255. Springer (2014). https://doi.org/10.1007/978-3-662-43951-7_21, full version at http://arxiv.org/abs/1310.4367

32.

Jeż, A.: Approximation of grammar-based compression via recompression. Theor. Comput. Sci. 592, 115–134 (2015). https://doi.org/10.1016/j.tcs.2015.05.027

33.

Jeż, A.: Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms 11(3), 20:1–20:43 (2015). https://doi.org/10.1145/2631920MathSciNetCrossRefMATH

34.

Jeż, A.: A really simple approximation of smallest grammar. Theor. Comput. Sci. 616, 141–150 (2016). https://doi.org/10.1016/j.tcs.2015.12.032MathSciNetCrossRefMATH

35.

Jeż, A.: One-variable word equations in linear time. Algorithmica 74, 1–48 (2016). https://doi.org/10.1007/s00453-014-9931-3MathSciNetCrossRefMATH

36.

Jeż, A.: Recompression: a simple and powerful technique for word equations. J. ACM 63(1), 4:1–4:51 (2016). https://doi.org/10.1145/2743014MathSciNetCrossRefMATH

37.

Jeż, A.: Word equations in nondeterministic linear space. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) ICALP. LIPIcs, vol. 80, pp. 95:1–95:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.ICALP.2017.95

38.

Jeż, A., Lohrey, M.: Approximation of smallest linear tree grammar. Inf. Comput. 251, 215–251 (2016). https://doi.org/10.1016/j.ic.2016.09.007MathSciNetCrossRefMATH

39.

Kärkkäinen, J., Mikkola, P., Kempa, D.: Grammar precompression speeds up Burrows–Wheeler compression. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 330–335. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34109-0_34CrossRef

40.

Karpinski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 205–214. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60044-2_44CrossRef

41.

Kharlampovich, O., Myasnikov, A.: Irreducible affine varieties over a free group. II: systems in triangular quasi-quadratic form and description of residually free groups. J. Algebra 200, 517–570 (1998)MathSciNetCrossRef

42.

Kharlampovich, O., Myasnikov, A.: Elementary theory of free non-abelian groups. J. Algebra 302, 451–552 (2006)MathSciNetCrossRef

43.

Kościelski, A., Pacholski, L.: Complexity of Makanin’s algorithm. J. ACM 43(4), 670–684 (1996). https://doi.org/10.1145/234533.234543MathSciNetCrossRefMATH

44.

Kościelski, A., Pacholski, L.: Makanin’s algorithm is not primitive recursive. Theor. Comput. Sci. 191(1–2), 145–156 (1998). https://doi.org/10.1016/S0304-3975(96)00321-0MathSciNetCrossRefMATH

45.

Laine, M., Plandowski, W.: Word equations with one unknown. Int. J. Found. Comput. Sci. 22(2), 345–375 (2011). https://doi.org/10.1142/S0129054111008088MathSciNetCrossRefMATH

46.

Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296–305 (1999). https://doi.org/10.1109/DCC.1999.755679

47.

Levy, J.: Linear second-order unification. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 332–346. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61464-8_63CrossRef

48.

Levy, J., Schmidt-Schauß, M., Villaret, M.: On the complexity of bounded second-order unification and stratified context unification. Log. J. IGPL 19(6), 763–789 (2011). https://doi.org/10.1093/jigpal/jzq010MathSciNetCrossRefMATH

49.

Levy, J., Veanes, M.: On the undecidability of second-order unification. Inf. Comput. 159(1–2), 125–150 (2000). https://doi.org/10.1006/inco.2000.2877MathSciNetCrossRefMATH

50.

Levy, J., Villaret, M.: Linear second-order unification and context unification with tree-regular constraints. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol. 1833, pp. 156–171. Springer, Heidelberg (2000). https://doi.org/10.1007/10721975_11CrossRefMATH

51.

Levy, J., Villaret, M.: Currying second-order unification problems. In: Tison, S. (ed.) RTA 2002. LNCS, vol. 2378, pp. 326–339. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45610-4_23CrossRef

52.

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). https://doi.org/10.1007/978-3-540-73437-6_24CrossRef

53.

Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241–299 (2012)MathSciNetCrossRef

54.

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

55.

Makanin, G.: Equations in a free group. Izv. Akad. Nauk SSR Ser. Math. 46, 1199–1273 (1983). English translation in Math. USSR Izv. 21 (1983)

56.

Makanin, G.: Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR Ser. Mat. 48, 735–749 (1984). in Russian. English translation. In: Math. USSR Izvestija 25(75–88) (1985)

57.

Matiyasevich, Y.: Some decision problems for traces. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol. 1234, pp. 248–257. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63045-7_25CrossRef

58.

Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183–198 (1997). https://doi.org/10.1007/BF02522825MathSciNetCrossRefMATH

59.

Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 1–11. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63220-4_45CrossRef

60.

Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artif. Intell. Res. (JAIR) 7, 67–82 (1997). https://doi.org/10.1613/jair.374CrossRefMATH

61.

Niehren, J., Pinkal, M., Ruhrberg, P.: On equality up-to constraints over finite trees, context unification, and one-step rewriting. In: McCune, W. (ed.) CADE 1997. LNCS, vol. 1249, pp. 34–48. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63104-6_4CrossRef

62.

Niehren, J., Pinkal, M., Ruhrberg, P.: A uniform approach to under specification and parallelism. In: Cohen, P.R., Wahlster, W. (eds.) ACL, pp. 410–417. Morgan Kaufmann Publishers/ACL (1997). https://doi.org/10.3115/979617.979670

63.

Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460–470. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0049431CrossRef

64.

Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: STOC, pp. 721–725. ACM (1999). https://doi.org/10.1145/301250.301443

65.

Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM 51(3), 483–496 (2004). https://doi.org/10.1145/990308.990312MathSciNetCrossRefMATH

66.

Plandowski, W.: An efficient algorithm for solving word equations. In: Kleinberg, J.M. (ed.) STOC, pp. 467–476. ACM (2006). https://doi.org/10.1145/1132516.1132584

67.

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

68.

Razborov, A.A.: On systems of equations in free groups. Ph.D. thesis, Steklov Institute of Mathematics (1987). (in Russian)

69.

Robinson, J.A.: A machine-oriented logic based on the resolution principle. J. ACM 12(1), 23–41 (1965)MathSciNetCrossRef

70.

Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1–3), 211–222 (2003). https://doi.org/10.1016/S0304-3975(02)00777-6MathSciNetCrossRefMATH

71.

Saarela, A.: On the complexity of Hmelevskii’s theorem and satisfiability of three unknown equations. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 443–453. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02737-6_36CrossRef

72.

Sahinalp, S.C., Vishkin, U.: Symmetry breaking for suffix tree construction. In: Leighton, F.T., Goodrich, M.T. (eds.) SODA, pp. 300–309. ACM (1994). https://doi.org/10.1145/195058.195164

73.

Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms 3(2–4), 416–430 (2005). https://doi.org/10.1016/j.jda.2004.08.016MathSciNetCrossRefMATH

74.

Schmidt-Schauß, M.: Unification of stratified second-order terms (1994). Internal Report 12/94, Johann-Wolfgang-Goethe-Universität

75.

Schmidt-Schauß, M.: A decision algorithm for stratified context unification. J. Log. Comput. 12(6), 929–953 (2002). https://doi.org/10.1093/logcom/12.6.929MathSciNetCrossRefMATH

76.

Schmidt-Schauß, M.: Decidability of bounded second order unification. Inf. Comput. 188(2), 143–178 (2004). https://doi.org/10.1016/j.ic.2003.08.002MathSciNetCrossRefMATH

77.

Schmidt-Schauß, M., Schulz, K.U.: On the exponent of periodicity of minimal solutions of context equations. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol. 1379, pp. 61–75. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0052361CrossRef

78.

Schmidt-Schauß, M., Schulz, K.U.: Solvability of context equations with two context variables is decidable. J. Symb. Comput. 33(1), 77–122 (2002). https://doi.org/10.1006/jsco.2001.0438MathSciNetCrossRefMATH

79.

Schulz, K.U.: Makanin’s algorithm for word equations-two improvements and a generalization. In: Schulz, K.U. (ed.) IWWERT 1990. LNCS, vol. 572, pp. 85–150. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55124-7_4CrossRef

80.

Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: STOC, pp. 30–39 (1978)

Titel: Recompression: Technique for Word Equations and Compressed Data
verfasst von: Artur Jeż
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"