Equations in words and lengths with endomorphisms (Q1317588)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equations in words and lengths with endomorphisms |
scientific article |
Statements
Equations in words and lengths with endomorphisms (English)
0 references
12 April 1994
0 references
Let \(F\) (\(P\)) be the free group (semigroup) on two generators \(a,b\) and let \(\phi\) be the automorphism of \(F\) (endomorphism of \(P\)) extending \(\phi(a) = ab\), \(\phi(b) = b\). The author studies the decidability of systems of equations in the first order theory of \(F\) (\(P\)) enriched with the endomorphism \(\phi\) and word lengths. The author constructs a system of equations \(\Psi(x,x_ 1,\dots,x_ n)\) of the form \(w = 1\;\&\;\&_{(i,j)\in B} | x_ i| = | x_ j|\;\&\;\phi(x_ 1) = x_ 2\) such that for an arbitrary positive integer \(p\) the solvability of the system \(\Psi(a^ p,x_ 1,\dots, x_ n)\) in \(F\) is undecidable. Similar results are proved for the free semigroup \(P\).
0 references
endomorphisms
0 references
free groups
0 references
automorphisms
0 references
decidability
0 references
systems of equations
0 references
first order theory
0 references
word lengths
0 references
solvability
0 references
free semigroups
0 references