Geodesic
Knapsack problem for Baumslag–Solitar groups
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 18 (2018) no. 4, pp. 43-55 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this work we investigate a decidability problem of group version of the knapsack problem for the Baumslag–Solitar group $BS(p,q)$. We proved, that the knapsack problem is decidable for the group $BS(p,q)$ for coprime integers $p > 1$, $q > 1$. In the case where $p=1$, $q\in \mathbb{N}$, we proved that the knapsack problem is decidable for the group $BS(1,q)$ with some restriction on the input of the problem. However, the problem of the decidability of the knapsack problem for the group $BS(1,q)$ on the whole set of inputs remains open.
Keywords: Baumslag–Solitar group, knapsack problem, decidability. 
@article{VNGU_2018_18_4_a3,
     author = {F. A. Dudkin and A. V. Treyer},
     title = {Knapsack problem for {Baumslag{\textendash}Solitar} groups},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {43--55},
     year = {2018},
     volume = {18},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2018_18_4_a3/}
}
TY  - JOUR
AU  - F. A. Dudkin
AU  - A. V. Treyer
TI  - Knapsack problem for Baumslag–Solitar groups
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2018
SP  - 43
EP  - 55
VL  - 18
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VNGU_2018_18_4_a3/
LA  - ru
ID  - VNGU_2018_18_4_a3
ER  - 
%0 Journal Article
%A F. A. Dudkin
%A A. V. Treyer
%T Knapsack problem for Baumslag–Solitar groups
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2018
%P 43-55
%V 18
%N 4
%U http://geodesic.mathdoc.fr/item/VNGU_2018_18_4_a3/
%G ru
%F VNGU_2018_18_4_a3
F. A. Dudkin; A. V. Treyer. Knapsack problem for Baumslag–Solitar groups. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 18 (2018) no. 4, pp. 43-55. http://geodesic.mathdoc.fr/item/VNGU_2018_18_4_a3/

[1] Baumslag G., Solitar D., “Some Two-Generator One-Relator Non-Hopfian Groups”, Bull. AMS, 68:3 (1962), 199–201 | DOI | MR | Zbl

[2] Myasnikov A., Nikolaev A., Ushakov A., “Knapsack Problems in Groups”, Mathematics of Computation, 84:292 (2015), 987–1016 | DOI | MR | Zbl

[3] A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Izv. Math., 22:3 (1984), 587–618 | DOI | MR | Zbl

[4] Lohrey M., Zetzsche G., “Knapsack in graph groups, HNN-extensions and amalgamated products”, Theory of Computing Systems, 62:1 (2018), 192–246 | DOI | MR | Zbl

[5] König D., Lohrey M., Zetzsche G., “Knapsack and Subset Sum Problems in Nilpotent, Polycyclic, and Co-Context-Free Groups”, Algebra and Computer Science, 677 (2016), 138–153 | MR

[6] Mishenko A., Treyer A., “Knapsack Problem for Nilpotent Groups”, Groups, Complexity and Cryptology, 9:1 (2017), 87–98 | MR

[7] Yu. G. Penzin, “Solvability of the theory of integers with addition, order, and multiplication by an arbitrary number”, Math. Notes, 13:5 (1973), 401–405 | DOI | MR | Zbl | Zbl

[8] R. C. Lyndon, P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977 | MR | MR | Zbl

[9] Dudkin F. A., “Subgroups of Baumslag–Solitar groups”, Algebra Logic, 48:1 (2009), 1–19 | DOI | MR | Zbl