Given a finite set X of states, a finite set of transformations of X (generators), and another transformation f of X, we analyze the complexity of the membership problem, which consists in deciding whether f can be obtained by composition of the generators. This problem is studied for various classes (pseudovarieties) of monoids. It is shown that the complexity is NP-hard for monoids of threshold 2 or more, and NP-complete in commutative, J- and R-trivial monoids. For idempotent monoids (aperiodic of threshold one), the problem is NP-complete in the general case; subcases are analyzed, and a largest class of aperiodic monoids is identified for which the problem is in FL, as well as a largest class for which the problem is not NP-hard. / The problem which consists in characterizing an idempotent monoid is also addressed: given a set of transformations, it can be decided in NC$ sp2$ whether the monoid they generate is idempotent. Similar tests are given for three subclasses of idempotent monoids: R$ sb1$, L$ sb1$, and N$ sb3$; in all three cases, the complexity is NC$ sp1$. / A sequential upper bound is also given for each of the parallel complexities given above.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.75773 |
| Date | January 1987 |
| Creators | Beaudry, Martin |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 000665106, proquestno: AAINL46162, Theses scanned by UMI/ProQuest. |
Page generated in 0.0187 seconds