MULTILINEAR EQUATIONS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS

Let S = S-1 *(U) S-2 = Inv < X; R > be the free amalgamated product of the finite inverse semigroups S-1, S-2 and let Xi be a finite set of unknowns. We consider the satisfiability problem for multilinear equations over S, i.e. equations w(L) equivalent to w(R) with w(L), w(R) is an element of (X boolean OR X-1 boolean OR Xi boolean OR Xi(-1))(+) such that each x is an element of Xi labels at most one edge in the Schutzenberger automaton of either wL or wR relative to the presentation < X boolean OR Xi vertical bar R >. We prove that the satisfiability problem for such equations is decidable using a normal form of the words w(L), w(R) and the fact that the language recognized by the Schutzenberger automaton of any word in (X boolean OR X-1)(+) relative to the presentation < X vertical bar R > is context-free.