Membership testing in commutative transformation semigroups

DOI10.1016/0890-5401(88)90018-1zbMath0654.68043OpenAlexW2073409415MaRDI QIDQ1108790

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

indexparallel complexityNP-completethresholdcommutative transformation semigroups

Mathematics Subject Classification ID

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

Related Items

Synchronizing words and monoid factorization, yielding a new parameterized complexity class?, The complexity of intersecting finite automata having few final states, The intersection problem for finite monoids, Computing finite semigroups, Unnamed Item, The Intersection Problem for Finite Semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Parallel algorithms for solvable permutation groups
• A taxonomy of problems with fast parallel algorithms
• The Parallel Complexity of Abelian Permutation Group Problems