# zbMATH — the first resource for mathematics

Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. (Russian) Zbl 0611.20020
The following Ehrenfeucht conjecture is proved: every set L of words over a finite alphabet A contains some finite subset (”a test set”) F such that, for every pair (g,h) of homomorphisms of the free semigroup $$\Pi$$ (A) with the basis A into an arbitrary free semigroup, the equality $$g(x)=h(x)$$ holds for all x in L if and only if it holds for all x in F [see, for example, J. Albert, Lect. Notes Comput. Sci. 176, 176-184 (1984; Zbl 0554.68047)]. This proposition is deduced from the following main theorem: every system of equations in a free group (or in a free semigroup) on a finite number of indeterminates over an arbitrary alphabet is equivalent to some finite subsystem.
Reviewer: Yu.I.Merzlyakov

##### MSC:
 20E05 Free nonabelian groups 20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) 20M05 Free semigroups, generators and relations, word problems 20E36 Automorphisms of infinite groups