scientific article; zbMATH DE number 4068272

MaRDI QIDQ3801066zbMATH OpenFDO

Authors Martin Beaudry

Publication date 1987

zbMATH Keywords

commutative transformation semigroupsindexNP-completeparallel complexitythreshold

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of properties of transformation semigroups
• The subpower membership problem for semigroups
• Complexity of identity checking in transformation semigroups of rank 2.
• The membership problem in aperiodic transformation monoids
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS

Cited in

(6)

• Characterization of idempotent transformation monoids
• Complexity of identity checking in transformation semigroups of rank 2.
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• The complexity of properties of transformation semigroups
• Testing membership: Beyond permutation groups
• Complexity of the identity checking problem for finite semigroups.

This page was built for publication:

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