{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T22:27:28Z","timestamp":1648852048663},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,16]],"date-time":"2013-03-16T00:00:00Z","timestamp":1363392000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s00037-012-0058-0","type":"journal-article","created":{"date-parts":[[2013,3,15]],"date-time":"2013-03-15T18:42:06Z","timestamp":1363372926000},"page":"771-830","source":"Crossref","is-referenced-by-count":0,"title":["Space Functions and Space Complexity of the Word Problem in Semigroups"],"prefix":"10.1007","volume":"22","author":[{"given":"A. Yu.","family":"Olshanskii","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,16]]},"reference":[{"key":"58_CR1","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S1446788700007783","volume":"10","author":"G. Baumslag","year":"1969","unstructured":"Baumslag G. (1969) A non-cyclic one-relator group all of whose finite quotients are cyclic. J. Austral. Math. Soc. 10: 497\u2013498","journal-title":"J. Austral. Math. Soc."},{"key":"58_CR2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1142\/S0218196798000132","volume":"8","author":"J.-C. Birget","year":"1998","unstructured":"Birget J.-C. (1998) Time-complexity of the word problem for semigroups and the Higman embedding theorem. Int. J. Algebra Comput. 8: 235\u2013294","journal-title":"Int. J. Algebra Comput."},{"key":"58_CR3","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1142\/S0218196704001815","volume":"14","author":"J.-C. Birget","year":"2004","unstructured":"Birget J.-C. (2004) Functions on groups and computational complexity. Int. J. Algebra Comput. 14: 409\u2013429","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"58_CR4","first-page":"467","volume":"156","author":"J.-C. Birget","year":"2002","unstructured":"Birget J.-C., Olshanskii A.Yu., Rips E., Sapir M.V. (2002) Isoperimetric functions of groups and computational complexity of the word problem. AMII 156(2): 467\u2013518","journal-title":"AMII"},{"key":"58_CR5","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1007\/PL00001646","volume":"10","author":"N. Brady","year":"2000","unstructured":"Brady N., Bridson M. (2000) There is only one gap in the isoperimetric spectrum. Geometric and Functional Analysis 10: 1053\u20131070","journal-title":"Geometric and Functional Analysis"},{"key":"58_CR6","unstructured":"N. Brady, T. Riley & H. Short (2007). The geometry of the word problem for finitely generated groups. Advanced Courses in Mathematics, CRM Barselona. Birkhauser-Verlag, Basel."},{"issue":"1","key":"58_CR7","first-page":"171","volume":"307","author":"M. Bridson","year":"2007","unstructured":"Bridson M., Riley T. (2007) Free and fragmenting filling length. JALG 307(1): 171\u2013190","journal-title":"JALG"},{"issue":"2","key":"58_CR8","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/malq.19930390117","volume":"39","author":"D.E. Cohen","year":"1993","unstructured":"Cohen D.E., Madlener K., Otto F. (1993) Separating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups. Math. Logic Quart. 39(2): 143\u2013157","journal-title":"Math. Logic Quart."},{"key":"58_CR9","unstructured":"Ding-Zhu Du & Ker-I Ko (2000). Theory of Computational Complexity. Wiley, NY."},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"S. Gersten (1992). Dehn functions and l1-norms of finite presentations. In Algorithms and Classification in Combinatorial Group Theory (Berkeley, CA, 1989), 195\u2013224. MSRI 23, SV, New York.","DOI":"10.1007\/978-1-4613-9730-4_9"},{"key":"58_CR11","unstructured":"S. Gersten (1993). Isoperimetric and isodiametric functions. In Geometric group theory I, Lecture Notes of LMS, 181, G. Niblo & M. Roller, editors, 79\u201396. Cambridge University Press."},{"issue":"1","key":"58_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1019682203828","volume":"92","author":"S. Gersten","year":"2002","unstructured":"Gersten S., Riley T. (2002) Filling length in finitely presentable groups. Geometricae Dedicata 92(1): 41\u201358","journal-title":"Geometricae Dedicata"},{"key":"58_CR13","doi-asserted-by":"crossref","unstructured":"M. Gromov (1987). Hyperbolic groups. In Essays in Group Theory, S. Gersten, editor, 75\u2013263. MSRI 8, SV.","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"58_CR14","doi-asserted-by":"crossref","first-page":"1885","DOI":"10.1090\/S0002-9939-99-04579-7","volume":"127","author":"V.S. Guba","year":"1999","unstructured":"Guba V.S., Sapir V.N. (1999) On Dehn functions of free products of groups. PAMS 127: 1885\u20131891","journal-title":"PAMS"},{"issue":"1311","key":"58_CR15","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1098\/rspa.1961.0132","volume":"262","author":"G. Higman","year":"1961","unstructured":"Higman G. (1961) Subgroups of finitely presented groups. Proc. Roy. Soc. 262(1311): 455\u2013475","journal-title":"Proc. Roy. Soc."},{"key":"58_CR16","first-page":"290","volume":"2","author":"E.V. Kashintsev","year":"1970","unstructured":"Kashintsev E.V. (1970) Graphs and the word problem for finitely presented semigroups (in Russian). Uchenye Zapiski Tulskogo Pedagogicheskogo Instituta 2: 290\u2013302","journal-title":"Uchenye Zapiski Tulskogo Pedagogicheskogo Instituta"},{"key":"58_CR17","volume-title":"Combinatorial Group Theory","author":"R.C. Lyndon","year":"1977","unstructured":"Lyndon R.C., Schupp P.E. (1977) Combinatorial Group Theory. Springer, Berlin"},{"key":"58_CR18","first-page":"383","volume":"1","author":"K. Madlener","year":"1985","unstructured":"Madlener K., Otto F. (1985) Pseudo-natural algorithms for the word problem for finitely presented monoids and groups. JSC 1: 383\u2013418","journal-title":"JSC"},{"key":"58_CR19","unstructured":"A. Miasnikov, A. Ushakov & Dong Wook Won (2011). The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. preprint, arXiv: 1102,2481."},{"key":"58_CR20","first-page":"217","volume":"1","author":"V.L. Murskii","year":"1967","unstructured":"Murskii V.L. (1967) Isomorphic embeddability of semigroups with countable sets of defining relations in finitely defined semigroups (in Russian). Matematicheskie Zametki 1: 217\u2013224","journal-title":"Matematicheskie Zametki"},{"key":"58_CR21","unstructured":"A.Yu. Olshanskii (1997). On the subgroup distortion in finitely presented groups (in Russian). MS 188(11), 73\u2013120."},{"issue":"9","key":"58_CR22","doi-asserted-by":"crossref","first-page":"4937","DOI":"10.1090\/S0002-9947-2012-05520-6","volume":"364","author":"A.Yu. Olshanskii","year":"2012","unstructured":"Olshanskii A.Yu. (2012) Space functions of groups. TAMS 364(9): 4937\u20134985","journal-title":"TAMS"},{"key":"58_CR23","unstructured":"A.N. Platonov (2004). Isoperimetric function of the Baumslag\u2013Gersten group (in Russian). Vestnik Moskov. Univ., Ser.1 (3), 12\u201317."},{"key":"58_CR24","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0001-8708(80)90018-3","volume":"36","author":"J.H. Remmers","year":"1980","unstructured":"Remmers J.H. (1980) On the geometry of semigroup presentations. Advances in Math. 36: 283\u2013296","journal-title":"Advances in Math."},{"key":"58_CR25","unstructured":"J. Rotman (1984). An introduction to the theory of groups, 3d edition. Allyn and Bacon, Boston, MA."},{"issue":"2","key":"58_CR26","first-page":"345","volume":"156","author":"M.V. Sapir","year":"2002","unstructured":"Sapir M.V., Birget J.-C., Rips E. (2002) Isoperimetric and isodiametric functions of groups. AMII 156(2): 345\u2013466","journal-title":"AMII"},{"issue":"1","key":"58_CR27","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/BF02219824","volume":"8","author":"B.A. Trakhtenbrot","year":"1969","unstructured":"Trakhtenbrot B.A. (1969) On the complexity of reduction algorithms in Novikov - Boone constructions (in Russian). Algebra i Logika 8(1): 50\u201371","journal-title":"Algebra i Logika"},{"issue":"1","key":"58_CR28","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF02219819","volume":"8","author":"M.K. Valiev","year":"1969","unstructured":"Valiev M.K. (1969) On the complexity of the identity problem for finitely defined groups (in Russian). Algebra i Logika 8(1): 5\u201343","journal-title":"Algebra i Logika"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0058-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0058-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0058-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:58Z","timestamp":1558537318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0058-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,16]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["58"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0058-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,16]]}}}