Equations in Free Inverse Monoids
by
John Meakin
University of Nebraska
Coauthors: Geraud Senizergues (Univ. Bordeaux)

It is known that the problem of deciding whether a finite system of equations in a free group or a free monoid is decidable, but the corresponding problem for systems of equations in free inverse monoids is undecidable. Any solution to a system of equations in a free inverse monoid induces a solution to the same system of equations in the associated free group in an obvious way, but solutions to equations in free inverse monoids do not necessarily lift to solutions to the same equations in a free inverse monoid. We show, by use of Rabin's tree theorem, that it is decidable whether a solution to a system of equations in a free group lifts to a solution in a free inverse monoid. When combined with some results of Deis, this shows that the consistency problem for single variable equations in free inverse monoids is decidable in most cases.

Date received: February 8, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-72.