Name
Abstract | ||
|---|---|---|
The author proves for each of the operations # equalling *, o, **, rectangle or m, there exist pseudovarieties of finite semigroups V-1 and V-2 with decidable membership problems, such that V-2#V-1 has an undecidable membership problem.In addition, if A denotes the pseudovariety of all finite aperiodic semigroups, G denotes the pseudovariety of all finite groups, and A(E) denotes the pseudovariety of all finite aperiodic semigroups satisfying the finite number of equations E, then it is proved that there exists E such that A * G * A(E) has an undecidable membership problem. Note A * G * A equals all semigroups of complexity less than or equal to 1.Section 6 is expanded into a joint paper with B. Steinberg, following this paper. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1142/S0218196799000278 | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION |
Field | DocType | Volume |
Discrete mathematics,Finite set,Krohn–Rhodes theory,Algebra,Existential quantification,Automaton,Decidability,Special classes of semigroups,Aperiodic graph,Mathematics,Undecidable problem | Journal | 9 |
Issue | ISSN | Citations |
3-4 | 0218-1967 | 9 |
PageRank | References | Authors |
1.24 | 5 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Rhodes | 1 | 9 | 1.58 |