Testing for a semilattice term (Q1732802)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Testing for a semilattice term |
scientific article |
Statements
Testing for a semilattice term (English)
0 references
25 March 2019
0 references
A \textit{semilattice term} in an algebra \(A\) means a binary term which is commutative, associative and idempotent. A binary term \(b(x,y)\) is called a \textit{flat semilattice term} if \(A\) has an absorbing element \(0\) such that \(b(a,a)=a\) for every element a and \(b(a,b)=0\) for different elements \(a, b\). The authors prove two remarkable results concerning the computational complexity as follows: Theorem 3.4. The problem of deciding, given a finite idempotent algebra \(A\), whether or not it has a flat semilattice term, is in P. Theorem 4.1 The problem of deciding, given an idempotent algebra \(A\) and its element 1, whether or not it has a semilattice term \(b(x,y)\) such that \(b(a,1)=a=b(1,a)\) for all elements \(a\) in \(A\) is EXP-TIME complete.
0 references
semilattice term
0 references
computational complexity
0 references
idempotent algebra
0 references