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

commutative transformation semigroupsindexNP-completeparallel complexitythreshold

Mathematics Subject Classification ID

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

Review text

See the review of the preliminary version of this article [Lect. Notes Comput. Sci. 267, 542-549 (1987)] in Zbl 0654.68042.

Cites work

• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A taxonomy of problems with fast parallel algorithms
• 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?)
• Parallel algorithms for solvable permutation groups
• The Parallel Complexity of Abelian Permutation Group Problems

Cited in

(9)

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

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)