ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS

DOI10.1142/S0218196706003086zbMath1103.08002MaRDI QIDQ5483455

Václav Koubek, Pavel Goralčík

Publication date: 14 August 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

semigroupNP-completenesscompletionpartial groupoid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Partial algebras (08A55)

Cites Work

• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• Algorithmic problems for amalgams of finite semigroups
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Unnamed Item
• Unnamed Item