Testing for a semilattice term
type: Item
instance of: scholarly article
title: Testing for a semilattice term
zbMATH Open document ID: 1439.08006
author: Ralph Freese
author: J. B. Nation
author: Matthew Valeriote
published in: Order
publication date: 2019-03-25T00:00:00Z
review text: 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.
reviewed by: Ivan Chajda
Mathematics Subject Classification ID: 08B05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 06A12
zbMATH DE Number: 7041564
zbMATH Keywords: semilattice term
zbMATH Keywords: computational complexity
zbMATH Keywords: idempotent algebra
MaRDI profile type: Publication
full work available at URL: s11083-018-9455-6
OpenAlex ID: W2793464978
cites work: Congruence-distributive polynomial reducts of lattices
cites work: Q4993594
cites work: Q3093852
cites work: COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
cites work: Q3934450
cites work: ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
cites work: The structure of finite algebras
cites work: Computational complexity of various Mal'cev conditions
cites work: Algebras Whose Congruence Lattices are Distributive.
cites work: DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS
cites work: The shape of congruence lattices
cites work: Simple equations on real intervals
cites work: Idempotent n -permutable varieties
Wikidata QID: Q130122823
DOI: 10.1007/S11083-018-9455-6
description: scientific article; zbMATH DE number 7041564