×

Closure properties of knapsack semilinear groups. (English) Zbl 1512.20105

Summary: A knapsack equation in a group \(G\) is an equation of the form \(g_1^{x_1}\cdots g_k^{x_k}=g\) where \(g_1,\dots,g_k,g\) are elements of \(G\) and \(x_1,\dots,x_k\) are variables that take values in the natural numbers. We study the class of groups \(G\) for which all knapsack equations have effectively semilinear solution sets. We show that the following group constructions preserve effective semilinearity: graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study a complexity measure, called magnitude, of the resulting semilinear solution sets. More precisely, we are interested in the growth of the magnitude in terms of the length of the knapsack equation (measured in number of generators). We investigate how this growth changes under the above group operations.

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E22 Extensions, wreath products, and other compositions of groups
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
68Q25 Analysis of algorithms and problem complexity

References:

[1] Adian, Sergei I., The Burnside problem and related topics, Russ. Math. Surv., 65, 5, 805-855 (2010) · Zbl 1230.20001
[2] Allenby, Reg; Gregorac, Robert John, On locally extended residually finite groups, (Conference on Group Theory. Conference on Group Theory, Univ. Wisconsin-Parkside, Kenosha, Wis., 1972. Conference on Group Theory. Conference on Group Theory, Univ. Wisconsin-Parkside, Kenosha, Wis., 1972, Lecture Notes in Mathematics, vol. 319 (1973), Springer: Springer Berlin), 9-17 · Zbl 0263.20020
[3] Babai, László; Beals, Richard; Cai, James; Ivanyos, Gábor; Luks, Eugene, Multiplicative equations over commuting matrices, (Proceedings of SODA 1996 (1996), ACM/SIAM), 498-507 · Zbl 0865.15012
[4] Beier, Simon; Holzer, Markus; Kutrib, Martin, On the descriptional complexity of operations on semilinear sets, (Proceedings of the 15th International Conference on Automata and Formal Languages. Proceedings of the 15th International Conference on Automata and Formal Languages, AFL 2017. Proceedings of the 15th International Conference on Automata and Formal Languages. Proceedings of the 15th International Conference on Automata and Formal Languages, AFL 2017, EPTCS, vol. 252 (2017)), 41-55 · Zbl 1483.68155
[5] Bergsträßer, Pascal; Ganardi, Moses; Zetzsche, Georg, A characterization of wreath products where knapsack is decidable, (Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, LIPIcs, vol. 187 (2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 11 pp.
[6] Bertoni, Alberto; Mauri, Giancarlo; Sabadini, Nicoletta, Membership problems for regular and context free trace languages, Inf. Comput., 82, 135-150 (1989) · Zbl 0682.68040
[7] Bezverkhnii, Vladimir Nikolaevich, On the intersection subgroups HNN-groups, Fundam. Prikl. Mat., 4, 1, 199-222 (1998) · Zbl 0970.20015
[8] Book, Ronald V.; Otto, Friedrich, String-Rewriting Systems (1993), Springer · Zbl 0832.68061
[9] Chistikov, Dmitry; Haase, Christoph, The taming of the semi-linear set, (Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Leibniz International Proceedings in Informatics (LIPIcs), vol. 55 (2016), Schloss Dagstuhl-Leibniz-Zentrum für Informatik), Article 128 pp. · Zbl 1388.68190
[10] Dehn, Max, Über unendliche diskontinuierliche Gruppen, Math. Ann., 71, 116-144 (1911), (in German) · JFM 42.0508.03
[11] Dicks, Warren; Dunwoody, Martin J., Groups Acting on Graphs (1989), Cambridge University Press · Zbl 0665.20001
[12] Diekert, Voker, Combinatorics on Traces, Lecture Notes in Computer Science., vol. 454 (1990), Springer · Zbl 0717.68002
[13] (Diekert, Voker; Rozenberg, Grzegorz, The Book of Traces (1995), World Scientific)
[14] Volker, Diekert; Lohrey, Markus, Word equations over graph products, Int. J. Algebra Comput., 18, 3, 493-533 (2008) · Zbl 1186.20041
[15] Droms, Carl, A complex for right-angled Coxeter groups, Proc. Am. Math. Soc., 131, 8, 2305-2311 (2003) · Zbl 1032.20027
[16] Dudkin, Fedor Anatolievich; Treyer, Alexander Victorovich, Knapsack problem for Baumslag-Solitar groups, Sib. J. Pure Appl. Math., 18, 4, 43-55 (2018) · Zbl 1438.20033
[17] Eisenbrand, Friedrich; Shmonin, Gennady, Carathéodory bounds for integer cones, Oper. Res. Lett., 34, 5, 564-568 (2006) · Zbl 1152.90662
[18] Elberfeld, Michael; Jakoby, Andreas; Tantau, Till, Algorithmic meta theorems for circuit classes of constant and logarithmic depth, Electron. Colloq. Comput. Complex., 18, 128 (2011) · Zbl 1245.68086
[19] Figelius, Michael; Ganardi, Moses; Lohrey, Markus; Zetzsche, Georg, The complexity of knapsack problems in wreath products, (Proceedings of the 47th International Colloquium on Automata, Languages, and Programming. Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Proceedings of the 47th International Colloquium on Automata, Languages, and Programming. Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, LIPIcs, vol. 168 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 126 pp.
[20] Frenkel, Elizaveta; Nikolaev, Andrey; Ushakov, Alexander, Knapsack problems in products of groups, J. Symb. Comput., 74, 96-108 (2016) · Zbl 1401.20031
[21] Ganardi, Moses; König, Daniel; Lohrey, Markus; Zetzsche, Georg, Knapsack problems for wreath products, (Proceedings of 35th Symposium on Theoretical Aspects of Computer Science. Proceedings of 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Proceedings of 35th Symposium on Theoretical Aspects of Computer Science. Proceedings of 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, LIPIcs, vol. 96 (2018), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 32 pp. · Zbl 1491.20078
[22] Ginsburg, Seymour; Spanier, Edwin Henry, Semigroups, Presburger formulas and languages, Pac. J. Math., 16, 2, 285-296 (1966) · Zbl 0143.01602
[23] Green, Elisabeth R., Graph Products of Groups (1990), The University of Leeds, PhD thesis
[24] Haase, Christoph, On the complexity of model checking counter automata (2011), University of Oxford, St Catherine’s College, PhD thesis
[25] Haubold, Niko; Lohrey, Markus, Compressed word problems in HNN-extensions and amalgamated products, Theory Comput. Syst., 49, 2, 283-305 (2011) · Zbl 1235.68106
[26] Haubold, Niko; Lohrey, Markus; Mathissen, Christian, Compressed decision problems for graph products of groups and applications to (outer) automorphism groups, Int. J. Algebra Comput., 22, 8 (2013) · Zbl 1267.20050
[27] Higman, Graham; Neumann, Bernhard H.; Neumann, Hanna, Embedding theorems for groups, J. Lond. Math. Soc. (2), 24, 247-254 (1949) · Zbl 0034.30101
[28] Holt, Derek F.; Lohrey, Markus; Schleimer, Saul, Compressed decision problems in hyperbolic groups, (Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, LIPIcs, vol. 126 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 37 pp.
[29] Huet, Gérard, Confluent reductions: abstract properties and applications to term rewriting systems: abstract properties and applications to term rewriting systems, J. ACM, 27, 4, 797-821 (1980) · Zbl 0458.68007
[30] Kambites, Mark; Silva, Pedro V.; Steinberg, Benjamin, On the rational subset problem for groups, J. Algebra, 309, 2, 622-639 (2007) · Zbl 1123.20047
[31] Kapovich, Ilya; Weidmann, Richard; Myasnikov, Alexei, Foldings, graphs of groups and the membership problem, Int. J. Algebra Comput., 15, 1, 95-128 (2005) · Zbl 1089.20018
[32] Karp, Richard M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065
[33] Karrass, Abraham; Solitar, Donald, The subgroups of a free product of two groups with an amalgamated subgroup, Trans. Am. Math. Soc., 150, 227-255 (1970) · Zbl 0223.20031
[34] Karrass, Abraham; Solitar, Donald, Subgroups of HNN groups and groups with one defining relation, Can. J. Math., 23, 627-643 (1971) · Zbl 0232.20051
[35] König, Daniel; Lohrey, Markus; Zetzsche, Georg, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, (Algebra and Computer Science. Algebra and Computer Science, Contemporary Mathematics, vol. 677 (2016), American Mathematical Society), Article 138 pp. · Zbl 1392.68205
[36] Kuske, Dietrich; Lohrey, Markus, Logical aspects of Cayley-graphs: the monoid case, Int. J. Algebra Comput., 16, 2, 307-340 (2006) · Zbl 1151.03003
[37] Lehnert, Jörg; Schweitzer, Pascal, The co-word problem for the Higman-Thompson group is context-free, Bull. Lond. Math. Soc., 39, 2, 235-241 (2007) · Zbl 1166.20025
[38] Lohrey, Markus, Knapsack in hyperbolic groups, J. Algebra (2019) · Zbl 1515.68153
[39] Lohrey, Markus; Sénizergues, Géraud, Theories of HNN-extensions and amalgamated products, (Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Lecture Notes in Computer Science, vol. 4052 (2006), Springer), 681-692 · Zbl 1134.03009
[40] Lohrey, Markus; Sénizergues, Géraud, Rational subsets in HNN-extensions and amalgamated products, Int. J. Algebra Comput., 18, 1, 111-163 (2008) · Zbl 1190.20019
[41] Lohrey, Markus; Zetzsche, Georg, Knapsack in graph groups, HNN-extensions and amalgamated products, (Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, STACS 2016, Dagstuhl, Germany. Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, STACS 2016, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs), vol. 47 (2016), Schloss Dagstuhl-Leibniz-Zentrum für Informatik), Article 50 pp. · Zbl 1380.68229
[42] Lohrey, Markus; Zetzsche, Georg, Knapsack in graph groups, Theory Comput. Syst., 62, 1, 192-246 (2018) · Zbl 1386.68073
[43] Lohrey, Markus; Zetzsche, Georg, Knapsack and the power word problem in solvable Baumslag-Solitar groups, (Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, LIPIcs, vol. 170 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 67 pp. · Zbl 1402.68103
[44] Lyndon, Roger; Schupp, Paul, Combinatorial Group Theory (1977), Springer · Zbl 0368.20023
[45] Metaftsis, Vasileios; Raptis, Evagelos, Subgroup separability of graphs of abelian groups, Proc. Am. Math. Soc., 132, 7, 1873-1884 (2004) · Zbl 1051.20012
[46] Mishchenko, Alexei; Treier, Alexander, Knapsack problem for nilpotent groups, Groups Complex. Cryptol., 9, 1, 87-98 (2017) · Zbl 1382.20039
[47] Myasnikov, Alexei; Nikolaev, Andrey; Ushakov, Alexander, Knapsack problems in groups, Math. Comput., 84, 987-1016 (2015) · Zbl 1392.68207
[48] Stallings, John Robert, Group Theory and Three-Dimensional Manifolds, Yale Mathematical Monographs, vol. 4 (1971), Yale University Press · Zbl 0241.57001
[49] To, Anthony Widjaja, Unary finite automata vs. arithmetic progressions, Inf. Process. Lett., 109, 17, 1010-1014 (2009) · Zbl 1202.68241
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.