Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 279 - 296 DOI 10.1051/ita:2005016

Theoret. Informatics Appl. 39, 279-296 (2005)
DOI: 10.1051/ita:2005016

Krohn-Rhodes complexity pseudovarieties are not finitely based

John Rhodes¹ and Benjamin Steinberg<sup>2

1</sup>  Department of Mathematics, University of California at Berkeley, Berkeley, CA 94720, USA; rhodes@math.berkeley.edu
²  School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario K1S 5B6, Canada; bsteinbg@math.carleton.ca

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.

Mathematics Subject Classification. 20M07

Key words: Complexity -- finite basis problem -- the presentation lemma


© EDP Sciences 2005

What is OpenURL?