A minimal nonfinitely based semigroup whose variety is polynomially recognizable.

DOI10.1007/S10958-011-0512-6MaRDI QIDQ2248321zbMATH OpenOpenAlexFDO

Authors S. V. Goldberg, S. I. Kublanovskiĭ, M. V. Volkov

Publication date 26 June 2014

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.2425

zbMATH Keywords

bases of identitiesmembership problemvarieties of semigroupsnonfinitely based semigroups

Mathematics Subject Classification ID

Lattices of varieties (08B15) Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07)

Abstract: We exhibit a 6-element semigroup that has no finite identity basis but nevertheless generates a variety whose finite membership problem admits a polynomial algorithm.

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 4023572 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1822380 (Why is no real title available?)
• A 2EXPTIME complete varietal membership problem
• ALGORITHMIC PROBLEMS IN VARIETIES
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• An example of a finite semigroup without an irreducible basis of identities in the class of completelyo-simple semigroups
• Bases for equational theories of semi-groups
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• Completely O-simple semigroups and their associated graphs and groups
• Complexity issues of checking identities in finite monoids
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Identical relations in finite groups
• Identities of a five-element \(0\)-simple semigroup
• Identity bases for some non-exact varieties.
• LIMIT VARIETIES GENERATED BY COMPLETELY 0-SIMPLE SEMIGROUPS
• Matrix rank 1 semigroup identities
• ON A BASIS OF THE PRODUCT OF VARIETIES OF GROUPS
• On Comparison of Finite Algebras
• On cross semigroup varieties and related questions
• On the structure of the lattice of combinatorial Rees-Sushkevich varieties.
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• The finite basis problem for finite semigroups
• The finite basis property for varieties of semigroups
• The finite basis question for semigroups of order less than six
• The pseudovariety generated by completely \(0\)-simple semigroups

Cited in

(2)

• COMBINATORIAL REES–SUSHKEVICH VARIETIES THAT ARE CROSS, FINITELY GENERATED, OR SMALL
• Minimal non-finitely based semigroups.

This page was built for publication: A minimal nonfinitely based semigroup whose variety is polynomially recognizable.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248321)