𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Unification in Commutative Semigroups

✍ Scribed by Andrzej Kisielewicz


Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
161 KB
Volume
200
Category
Article
ISSN
0021-8693

No coin nor oath required. For personal study only.

✦ Synopsis


Unification is one of the basic concepts of automated theorem proving. It concerns such questions as finding solutions of finite sets of equations, determining if every solution comes from a most general solution, and if so, determining how many most general solutions are needed to generate all solutions. These solutions given in terms of substitutions are called, more formally, unifiers. The unification Ž . type of a variery equational class of algebras is defined according to the cardinality or existence of minimal complete sets of most general unifiers. Of particular interest, from a computational point of view, are varieties of groups and semigroups. So far the problem has been considered mainly for particular varieties. In this paper we determine unification types for all varieties of commutative semigroups. In particular, we prove that for commutative semigroups the unification problem is solvable in the very strong sense that there is an algorithm which for any two finite sets ⌺ and ⌺ of semigroup equations produces the minimal 1 2 complete set of the most general unifiers of ⌺ over the variety of commutative 1 semigroups generated by ⌺ . It seems that this is the first so general decidability 2 result in the area.


πŸ“œ SIMILAR VOLUMES


Slightly Commutative Kleene Semigroups
✍ C.P. Rupert πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 285 KB

Commutative Kleene semigroups are known to be rational, but Pelletier constructed a nonrational weakly commutative Kleene semigroup. We introduce slightly commutative Kleene semigroups, a class of weakly commutative Kleene semigroups, and prove that every slightly commutative Kleene semigroup is rat

Commutative Semigroups Which Are Semigro
✍ Kunitaka Shoji πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 371 KB

Ξ± -r e 2 s at , and bt β‰₯ Ξ± 2i-r e 2 Ξ± -r e 2 s at . Since Ξ± r e 1 a β‰₯ e 1 at, there exists v ∈ S such that at = Ξ± r e 1 av. Then e 1 sat . We can prove similarly the other inequations. Thus it follows from the equations above and Lemma 7(ii) that Ξ± 2i-r Ξ± -r e 2 s at = Ξ± 2i-r f 2 Ξ± -r f 2 s at . T