Unification in commutative semigroups
type: Item
instance of: scholarly article
title: Unification in commutative semigroups
zbMATH Open document ID: 0898.20037
published in: Journal of Algebra
publication date: 1998-08-26T00:00:00Z
review text: Let \(V\) be a variety of algebras and \(X\) a fixed set of variables. Every function \(\sigma\) assigning \(V\)-terms to variables is called a substitution. If \(p\) is a term and \(\sigma\) is a substitution, the term \(\sigma(p)\) is defined in the usual way. Let \(\Sigma\) be a finite set of equations over \(V\). A substitution \(\sigma\) is said to be a unifier of \(\Sigma\), if for every equation \(p\approx q\in\Sigma\), the equation \(\sigma(p)\approx\sigma(q)\) holds in \(V\). The problem is to describe the structure of the set \(U(\Sigma,V)\) of all unifiers of \(\Sigma\). Speaking non-formally, it means that we want to describe all solutions of finite sets of equations, defining if every solution comes from a most general solution, and if so, defining how many most general solutions are needed to generate all solutions. This problem is solved for all varieties of commutative semigroups. A unifier \(\sigma_1\) is called more general than a unifier \(\sigma_2\) (\(\sigma_1\leq\sigma_2\)) if \(\sigma_2=\tau\sigma_1\) for some substitution \(\tau\). One of the results obtained states that every nontrivial variety \(V\) of commutative semigroups has finitary unification type (it means that all unifiers are generated, relative to \(\leq\), by a finite number of most general unifiers), unless \(V\) is the variety of abelian groups of exponent \(r>1\) or the variety of nullsemigroups, in which cases the unification type is unitary. Another result states that for commutative semigroups the unification problem is solvable. The author assumes that this is the first so general result in the area.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M14
zbMATH DE Number: 1139777
zbMATH Keywords: unification types
zbMATH Keywords: varieties of commutative semigroups
zbMATH Keywords: automated theorem proving
zbMATH Keywords: finite sets of equations
author: Andrzej Kisielewicz
reviewed by: Grigori I. Zhitomirski
MaRDI profile type: Publication
OpenAlex ID: W2076117469
cites work: Unification in Varieties of Groups: Nilpotent Varieties
cites work: Free groups and unification in \({\mathfrak A}_ m{\mathfrak A}_ 2\)
cites work: Unification in varieties of completely regular semigroups
cites work: Unification in varieties of idempotent semigroups
cites work: Unification in commutative idempotent monoids
cites work: Q4296747
cites work: Unification in Boolean rings and Abelian groups
cites work: The Undecidability of the Unification Problem for Nilpotent Groups of Class ⩾ 5
cites work: Unification in partially commutative semigroups
cites work: Unification for nilpotent groups of class 2
cites work: Computers and universal algebra: Some directions
cites work: Unification in commutative rings is not finitary
cites work: Q3338216
cites work: Unification in abelian semigroups
cites work: Varieties of Commutative Semigroups
cites work: Complexity of Makanin's algorithm
cites work: The theory of well-quasi-ordering: a frequently discovered concept
cites work: Q3219154
cites work: EQUATIONS IN A FREE GROUP
cites work: Q3751631
cites work: Unification in primal algebras, their powers and their varieties
cites work: THE SOLVABILITY PROBLEM FOR EQUATIONS IN ONE UNKNOWN IN NILPOTENT GROUPS
cites work: Q3824583
cites work: Semi-unification of two terms in Abelian groups
cites work: Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
cites work: Unification theory
cites work: The undecidability of the DA-unification problem
cites work: Q3484383
cites work: Equation-Solving in Free Nilpotent groups Class 2 and 3
DOI: 10.1006/JABR.1997.7212
description: scientific article; zbMATH DE number 1139777