{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:58Z","timestamp":1760202658503},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,1,18]],"date-time":"2013-01-18T00:00:00Z","timestamp":1358467200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1007\/s00224-013-9443-6","type":"journal-article","created":{"date-parts":[[2013,1,17]],"date-time":"2013-01-17T10:39:26Z","timestamp":1358419166000},"page":"685-718","source":"Crossref","is-referenced-by-count":13,"title":["The Complexity of Compressed Membership Problems for Finite Automata"],"prefix":"10.1007","volume":"55","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,18]]},"reference":[{"key":"9443_CR1","first-page":"819","volume-title":"Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0819\u2013828 (2000). doi: 10.1145\/338219.338645"},{"key":"9443_CR2","first-page":"705","volume-title":"SODA","author":"A. Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in Z-compressed files. In: SODA, pp.\u00a0705\u2013714 (1994)"},{"issue":"1","key":"9443_CR3","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1137\/S0097539793249530","volume":"26","author":"M. Beaudry","year":"1997","unstructured":"Beaudry, M., McKenzie, P., P\u00e9ladeau, P., Th\u00e9rien, D.: Finite moniods: from word to circuit evaluation. SIAM J. Comput. 26(1), 138\u2013152 (1997)","journal-title":"SIAM J. Comput."},{"key":"9443_CR4","first-page":"373","volume-title":"SODA","author":"P. Bille","year":"2011","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: Randall, D. (ed.) SODA, pp.\u00a0373\u2013389. SIAM, Philadelphia (2011)"},{"issue":"7","key":"9443_CR5","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9443_CR6","first-page":"260","volume-title":"FSTTCS, LIPIcs","author":"W. Czerwi\u0144ski","year":"2010","unstructured":"Czerwi\u0144ski, W., Lasota, S.: Fast equivalence-checking for normed context-free processes. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS, LIPIcs, vol.\u00a08, pp.\u00a0260\u2013271. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Wadern (2010)"},{"key":"9443_CR7","first-page":"703","volume-title":"STOC","author":"M. Farach","year":"1995","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. In: STOC, pp.\u00a0703\u2013712. ACM Press, New York (1995)"},{"key":"9443_CR8","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1145\/301250.301378","volume-title":"STOC","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Muthukrishnan, S., de Berg, M.: Multi-method dispatching: a geometric approach with applications to string matching problems. In: STOC, pp.\u00a0483\u2013491 (1999)"},{"key":"9443_CR9","unstructured":"Gawrychowski, P.: (2011). Personal communication"},{"key":"9443_CR10","first-page":"362","volume-title":"SODA","author":"P. Gawrychowski","year":"2011","unstructured":"Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. In: Randall, D. (ed.) SODA, pp.\u00a0362\u2013372. SIAM, Philadelphia (2011)"},{"key":"9443_CR11","series-title":"LNCS","first-page":"421","volume-title":"ESA","author":"P. Gawrychowski","year":"2011","unstructured":"Gawrychowski, P.: Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA. LNCS, vol.\u00a06942, pp.\u00a0421\u2013432. Springer, Berlin (2011)"},{"key":"9443_CR12","series-title":"LNCS","volume-title":"CPM","author":"P. Gawrychowski","year":"2012","unstructured":"Gawrychowski, P.: Simple and efficient LZW-compressed multiple pattern matching. In: CPM. LNCS Springer, Berlin (2012)"},{"key":"9443_CR13","series-title":"LIPIcs","first-page":"624","volume-title":"STACS","author":"P. Gawrychowski","year":"2012","unstructured":"Gawrychowski, P.: Tying up the loose ends in fully LZW-compressed pattern matching. In: D\u00fcrr, C., Wilke, T. (eds.) STACS, LIPIcs, vol.\u00a014, pp.\u00a0624\u2013635. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Wadern (2012)"},{"issue":"4","key":"9443_CR14","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/s00224-007-9054-1","volume":"42","author":"B. Genest","year":"2008","unstructured":"Genest, B., Muscholl, A.: Pattern matching and membership for hierarchical message sequence charts. Theory Comput. Syst. 42(4), 536\u2013567 (2008). doi: 10.1007\/s00224-007-9054-1","journal-title":"Theory Comput. Syst."},{"key":"9443_CR15","series-title":"LNCS","first-page":"392","volume-title":"SWAT","author":"L. G\u0105sieniec","year":"1996","unstructured":"G\u0105sieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R.G., Lingas, A. (eds.) SWAT. LNCS, vol.\u00a01097, pp.\u00a0392\u2013403. Springer, Berlin (1996)"},{"key":"9443_CR16","series-title":"LNCS","first-page":"39","volume-title":"CPM","author":"L. G\u0105sieniec","year":"1996","unstructured":"G\u0105sieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Randomized efficient algorithms for compressed strings: the finger-print approach (extended abstract). In: Hirschberg, D.S., Myers, E.W. (eds.) CPM. LNCS, vol.\u00a01075, pp.\u00a039\u201349. Springer, Berlin (1996)"},{"key":"9443_CR17","first-page":"316","volume-title":"Data Compression Conference","author":"L. G\u0105sieniec","year":"1999","unstructured":"G\u0105sieniec, L., Rytter, W.: Almost optimal fully LZW-compressed pattern matching. In: Data Compression Conference, pp.\u00a0316\u2013325 (1999)"},{"key":"9443_CR18","series-title":"LNCS","first-page":"533","volume-title":"ICALP","author":"A. Je\u017c","year":"2012","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP. LNCS, vol.\u00a07391, pp.\u00a0533\u2013544. Springer, Berlin (2012)"},{"key":"9443_CR19","volume-title":"STACS 2013 Conference, LIPIcs","author":"A. Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. In: STACS 2013 Conference, LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Wadern (2013). Available at http:\/\/arxiv.org\/abs\/1203.3705"},{"issue":"2","key":"9443_CR20","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s00224-009-9246-y","volume":"48","author":"A. Je\u017c","year":"2011","unstructured":"Je\u017c, A., Okhotin, A.: Complexity of equations over sets of natural numbers. Theory Comput. Syst. 48(2), 319\u2013342 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9443_CR21","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s00224-011-9319-6","volume":"49","author":"A. Je\u017c","year":"2011","unstructured":"Je\u017c, A., Okhotin, A.: One-nonterminal conjunctive grammars over a unary alphabet. Theory Comput. Syst. 49(2), 319\u2013342 (2011)","journal-title":"Theory Comput. Syst."},{"key":"9443_CR22","first-page":"103","volume-title":"Data Compression Conference","author":"T. Kida","year":"1998","unstructured":"Kida, T., Takeda, M., Shinohara, A., Miyazaki, M., Arikawa, S.: Multiple pattern matching in LZW compressed text. In: Data Compression Conference, pp.\u00a0103\u2013112 (1998)"},{"key":"9443_CR23","series-title":"LNCS","first-page":"349","volume-title":"FSTTCS","author":"S.R. Kosaraju","year":"1995","unstructured":"Kosaraju, S.R.: Pattern matching in compressed texts. In: Thiagarajan, P.S. (ed.) FSTTCS. LNCS, vol.\u00a01026, pp.\u00a0349\u2013362. Springer, Berlin (1995)"},{"key":"9443_CR24","series-title":"LNCS","first-page":"646","volume-title":"MFCS","author":"S. Lasota","year":"2006","unstructured":"Lasota, S., Rytter, W.: Faster algorithm for bisimulation equivalence of normed context-free processes. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS. LNCS, vol.\u00a04162, pp.\u00a0646\u2013657. Springer, Berlin (2006). doi: 10.1007\/11821069_56"},{"key":"9443_CR25","volume-title":"Combinatorial and Algorithmic Foundations of Pattern and Association Discovery, Dagstuhl Seminar Proceedings","author":"Y. Lifshits","year":"2006","unstructured":"Lifshits, Y.: Solving classical string problems an compressed texts. In: Ahlswede, R., Apostolico, A., Levenshtein, V.I. (eds.) Combinatorial and Algorithmic Foundations of Pattern and Association Discovery, Dagstuhl Seminar Proceedings, vol.\u00a006201. IBFI, Schloss Dagstuhl, Wadern (2006)"},{"key":"9443_CR26","first-page":"681","volume-title":"MFCS","author":"Y. Lifshits","year":"2006","unstructured":"Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS. LNCS, vol.\u00a04162, pp.\u00a0681\u2013692. Springer, Berlin (2006)"},{"issue":"5","key":"9443_CR27","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006). doi: 10.1137\/S0097539704445950","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9443_CR28","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1142\/S012905411000757X","volume":"21","author":"M. Lohrey","year":"2010","unstructured":"Lohrey, M.: Compressed membership problems for regular expressions and hierarchical automata. Int. J. Found. Comput. Sci. 21(5), 817\u2013841 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"9443_CR29","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M. Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"9443_CR30","series-title":"LNCS","first-page":"275","volume-title":"CSR","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A.S., Vereshchagin, N.K. (eds.) CSR. LNCS, vol.\u00a06651, pp.\u00a0275\u2013288. Springer, Berlin (2011). doi: 10.1007\/978-3-642-20712-9_21"},{"key":"9443_CR31","series-title":"LNCS","first-page":"249","volume-title":"CSR","author":"M. Lohrey","year":"2007","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR. LNCS, vol.\u00a04649, pp.\u00a0249\u2013258. Springer, Berlin (2007). doi: 10.1007\/978-3-540-74510-5_26"},{"issue":"3","key":"9443_CR32","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S021819671000542X","volume":"20","author":"J. MacDonald","year":"2010","unstructured":"MacDonald, J.: Compressed words and automorphisms in fully residually free groups. Int. J. Autom. Comput. 20(3), 343\u2013355 (2010)","journal-title":"Int. J. Autom. Comput."},{"issue":"1","key":"9443_CR33","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.ipl.2004.01.002","volume":"90","author":"N. Markey","year":"2004","unstructured":"Markey, N., Schnoebelen, P.: A\u00a0PTIME-complete matching problem for SLP-compressed words. Inf. Process. Lett. 90(1), 3\u20136 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9443_CR34","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K. Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"9443_CR35","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.jda.2003.12.002","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G., Raffinot, M.: Practical and flexible pattern matching over Ziv-Lempel compressed text. J.\u00a0Discrete Algorithms 2(3), 347\u2013371 (2004)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9443_CR36","series-title":"LNCS","first-page":"460","volume-title":"ESA","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA, LNCS, vol.\u00a0855, pp.\u00a0460\u2013470. Springer, Berlin (1994). doi: 10.1007\/BFb0049431"},{"issue":"3","key":"9443_CR37","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1145\/990308.990312","volume":"51","author":"W. Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM 51(3), 483\u2013496 (2004). doi: 10.1145\/990308.990312","journal-title":"J. ACM"},{"key":"9443_CR38","series-title":"LNCS","first-page":"731","volume-title":"ICALP","author":"W. Plandowski","year":"1998","unstructured":"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. LNCS, vol.\u00a01443, pp.\u00a0731\u2013742. Springer, Berlin (1998). doi: 10.1007\/BFb0055097"},{"key":"9443_CR39","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels Are Forever","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels Are Forever, pp.\u00a0262\u2013272. Springer, Berlin (1999)"},{"issue":"1\u20133","key":"9443_CR40","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9443-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9443-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9443-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T20:16:19Z","timestamp":1714853779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9443-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,18]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["9443"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9443-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,18]]}}}