Membership testing in commutative transformation semigroups

DOI10.1016/0890-5401(88)90018-1MaRDI QIDQ1108790zbMATH OpenOpenAlexFDO

Authors Martin Beaudry

Publication date 1988

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(88)90018-1

zbMATH Keywords

thresholdindexNP-completeparallel complexitycommutative transformation semigroups

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A taxonomy of problems with fast parallel algorithms
• Parallel algorithms for solvable permutation groups
• The Parallel Complexity of Abelian Permutation Group Problems

Cited in

(7)

• Computing finite semigroups
• The complexity of intersecting finite automata having few final states
• scientific article; zbMATH DE number 7250165 (Why is no real title available?)
• The intersection problem for finite semigroups
• The intersection problem for finite monoids
• Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?

This page was built for publication: Membership testing in commutative transformation semigroups

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