ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS

DOI10.1142/S0218196706003086MaRDI QIDQ5483455zbMATH OpenFDO

Authors Pavel Goralčík, Václav Koubek

Publication date 14 August 2006

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

zbMATH Keywords

NP-completenesssemigroupcompletionpartial groupoid

Mathematics Subject Classification ID

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

Recommendations

• Deciding embeddability of partial groupoids into semigroups
• scientific article; zbMATH DE number 7250165
• Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
• Complexity of the identity checking problem for finite semigroups.
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

Cites work

• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithmic problems for amalgams of finite semigroups
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• On Isomorphisms and Density of $NP$ and Other Complete Sets

Cited in

(5)

• scientific article; zbMATH DE number 18496 (Why is no real title available?)
• scientific article; zbMATH DE number 4093768 (Why is no real title available?)
• scientific article; zbMATH DE number 1978807 (Why is no real title available?)
• scientific article; zbMATH DE number 4168952 (Why is no real title available?)
• \(G_a\)-actions and completions

This page was built for publication: ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS

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