On the membership problem for pseudovarieties of commutative semigroups
type: Item
instance of: scholarly article
title: On the membership problem for pseudovarieties of commutative semigroups
zbMATH Open document ID: 0728.20050
DOI: 10.1007/BF02573404
published in: Semigroup Forum
publication date: 1991-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/135062
review text: The author shows that every pseudovariety of finite commutative semigroups admits a finite basis of pseudoidentities. On the other hand, he exhibits an example of a permutative pseudovariety without finite basis of pseudoidentities. He proves also that a pseudovariety of commutative semigroups has the membership problem decidable in polynomial time if and only if it admits a finite basis of pseudoidentities verifiable in polynomial time.
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M14
Mathematics Subject Classification ID: 08C15
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 4202593
zbMATH Keywords: pseudovariety of finite commutative semigroups
zbMATH Keywords: finite basis of pseudoidentities
zbMATH Keywords: permutative pseudovariety
zbMATH Keywords: membership problem
zbMATH Keywords: polynomial time
author: Jorge Almeida
MaRDI profile type: Publication
cites work: Some Order Properties of the Lattice of Varieties of Commutative Semigroups
cites work: Minimal non-permutative pseudovarieties of semigroups. I
cites work: Some algorithmic problems for pseudovarieties
cites work: Q3760739
cites work: Q4132170
cites work: Bases for equational theories of semi-groups
cites work: The Birkhoff theorem for finite algebras
OpenAlex ID: W2035576809
Recommended article: Pseudovarieties of completely regular semigroups
Recommended article: Mathematical Foundations of Computer Science 2004
Recommended article: A decision problem for varieties of commutative semigroups
Recommended article: Q4258200
Recommended article: On the irreducibility of pseudovarieties of semigroups.
Recommended article: Variety Membership Problem for Two Classes of Non-Finitely Based Semigroups
Recommended article: Globals of pseudovarieties of commutative semigroups: the finite basis problem, decidability and gaps
Recommended article: Join decompositions of pseudovarieties involving semigroups with commuting idempotents
Recommended article: On the Joins of Semigroup Varieties with the Variety of Commutative Semigroups
Recommended article: The pseudovariety generated by completely \(0\)-simple semigroups
description: scientific article; zbMATH DE number 4202593