{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:51:17Z","timestamp":1725565877500},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228493"},{"type":"electronic","value":"9783540278368"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_76","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"906-918","source":"Crossref","is-referenced-by-count":9,"title":["Word Problems on Compressed Words"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"76_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci.\u00a038, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"76_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0028550","volume-title":"STACS 98","author":"D.A.M. Barrington","year":"1998","unstructured":"Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC0 hierarchy. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 73\u201383. Springer, Heidelberg (1998)"},{"key":"76_CR3","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF00271645","volume":"21","author":"G. Bauer","year":"1984","unstructured":"Bauer, G., Otto, F.: Finite complete rewriting systems and the complexity of the word problem. Acta Inf.\u00a021, 521\u2013540 (1984)","journal-title":"Acta Inf."},{"issue":"3","key":"76_CR4","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1016\/S0304-3975(02)00070-1","volume":"290","author":"M. Beaudry","year":"2003","unstructured":"Beaudry, M., Holzer, M., Niemann, G., Otto, F.: McNaughton families of languages. Theor. Comput. Sci.\u00a0290(3), 1581\u20131628 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"76_CR5","doi-asserted-by":"publisher","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 monoids: From word to circuit evaluation. SIAM J. Comput.\u00a026(1), 138\u2013152 (1997)","journal-title":"SIAM J. Comput."},{"key":"76_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0012-365X(84)90177-8","volume":"48","author":"R.V. Book","year":"1984","unstructured":"Book, R.V.: Homogeneous Thue systems and the Church\u2013Rosser property. Discrete Math.\u00a048, 137\u2013145 (1984)","journal-title":"Discrete Math."},{"key":"76_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-10856-4_87","volume-title":"Mathematical Foundations of Computer Science 1981","author":"R.V. Book","year":"1981","unstructured":"Book, R.V., Jantzen, M., Monien, B., \u00d3\u2019D\u00fanlaing, C.P., Wrathall, C.: On the complexity of word problems in certain Thue systems. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol.\u00a0118, pp. 216\u2013223. Springer, Heidelberg (1981)"},{"key":"76_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String\u2013Rewriting Systems","author":"R.V. Book","year":"1993","unstructured":"Book, R.V., Otto, F.: String\u2013Rewriting Systems. Springer, Heidelberg (1993)"},{"key":"76_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm Theory - SWAT \u201996","author":"L. Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996) (extended abstract)"},{"key":"76_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/3-540-57163-9_25","volume-title":"Fundamentals of Computation Theory","author":"M. Holzer","year":"1993","unstructured":"Holzer, M., Lange, K.-J.: On the complexities of linear LL(1) and LR(1) grammars. In: \u00c9sik, Z. (ed.) FCT 1993. LNCS, vol.\u00a0710, pp. 299\u2013308. Springer, Heidelberg (1993)"},{"issue":"3","key":"76_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"Krentel, M.W.: The complexity of optimization problems. J. Comput. Syst. Sci.\u00a036(3), 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"76_CR12","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(92)90004-3","volume":"44","author":"T. Lengauer","year":"1992","unstructured":"Lengauer, T., Wanke, E.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci.\u00a044, 63\u201393 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"76_CR13","doi-asserted-by":"crossref","unstructured":"Lewis II, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Proc. Sixth Annual IEEE Symp. on Switching Circuit Theory and Logic Design, pp. 191\u2013202 (1965)","DOI":"10.1109\/FOCS.1965.14"},{"issue":"3","key":"76_CR14","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R.J. Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. Assoc. Comput. Mach.\u00a024(3), 522\u2013526 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"key":"76_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/10721975_12","volume-title":"Rewriting Techniques and Applications","author":"M. Lohrey","year":"2000","unstructured":"Lohrey, M.: Word problems and confluence problems for restricted semi-Thue systems. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol.\u00a01833, pp. 172\u2013186. Springer, Heidelberg (2000)"},{"key":"76_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/3-540-44683-4_44","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M. Lohrey","year":"2001","unstructured":"Lohrey, M.: Word problems for 2-homogeneous monoids and symmetric logspace. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 500\u2013511. Springer, Heidelberg (2001)"},{"key":"76_CR17","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"76_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"76_CR19","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 262\u2013272. Springer, Heidelberg (1999)"},{"key":"76_CR20","unstructured":"Robinson, D.: Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego (1993)"},{"issue":"11","key":"76_CR21","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.1109\/5.892712","volume":"88","author":"W. Rytter","year":"2000","unstructured":"Rytter, W.: Compressed and fully compressed pattern matching in one and two dimensions. Proc. IEEE\u00a088(11), 1769\u20131778 (2000)","journal-title":"Proc. IEEE"},{"key":"76_CR22","first-page":"61","volume-title":"Proc. STOC 1983","author":"M. Sipser","year":"1983","unstructured":"Sipser, M.: Borel sets and circuit complexity. In: Proc. STOC 1983, pp. 61\u201369. ACM Press, New York (1983)"},{"issue":"1","key":"76_CR23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1090\/S0273-0979-1982-14963-1","volume":"6","author":"J. Stillwell","year":"1982","unstructured":"Stillwell, J.: The word problem and the isomorphism problem for groups. Bull. Am. Math. Soc., New Ser.\u00a06(1), 33\u201356 (1982)","journal-title":"Bull. Am. Math. Soc., New Ser."},{"issue":"3","key":"76_CR24","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I.H. Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context\u2013free languages. J. Assoc. Comput. Mach.\u00a025(3), 405\u2013414 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"76_CR25","first-page":"207","volume":"142","author":"H. Veith","year":"1998","unstructured":"Veith, H.: Succinct representation, leaf languages, and projection reductions. Inf. Control\u00a0142(2), 207\u2013236 (1998)","journal-title":"Inf. Control"},{"issue":"3","key":"76_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K.W. Wagner","year":"1986","unstructured":"Wagner, K.W.: The complexity of combinatorial problems with succinct input representation. Acta Inf.\u00a023(3), 325\u2013356 (1986)","journal-title":"Acta Inf."},{"key":"76_CR27","first-page":"132","volume-title":"Proc. DCC 2002","author":"Y. Zhang","year":"2002","unstructured":"Zhang, Y., Gupta, R.: Path matching in compressed control flow traces. In: Proc. DCC 2002, pp. 132\u2013141. IEEE Computer Society Press, Los Alamitos (2002)"},{"issue":"3","key":"76_CR28","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. on Inf. Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. on Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:31:05Z","timestamp":1620012665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}