Article contents
Krohn-Rhodes complexity pseudovarieties are not finitely based
Published online by Cambridge University Press: 15 March 2005
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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 1: Imre Simon, the tropical computer scientist , January 2005 , pp. 279 - 296
- Copyright
- © EDP Sciences, 2005
References
- 4
- Cited by