Geodesic
Decidability problem for exponential equations in finitely presented groups
Canadian mathematical bulletin, Tome 66 (2023) no. 3, pp. 731-748

Voir la notice de l'article provenant de la source Cambridge

DOI

We study the following decision problem: given an exponential equation $a_1g_1^{x_1}a_2g_2^{x_2}\dots a_ng_n^{x_n}=1$ over a recursively presented group G, decide if it has a solution with all $x_i$ in $\mathbb {Z}$. We construct a finitely presented group G where this problem is decidable for equations with one variable and is undecidable for equations with two variables. We also study functions estimating possible solutions of such an equation through the lengths of its coefficients with respect to a given generating set of G. Another result concerns Turing degrees of some natural fragments of the above problem.
DOI : 10.4153/S0008439522000698
Mots-clés : Decidability problems, exponential equations, knapsack problem, finitely presented groups 
Bogopolski, Oleg; Ivanov, Aleksander. Decidability problem for exponential equations in finitely presented groups. Canadian mathematical bulletin, Tome 66 (2023) no. 3, pp. 731-748. doi: 10.4153/S0008439522000698
@article{10_4153_S0008439522000698,
     author = {Bogopolski, Oleg and Ivanov, Aleksander},
     title = {Decidability problem for exponential equations in finitely presented groups},
     journal = {Canadian mathematical bulletin},
     pages = {731--748},
     year = {2023},
     volume = {66},
     number = {3},
     doi = {10.4153/S0008439522000698},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439522000698/}
}
TY  - JOUR
AU  - Bogopolski, Oleg
AU  - Ivanov, Aleksander
TI  - Decidability problem for exponential equations in finitely presented groups
JO  - Canadian mathematical bulletin
PY  - 2023
SP  - 731
EP  - 748
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439522000698/
DO  - 10.4153/S0008439522000698
ID  - 10_4153_S0008439522000698
ER  - 
%0 Journal Article
%A Bogopolski, Oleg
%A Ivanov, Aleksander
%T Decidability problem for exponential equations in finitely presented groups
%J Canadian mathematical bulletin
%D 2023
%P 731-748
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439522000698/
%R 10.4153/S0008439522000698
%F 10_4153_S0008439522000698

Cité par Sources :