The membership problem in aperiodic transformation monoids
| Autor: | Martin Beaudry, Denis Thérien, Pierre McKenzie |
|---|---|
| Rok vydání: | 1992 |
| Předmět: | |
| Zdroj: | Journal of the ACM. 39:599-616 |
| ISSN: | 1557-735X 0004-5411 |
| DOI: | 10.1145/146637.146661 |
| Popis: | The problem of testing membership in aperiodic or “group-free” transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. The class A of all finite aperiodic monoids and the class G of all finite groups are two examples of varieties , the fundamental complexity units in terms of which finite monoids are classified. The collection of all varieties V forms an infinite lattice under the inclusion ordering, with the subfamily of varieties that are contained in A forming an infinite sublattice. For each V ⊆ A , the associated problem MEMB( V ) of testing membership in transformation monoids that belong to V , is considered. Remarkably, the computational complexity of each such problem turns out to look familiar. Moreover, only five possibilities occur as V ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB( V ) is either PSPACE-complete, NP-complete, P-complete or in AC 0 . These results thus uncover yet another surprisingly tight link between the theory of monoids and computational complexity theory. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|