{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:08:48Z","timestamp":1767236928967,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T00:00:00Z","timestamp":1505174400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00224-017-9808-3","type":"journal-article","created":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T07:10:55Z","timestamp":1505200255000},"page":"192-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Knapsack in Graph Groups"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4680-7198","authenticated-orcid":false,"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,12]]},"reference":[{"key":"9808_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02088289","volume":"22","author":"IJ Aalbersberg","year":"1989","unstructured":"Aalbersberg, I.J., Hoogeboom, H.J.: Characterizations of the decidability of some problems for regular trace languages. Math. Syst. Theory 22, 1\u201319 (1989)","journal-title":"Math. Syst. Theory"},{"key":"9808_CR2","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.4171\/dm\/421","volume":"18","author":"I Agol","year":"2013","unstructured":"Agol, I.: The virtual Haken conjecture. With an appendix by Agol, Daniel Groves, and Jason Manning. Doc. Math. 18, 1045\u20131087 (2013)","journal-title":"Doc. Math."},{"key":"9808_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity \u2014 a modern approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational complexity \u2014 a modern approach. Cambridge University Press, Cambridge (2009)"},{"key":"9808_CR4","unstructured":"Babai, L., Beals, R., Cai, J., Ivanyos, G., Luks, E.M.: Multiplicative equations over commuting matrices. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms SODA 1996, pp 498\u2013507. ACM\/SIAM (1996)"},{"key":"9808_CR5","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0890-5401(89)90051-5","volume":"82","author":"A Bertoni","year":"1989","unstructured":"Bertoni, A., Mauri, G., Sabadini, N.: Membership problems for regular and context free trace languages. Inf. Comput. 82, 135\u2013150 (1989)","journal-title":"Inf. Comput."},{"issue":"3","key":"9808_CR6","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/s002220050168","volume":"129","author":"M Bestvina","year":"1997","unstructured":"Bestvina, M., Brady, N.: Morse theory and finiteness properties of groups. Invent. Math. 129(3), 445\u2013470 (1997)","journal-title":"Invent. Math."},{"issue":"2","key":"9808_CR7","doi-asserted-by":"crossref","first-page":"467","DOI":"10.2307\/3597196","volume":"156","author":"J-C Birget","year":"2002","unstructured":"Birget, J.-C., Ol\u2019shanskii, A.Y., Rips, E., Sapir, M.V.: Isoperimetric functions of groups and computational complexity of the word problem. Ann. Math. Second Ser. 156(2), 467\u2013518 (2002)","journal-title":"Ann. Math. Second Ser."},{"key":"9808_CR8","unstructured":"Bj\u00f6rner, A., Brenti, F.: Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005)"},{"issue":"7","key":"9808_CR9","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., Lehman, A., 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":"9808_CR10","doi-asserted-by":"crossref","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. Algebraic Geom. Topol. 4, 439\u2013472 (2004)","journal-title":"Algebraic Geom. Topol."},{"key":"9808_CR11","doi-asserted-by":"crossref","unstructured":"Diekert, V.: Combinatorics on traces. Lecture Notes in Computer Science, vol. 454. Springer, New York (1990)","DOI":"10.1007\/3-540-53031-2"},{"key":"9808_CR12","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2015.11.009","volume":"75","author":"V Diekert","year":"2016","unstructured":"Diekert, V., Kausch, J.: Logspace computations in graph products. J. Symb. Comput. 75, 94\u2013109 (2016)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"9808_CR13","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1142\/S0218196708004548","volume":"18","author":"V Diekert","year":"2008","unstructured":"Diekert, V., Lohrey, M.: Word equations over graph products. Int. J. Algebra Comput. 18(3), 493\u2013533 (2008)","journal-title":"Int. J. Algebra Comput."},{"issue":"6","key":"9808_CR14","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1142\/S0218196706003372","volume":"16","author":"V Diekert","year":"2006","unstructured":"Diekert, V., Muscholl, A.: Solvability of equations in graph groups is decidable. Int. J. Algebra Comput. 16(6), 1047\u20131069 (2006)","journal-title":"Int. J. Algebra Comput."},{"key":"9808_CR15","doi-asserted-by":"crossref","unstructured":"Diekert, V., Myasnikov, A.G., Wei\u00df, A.: Conjugacy in Baumslag\u2019s group, generic case complexity, and division in power circuiats. In: Symposium of the 11th Latin American Symposium, LATIN 2014. Lecture Notes in Computer Science, vol. 8392, pp 1\u201312. Springer (2014)","DOI":"10.1007\/978-3-642-54423-1_1"},{"key":"9808_CR16","doi-asserted-by":"crossref","unstructured":"Diekert, V., Rozenberg, G. (eds.): The Book of Traces World Scientific (1995)","DOI":"10.1142\/2563"},{"key":"9808_CR17","first-page":"128","volume":"18","author":"M Elberfeld","year":"2011","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Algorithmic meta theorems for circuit classes of constant and logarithmic depth. Electron. Colloq. Comput. Complexity (ECCC) 18, 128 (2011)","journal-title":"Electron. Colloq. Comput. Complexity (ECCC)"},{"key":"9808_CR18","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.jsc.2015.05.006","volume":"74","author":"E Frenkel","year":"2016","unstructured":"Frenkel, E., Nikolaev, A., Ushakov, A.: Knapsack problems in products of groups. J. Symb. Comput. 74, 96\u2013108 (2016)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"9808_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J Von zur Gathen","year":"1978","unstructured":"Von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proc. Amer. Math. Soc. 72(1), 155\u2013158 (1978)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"9808_CR20","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.aam.2005.08.009","volume":"38","author":"R Ghrist","year":"2007","unstructured":"Ghrist, R., Peterson, V.: The geometry and topology of reconfiguration. Adv. Appl. Math. 38(3), 302\u2013323 (2007)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"9808_CR21","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S Greibach","year":"1973","unstructured":"Greibach, S.: The hardest context-free language. SIAM J. Comput. 2(4), 304\u2013310 (1973)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9808_CR22","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"SA Greibach","year":"1965","unstructured":"Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. Assoc. Comput. Mach. 12(1), 42\u201352 (1965)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9808_CR23","unstructured":"Haase, C.: On the complexity of model checking counter automata. PhD thesis, University of Oxford St Catherine\u2019s College (2011)"},{"issue":"5","key":"9808_CR24","doi-asserted-by":"crossref","first-page":"1890","DOI":"10.1016\/j.aim.2010.01.011","volume":"224","author":"F Haglund","year":"2010","unstructured":"Haglund, F., Wise, D.T.: Coxeter groups are virtually special. Adv. Math. 224(5), 1890\u20131903 (2010)","journal-title":"Adv. Math."},{"key":"9808_CR25","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65, 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9808_CR26","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1307\/mmj\/1030132408","volume":"46","author":"T Hsu","year":"1999","unstructured":"Hsu, T., Wise, D.T.: On linear and residual properties of graph products. Mich. Math. J. 46(2), 251\u2013259 (1999)","journal-title":"Mich. Math. J."},{"issue":"1","key":"9808_CR27","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"OH Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach. 30(1), 217\u2013228 (1983)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9808_CR28","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits Derandomizing the XOR Lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, STOC 1997, pp 220\u2013229. ACM Press (1997)","DOI":"10.1145\/258533.258590"},{"key":"9808_CR29","doi-asserted-by":"crossref","unstructured":"Jenner, B.: Knapsack problems for NL. Inf. Process. Lett. 54(3), 169\u2013174 (1995)","DOI":"10.1016\/0020-0190(95)00017-7"},{"key":"9808_CR30","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1080\/00927870802243580","volume":"37","author":"M Kambites","year":"2009","unstructured":"Kambites, M.: Formal languages and groups as memory. Commun. Algebra 37, 193\u2013208 (2009)","journal-title":"Commun. Algebra"},{"key":"9808_CR31","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R. E., Thatcher, J. W. (eds.) Complexity of Computer Computations, pp 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9808_CR32","doi-asserted-by":"crossref","unstructured":"Ko\u0307nig, D., Lohrey, M.: Evaluating matrix circuits. In: Proceedings of the 21st International Conference on Computing and Combinatorics, COCOON 2015. Lecture Notes in Computer Science, vol. 9198, pp 235\u2013248. Springer (2015)","DOI":"10.1007\/978-3-319-21398-9_19"},{"key":"9808_CR33","doi-asserted-by":"crossref","unstructured":"K\u00f6nig, D., Lohrey, M., Zetzsche, G.: Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. In: Algebra and Computer Science. Contemporary Mathematics, vol. 677. AMS (2016)","DOI":"10.1090\/conm\/677\/13625"},{"issue":"2","key":"9808_CR34","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1142\/S0218196706003001","volume":"16","author":"D Kuske","year":"2006","unstructured":"Kuske, D., Lohrey, M.: Logical aspects of Cayley-graphs: the monoid case. Int. J. Algebra Comput. 16(2), 307\u2013340 (2006)","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"9808_CR35","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":"9808_CR36","doi-asserted-by":"crossref","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. SpringerBriefs in Mathematics Springer (2014)","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"9808_CR37","doi-asserted-by":"crossref","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: Proceedings of Computer Science in Russia, CSR 2007. Lecture Notes in Computer Science, vol. 4649, pp 249\u2013258. Springer (2007)","DOI":"10.1007\/978-3-540-74510-5_26"},{"issue":"2","key":"9808_CR38","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1016\/j.jalgebra.2007.08.025","volume":"320","author":"M Lohrey","year":"2008","unstructured":"Lohrey, M., Steinberg, B.: The submonoid and rational subset membership problems for graph groups. J. Algebra 320(2), 728\u2013755 (2008)","journal-title":"J. Algebra"},{"key":"9808_CR39","unstructured":"Lohrey, M., Zetzsche, G.: Knapsack in graph groups, HNN-extensions and amalgamated products. In: Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 47, pp 50:1\u201350:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Germany (2016)"},{"key":"9808_CR40","unstructured":"Lohrey, M., Zetzsche, G.: The complexity of knapsack in graph groups. In: Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 66, pp 52:1\u201352:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Germany (2017)"},{"key":"9808_CR41","volume-title":"Combinatorial group theory","author":"RC Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial group theory. Springer, New York (1977)"},{"key":"9808_CR42","first-page":"241","volume":"70","author":"KA Miha\u0131\u0306lova","year":"1966","unstructured":"Miha\u0131\u0306lova, K.A.: The occurrence problem for direct products of groups. Math. USSR Sbornik 70, 241\u2013251 (1966). English translation","journal-title":"Math. USSR Sbornik"},{"key":"9808_CR43","doi-asserted-by":"crossref","unstructured":"Muscholl, A., Peled, D.: Message sequence graphs and decision problems on Mazurkiewicz traces. In: Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, MFCS 1999. Lecture Notes in Computer Science, number 1672 , pp 81\u201391. Springer (1999)","DOI":"10.1007\/3-540-48340-3_8"},{"key":"9808_CR44","doi-asserted-by":"crossref","unstructured":"Myasnikov, A., Nikolaev, A., Ushakov, A.: Knapsack problems in groups. Math. Comput. 84, 987\u20131016 (2015)","DOI":"10.1090\/S0025-5718-2014-02880-9"},{"key":"9808_CR45","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.jsc.2017.03.007","volume":"84","author":"A Nikolaev","year":"2018","unstructured":"Nikolaev, A., Ushakov, A.: Subset sum problem in polycyclic groups. J. Symb. Comput. 84, 84\u201394 (2018)","journal-title":"J. Symb. Comput."},{"issue":"4","key":"9808_CR46","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.H.: On the complexity of integer programming. J. Assoc. Comput. Mach. 28(4), 765\u2013768 (1981)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9808_CR47","doi-asserted-by":"crossref","unstructured":"Pottier, L.: Minimal solutions of linear Diophantine systems: bounds and algorithms. In: Proceedings of the 4th International Conference on Rewriting Techniques and Applications, RTA 1991. Lecture Notes in Computer Science, vol. 488, pp 162\u2013173. Springer-Verlag (1991)","DOI":"10.1007\/3-540-53904-2_94"},{"issue":"3","key":"9808_CR48","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"IH Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context\u2013free languages. J. Assoc. Comput. Mach. 25(3), 405\u2013414 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"17","key":"9808_CR49","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1016\/j.ipl.2009.06.005","volume":"109","author":"AW To","year":"2009","unstructured":"To, A.W.: Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. 109(17), 1010\u20131014 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9808_CR50","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to circuit complexity. Springer, New York (1999)"},{"key":"9808_CR51","first-page":"44","volume":"16","author":"DT Wise","year":"2009","unstructured":"Wise, D.T.: Research announcement: the structure of groups with a quasiconvex hierarchy. Electron. Res. Announc. Math. Sci. 16, 44\u201355 (2009)","journal-title":"Electron. Res. Announc. Math. Sci."},{"key":"9808_CR52","first-page":"17","volume":"16","author":"ES Wolk","year":"1965","unstructured":"Wolk, E.S.: A note on the \u201cThe comparability graph of a tree\u201d. Proc. Amer. Math. Soc. 16, 17\u201320 (1965)","journal-title":"Proc. Amer. Math. Soc."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9808-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9808-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9808-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T17:52:49Z","timestamp":1692985969000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9808-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,12]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9808"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9808-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,9,12]]}}}