Testing for a semilattice term
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.
- Algebras Whose Congruence Lattices are Distributive.
- COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
- Computational complexity of various Mal'cev conditions
- Congruence-distributive polynomial reducts of lattices
- DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Idempotent n-permutable varieties.
- ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
- Simple equations on real intervals
- The shape of congruence lattices
- The structure of finite algebras
- Universal algebra. Fundamentals and selected topics
This page was built for publication: Testing for a semilattice term
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1732802)
