Abstract | ||
---|---|---|
We prove that the pseudovariety of monoids of Krohn-Rhodes complexity at most n is not finitely based for all n > 0. More specifically, for each pair of positive integers n, k, we construct a monoid of complexity n + 1, all of whose k-generated submonoids have complexity at most n. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1051/ita:2005016 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
complexity,finite basis problem,the presentation lemma | Integer,Discrete mathematics,Combinatorics,Monoid,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 1 | 0988-3754 |
Citations | PageRank | References |
1 | 0.43 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
John Rhodes | 1 | 89 | 20.04 |
Benjamin Steinberg | 2 | 102 | 17.57 |