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

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