{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:48Z","timestamp":1725490248915},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540745099"},{"type":"electronic","value":"9783540745105"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74510-5_26","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T11:11:35Z","timestamp":1187694695000},"page":"249-258","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Computation in Groups Via Compression"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]},{"given":"Saul","family":"Schleimer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01917515","volume":"38","author":"A. Baudisch","year":"1981","unstructured":"Baudisch, A.: Subgroups of semifree groups. Acta Math. Acad. Sci. Hungar.\u00a038, 19\u201328 (1981)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"issue":"2","key":"26_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01179785","volume":"153","author":"G. Baumslag","year":"1977","unstructured":"Baumslag, G., Cannonito, F.B., Miller III, C.F.: Infinitely generated subgroups of finitely presented groups. Math. Z.\u00a0153(2), 117\u2013134 (1977)","journal-title":"Math. Z."},{"issue":"1","key":"26_CR3","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":"26_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1090\/S0002-9947-00-02506-X","volume":"353","author":"N. Brady","year":"2001","unstructured":"Brady, N., Meier, J.: Connectivity at infinity for right angled Artin groups. Trans. Amer. Math. Soc.\u00a0353, 117\u2013132 (2001)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2","key":"26_CR5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.2140\/pjm.1975.61.351","volume":"61","author":"F.B. Cannonito","year":"1975","unstructured":"Cannonito, F.B., Gatterdam, R.W.: The word problem and power problem in 1-relator groups are primitive recursive. Pacific J. Math.\u00a061(2), 351\u2013359 (1975)","journal-title":"Pacific J. Math."},{"issue":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1093\/qmath\/2.1.123","volume":"2","author":"W.H. Cockcroft","year":"1951","unstructured":"Cockcroft, W.H.: The word problem in a group extension. Quart. J. Math. Oxford Ser.\u00a02(2), 123\u2013134 (1951)","journal-title":"Quart. J. Math. Oxford Ser."},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.2140\/agt.2004.4.439","volume":"4","author":"J. Crisp","year":"2004","unstructured":"Crisp, J., Wiest, B.: Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups. Algebr. Geom. Topol.\u00a04, 439\u2013472 (2004)","journal-title":"Algebr. Geom. Topol."},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-53031-2","volume-title":"Combinatorics on Traces","author":"V. Diekert","year":"1990","unstructured":"Diekert, V.: Combinatorics on Traces. LNCS, vol.\u00a0454. Springer, Heidelberg (1990)"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(90)90003-Z","volume":"74","author":"V. Diekert","year":"1990","unstructured":"Diekert, V.: Word problems over traces which are solvable in linear time. Theoret. Comput. Sci.\u00a074, 3\u201318 (1990)","journal-title":"Theoret. Comput. Sci."},{"volume-title":"The Book of Traces","year":"1995","key":"26_CR10","unstructured":"Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)"},{"issue":"2","key":"26_CR11","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1016\/0021-8693(87)90010-X","volume":"106","author":"C. Droms","year":"1985","unstructured":"Droms, C.: Graph groups, coherence and three-manifolds. J. Algebra\u00a0106(2), 484\u2013489 (1985)","journal-title":"J. Algebra"},{"key":"26_CR12","doi-asserted-by":"crossref","DOI":"10.1201\/9781439865699","volume-title":"Word processing in groups","author":"D.B.A. Epstein","year":"1992","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word processing in groups. Jones and Bartlett, Boston (1992)"},{"key":"26_CR13","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 (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"26_CR14","unstructured":"Green, E.R.: Graph Products of Groups. PhD thesis, The University of Leeds (1990)"},{"key":"26_CR15","unstructured":"Hagenah, C.: Gleichungen mit regul\u00e4ren Randbedingungen \u00fcber freien Gruppen. PhD thesis, University of Stuttgart, Institut f\u00fcr Informatik (2000)"},{"issue":"1","key":"26_CR16","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O.H. Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach.\u00a030(1), 217\u2013228 (1983)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"26_CR17","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","volume":"264","author":"I. Kapovich","year":"2003","unstructured":"Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory, and random walks. J. Algebra\u00a0264(2), 665\u2013694 (2003)","journal-title":"J. Algebra"},{"issue":"2","key":"26_CR18","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1112\/jlms\/52.2.318","volume":"52","author":"M.R. Laurence","year":"1995","unstructured":"Laurence, M.R.: A generating set for the automorphism group of a graph group. J. London Math. Soc (2)\u00a052(2), 318\u2013334 (1995)","journal-title":"J. London Math. Soc. (2)"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Lifshits, Y.: Processing compressed texts: a tractability border. In: Proc. CPM 2007. Springer, Heidelberg (to appear, 2007)","DOI":"10.1007\/978-3-540-73437-6_24"},{"issue":"3","key":"26_CR20","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."},{"issue":"5","key":"26_CR21","doi-asserted-by":"publisher","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.\u00a035(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"key":"26_CR22","volume-title":"Combinatorial Group Theory","author":"R.C. Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Heidelberg (1977)"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Combinatorial Pattern Matching","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Hein, J., Apostolico, A. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a01264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"key":"26_CR24","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, London, UK (1994)"},{"key":"26_CR25","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":"26_CR26","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":"26_CR27","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01241140","volume":"120","author":"E. Rips","year":"1995","unstructured":"Rips, E., Sela, Z.: Canonical representatives and equations in hyperbolic groups. Invent. Math.\u00a0120, 489\u2013512 (1995)","journal-title":"Invent. Math."},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Schleimer, S.: Polynomial-time word problems. In: Commentarii Mathematici Helvetici (to appear)","DOI":"10.4171\/CMH\/142"},{"issue":"1","key":"26_CR29","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/0021-8693(89)90319-0","volume":"126","author":"H. Servatius","year":"1989","unstructured":"Servatius, H.: Automorphisms of graph groups. J. Algebra\u00a0126(1), 34\u201360 (1989)","journal-title":"J. Algebra"},{"key":"26_CR30","unstructured":"Simon, H.-U.: Word problems for groups and contextfree recognition. In: Proc. FCT 1979, pp. 417\u2013422. Akademie-Verlag (1979)"},{"key":"26_CR31","volume-title":"Classical Topology and Combinatorial Group Theory","author":"J. Stillwell","year":"1995","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory. Springer, Heidelberg (1995)"},{"issue":"1","key":"26_CR32","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0747-7171(88)80024-5","volume":"6","author":"C. Wrathall","year":"1988","unstructured":"Wrathall, C.: The word problem for free partially commutative groups. J. Symbolic Comput.\u00a06(1), 99\u2013104 (1988)","journal-title":"J. Symbolic Comput."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74510-5_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:21:52Z","timestamp":1619504512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74510-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745099","9783540745105"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74510-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}