Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint
type: Item
instance of: scholarly article
title: Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint
zbMATH Open document ID: 1462.20014
author: V. G. Durnev
author: O. V. Zetkina
author: A. I. Zetkina
published in: Journal of Algebra
publication date: 2021-01-06T00:00:00Z
review text: Let \(F_{2}=\langle a,b \rangle\) be a free group with free generators \(a\), \(b\) and let \(F_{2}^{(s)}\) be the \(s\)-th term of the derived series of \(F_{2}\). The main results proved in this paper are. Theorem 1. In \(F_{2}\) one can construct an equation \(w(x,x_{1},x_{2}, \ldots, x_{n},a,b)=1\) with unknowns \(x_{1}, x_{2}, \ldots, x_{n}\) and parameter \(x\), such that there exists no algorithm to recognize for an arbitrary \(k \in \mathbb{N}\), whether the equation \[w(a^{k},x_{1},x_{2}, \ldots, x_{n},a,b)=1\] has a solution satisfying the condition \(x_{1},x_{2}, \ldots, x_{t} \in F_{2}^{(1)}\) where \(t\) is some fixed integer between \(1\) and \(n\). Theorem 3. There exists no algorithm to recognize, whether an arbitrary equation \(w(x_{1},x_{2}, \ldots, x_{n})=[a,b]\) in the free group \(F_{2}=\langle a,b \rangle\) has a solution \(g_{1}, g_{2}, \ldots, g_{n}\) satisfying the condition \(g_{1} \in F_{2}^{(2)}\).
reviewed by: Egle Bettio
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 20E05
Mathematics Subject Classification ID: 20F18
Mathematics Subject Classification ID: 20F05
zbMATH DE Number: 7290698
zbMATH Keywords: algorithmic undecidability
zbMATH Keywords: equations in free groups
zbMATH Keywords: word problem
MaRDI profile type: Publication
full work available at URL: j.jalgebra.2020.12.007
OpenAlex ID: W3112819292
cites work: Undecidable theories
cites work: Implicit function theorem over free groups.
cites work: Elementary theory of free non-abelian groups.
cites work: Equations in Free Groups
cites work: One-Variable Equations in Free Groups
cites work: SYSTEMS OF EQUATIONS IN A FREE GROUP. I
cites work: SYSTEMS OF EQUATIONS IN A FREE GROUP. II
cites work: EQUATIONS IN A FREE GROUP
cites work: DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
cites work: Q5619830
cites work: ON SYSTEMS OF EQUATIONS IN A FREE GROUP
cites work: On systems of equations over free products of groups.
cites work: Equations over groups.
cites work: On braid groups
cites work: The Kourovka notebook. Unsolved problems in group theory.
cites work: Pseudosymmetric equations in a free monoid.
cites work: On equations in free semigroups and groups
cites work: Q5519938
cites work: On the Substitution Problem for Free Groups
cites work: Quadratic equations over free groups and free products
cites work: Quadratic equations over small cancellation groups
cites work: On the solvability problem for equations with a single coefficient
cites work: Quadratic equations in hyperbolic groups are NP-complete
cites work: Q5613949
cites work: Q5331777
cites work: Combinatorial group theory.
cites work: Generators of the group \(F/[N,N]\)
cites work: Some properties of a Magnus embedding
cites work: Solving one-variable equations in free groups
cites work: Q5662582
cites work: Q3276701
cites work: Varieties of groups
DOI: 10.1016/J.JALGEBRA.2020.12.007
description: scientific article; zbMATH DE number 7290698