Unification in partially commutative semigroups |
| |
Authors: | E K Burke |
| |
Affiliation: | (1) Department of Computer Science, Nottingham University, NG7 2RD University Park, Nottingham, England |
| |
Abstract: | Unification algorithms have been constructed for semigroups and commutative semigroups. This paper considers the intermediate case of partially commutative semigroups. We introduce classesN and of such semigroups and justify their use. We present an equation-solving algorithm for any member of the classN. This algorithm is relative to having an algorithm to determine all non-negative solutions of a certain class of diophantine equations of degree 2 which we call -equations. The difficulties arising when attempting to solve equations in members of the class are discussed, and we present arguments that strongly suggest that unification in these semigroups is undecidable. |
| |
Keywords: | Unification equation solving partially commutative semigroups |
本文献已被 SpringerLink 等数据库收录! |