Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-13T06:46:51.999Z Has data issue: false hasContentIssue false
  • English
  • Français

Krohn-Rhodes complexity pseudovarieties are not finitely based

Published online by Cambridge University Press:  15 March 2005

John Rhodes  and
Benjamin Steinberg
John Rhodes
Affiliation:
Department of Mathematics, University of California at Berkeley, Berkeley, CA 94720, USA; [email protected]
Benjamin Steinberg
Affiliation:
School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario K1S 5B6, Canada; [email protected]
Get access

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.

Keywords

Complexityfinite basis problemthe presentation lemma
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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994).
Almeida, J., Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999) 241–261. CrossRef
Ash, C.J., Inevitable graphs: A proof of the Type II conjecture and some related decision procedures. Internat. J. Algebra Comput. 1 (1991) 127–146. CrossRef
Austin, B., Henckell, K., Nehaniv, C. and Rhodes, J., Subsemigroups and complexity via the presentation lemma. J. Pure Appl. Algebra 101 (1995) 245–289. CrossRef
S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976).
Graham, R.L., On finite 0-simple semigroups and graph theory. Math. Syst. Theor. 2 (1968) 325–339. CrossRef
K. Henckell, Idempotent pointlikes. Internat. J. Algebra Comput. (To appear).
K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted).
Henckell, K., Margolis, S., Pin, J.-E. and Rhodes, J., Ash's type II Theorem, profinite topology and Mal'cev products: Part I. Internat. J. Algebra Comput. 1 (1991) 411–436. CrossRef
Krohn, K. and Rhodes, J., Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. 116 (1965) 450–464. CrossRef
Krohn, K. and Rhodes, J., Complexity of finite semigroups. Ann. Math. 88 (1968) 128–160. CrossRef
K. Krohn, J. Rhodes and B. Tilson, Lectures on the algebraic theory of finite semigroups and finite-state machines Chapters 1, 5–9 (Chapter 6 with M.A. Arbib), in The Algebraic Theory of Machines, Languages, and Semigroups, edited by M.A. Arbib. Academic Press, New York (1968).
J.-E. Pin, Varieties of Formal Languages. Plenum, New York (1986).
Rhodes, J., The fundamental lemma of complexity for arbitrary finite semigroups. Bull. Amer. Math. Soc. 74 (1968) 1104–1109. CrossRef
Rhodes, J., Kernel systems – A global study of homomorphisms on finite semigroups. J. Algebra 49 (1977) 1–45. CrossRef
Rhodes, J., Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra 98 (1986) 422–451. CrossRef
Rhodes, J., Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra 100 (1986) 25–137. CrossRef
J. Rhodes and B. Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity. Internat. J. Algebra Comput. (Submitted).
Rhodes, J. and Tilson, B., Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra 1 (1971) 79–95. CrossRef
Rhodes, J. and Tilson, B., Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra 2 (1972) 13–71. CrossRef
Rhodes, J. and Tilson, B., A reduction theorem for complexity of finite semigroups. Semigroup Forum 10 (1975) 96–114. CrossRef
J. Rhodes and B. Tilson, Local complexity of finite semigroups, in Algebra, Topology, and Category Theory (collection of papers in honor of Samuel Eilenberg). Academic Press, New York (1976) 149–168.
Ribes, L. and Zalesskiĭ, P.A., On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993) 37–43. CrossRef
Steinberg, B., On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties. J. Pure Appl. Algebra 186 (2004) 91–107. CrossRef
B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted).
Tilson, B., Decomposition and complexity of finite semigroups. Semigroup Forum 3 (1971) 189–250. CrossRef
Tilson, B., Complexity of two- $\mathcal J$ -class semigroups. Adv. Math. 11 (1973) 215–237. CrossRef
B. Tilson, Depth decomposition theorem. Chapter XI in [5]SS.
B. Tilson, Complexity of semigroups and morphisms. Chapter XII in [5].
B. Tilson, Presentation lemma... the short form. (Unpublished 1995).
Y. Zalcstein, Group-complexity and reversals of finite semigroups. Math. Syst. Theor. 8 (1974/75) 235–242.