An effective lower bound for group complexity of finite semigroups and automata

Henckell, Karsten; Rhodes, John; Steinberg, Benjamin

doi:10.1090/S0002-9947-2011-05379-1

An effective lower bound for group complexity of finite semigroups and automata
HTML articles powered by AMS MathViewer

by Karsten Henckell, John Rhodes and Benjamin Steinberg PDF

Trans. Amer. Math. Soc. 364 (2012), 1815-1857 Request permission

Abstract:

The question of computing the group complexity of finite semigroups and automata was first posed in K. Krohn and J. Rhodes, Complexity of finite semigroups, Annals of Mathematics (2) 88 (1968), 128–160, motivated by the Prime Decomposition Theorem of K. Krohn and J. Rhodes, Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines, Transactions of the American Mathematical Society 116 (1965), 450–464. Here we provide an effective lower bound for group complexity.

References

Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
Jorge Almeida and Benjamin Steinberg, On the decidability of iterated semidirect products with applications to complexity, Proc. London Math. Soc. (3) 80 (2000), no. 1, 50–74. MR 1719180, DOI 10.1112/S0024611500012144
Jorge Almeida and Benjamin Steinberg, Syntactic and global semigroup theory: a synthesis approach, Algorithmic problems in groups and semigroups (Lincoln, NE, 1998) Trends Math., Birkhäuser Boston, Boston, MA, 2000, pp. 1–23. MR 1750489
C. J. Ash, Inevitable graphs: a proof of the type $\textrm {II}$ conjecture and some related decision procedures, Internat. J. Algebra Comput. 1 (1991), no. 1, 127–146. MR 1112302, DOI 10.1142/S0218196791000079
K. Auinger, A new proof of the Rhodes type II conjecture, Internat. J. Algebra Comput. 14 (2004), no. 5-6, 551–568. International Conference on Semigroups and Groups in honor of the 65th birthday of Prof. John Rhodes. MR 2104770, DOI 10.1142/S0218196704001918
Beverly Austin, Karsten Henckell, Chrystopher Nehaniv, and John Rhodes, Subsemigroups and complexity via the presentation lemma, J. Pure Appl. Algebra 101 (1995), no. 3, 245–289. MR 1348570, DOI 10.1016/0022-4049(94)00063-O
T. A. Dowling, A class of geometric lattices based on finite groups, J. Combinatorial Theory Ser. B 14 (1973), 61–86. MR 307951, DOI 10.1016/s0095-8956(73)80007-3
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
Karsten Henckell, Pointlike sets: the finest aperiodic cover of a finite semigroup, J. Pure Appl. Algebra 55 (1988), no. 1-2, 85–126. MR 968571, DOI 10.1016/0022-4049(88)90042-4
Karsten Henckell, Stuart W. Margolis, Jean-Eric Pin, and John Rhodes, Ash’s type $\textrm {II}$ theorem, profinite topology and Mal′cev products. I, Internat. J. Algebra Comput. 1 (1991), no. 4, 411–436. MR 1154442, DOI 10.1142/S0218196791000298
Karsten Henckell, John Rhodes, and Benjamin Steinberg, Aperiodic pointlikes and beyond, Internat. J. Algebra Comput. 20 (2010), no. 2, 287–305. MR 2646752, DOI 10.1142/S0218196710005662
Karsten Henckell, John Rhodes, and Benjamin Steinberg, A profinite approach to stable pairs, Internat. J. Algebra Comput. 20 (2010), no. 2, 269–285. MR 2646751, DOI 10.1142/S0218196710005650
Joel Karnofsky and John Rhodes, Decidability of complexity one-half for finite semigroups, Semigroup Forum 24 (1982), no. 1, 55–66. MR 645703, DOI 10.1007/BF02572755
Kenneth Krohn and John Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450–464. MR 188316, DOI 10.1090/S0002-9947-1965-0188316-1
Kenneth Krohn and John Rhodes, Complexity of finite semigroups, Ann. of Math. (2) 88 (1968), 128–160. MR 236294, DOI 10.2307/1970558
K. Krohn, J. Rhodes, and B. Tilson. Algebraic theory of machines, languages, and semigroups. Edited by Michael A. Arbib. With a major contribution by Kenneth Krohn and John L. Rhodes. Academic Press, New York, 1968. Chapters 1, 5–9.
Stuart W. Margolis, $k$-transformation semigroups and a conjecture of Tilson, J. Pure Appl. Algebra 17 (1980), no. 3, 313–322. MR 579091, DOI 10.1016/0022-4049(80)90053-5
Stuart W. Margolis and Bret Tilson, An upper bound for the complexity of transformation semigroups, J. Algebra 73 (1981), no. 2, 518–537. MR 640046, DOI 10.1016/0021-8693(81)90332-X
J. McCammond, J. Rhodes, and B. Steinberg. Geometric semigroup theory. Internat. J. Algebra Comput., to appear.
John Rhodes, The fundamental lemma of complexity for arbitrary finite semigroups, Bull. Amer. Math. Soc. 74 (1968), 1104–1109. MR 232873, DOI 10.1090/S0002-9904-1968-12064-6
John Rhodes, Algebraic theory of finite semigroups. Structure numbers and structure theorems for finite semigroups, Semigroups (Proc. Sympos., Wayne State Univ., Detroit, Mich., 1968) Academic Press, New York, 1969, pp. 125–162. MR 0281817
John Rhodes, Proof of the fundamental lemma of complexity (weak version) for arbitrary finite semigroups, J. Combinatorial Theory Ser. A 10 (1971), 22–73. MR 274615, DOI 10.1016/0097-3165(71)90064-1
J. Rhodes. Axioms for complexity for all finite semigroups. Advances in Math., 11(2):210–214, 1973.
John Rhodes, Proof of the fundamental lemma of complexity (strong version) for arbitrary finite semigroups, J. Combinatorial Theory Ser. A 16 (1974), 209–214. MR 338235, DOI 10.1016/0097-3165(74)90045-4
John Rhodes, Kernel systems—a global study of homomorphisms on finite semigroups, J. Algebra 49 (1977), no. 1, 1–45. MR 463337, DOI 10.1016/0021-8693(77)90265-4
J. Rhodes. Flows on automata. Technical report, Center for Pure & Applied Mathematics, University of California, Berkeley, CA 94720-3840, 1995.
John Rhodes and Benjamin Steinberg, Krohn-Rhodes complexity pseudovarieties are not finitely based, Theor. Inform. Appl. 39 (2005), no. 1, 279–296. MR 2132592, DOI 10.1051/ita:2005016
John Rhodes and Benjamin Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity, Internat. J. Algebra Comput. 16 (2006), no. 4, 739–748. MR 2258836, DOI 10.1142/S0218196706003177
John Rhodes and Benjamin Steinberg, The $q$-theory of finite semigroups, Springer Monographs in Mathematics, Springer, New York, 2009. MR 2472427, DOI 10.1007/b104443
John Rhodes and Bret Tilson, Local complexity of finite semigroups, Algebra, Topology, and category theory (collection of papers in honor of Samuel Eilenberg), Academic Press, New York, 1976, pp. 149–168. MR 0432792
John Rhodes and Bret R. Tilson, Lower bounds for complexity of finite semigroups, J. Pure Appl. Algebra 1 (1971), no. 1, 79–95. MR 285649, DOI 10.1016/0022-4049(71)90012-0
John Rhodes and Bret R. Tilson, Improved lower bounds for the complexity of finite semigroups, J. Pure Appl. Algebra 2 (1972), 13–71. MR 299708, DOI 10.1016/0022-4049(72)90022-9
Luis Ribes and Pavel A. Zalesskii, On the profinite topology on a free group, Bull. London Math. Soc. 25 (1993), no. 1, 37–43. MR 1190361, DOI 10.1112/blms/25.1.37
Benjamin Steinberg, On aperiodic relational morphisms, Semigroup Forum 70 (2005), no. 1, 1–43. MR 2107191, DOI 10.1007/s00233-004-0148-7
J. P. Stiffler. Extension of the fundamental theorem of finite semigroups. Advances in Math., 11(2):159–209, 1973.
Bret Tilson, Decomposition and complexity of finite semigroups, Semigroup Forum 3 (1971/72), no. 3, 189–250. MR 296201, DOI 10.1007/BF02572961
B. Tilson. Complexity of two$\mathscr J$-class semigroups. Advances in Math., 11(2):215–237, 1973.
B. Tilson, On the complexity of finite semigroups, J. Pure Appl. Algebra 5 (1974), 187–208. MR 364517, DOI 10.1016/0022-4049(74)90046-2
B. Tilson. Complexity of semigroups and morphisms, chapter XII, pages 313–384. In Eilenberg \cite{Eilenberg}, 1976.
B. Tilson. Depth decomposition theorem, chapter XI, pages 287–312. In Eilenberg \cite{Eilenberg}, 1976.
Bret Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), no. 1-2, 83–198. MR 915990, DOI 10.1016/0022-4049(87)90108-3
Bret Tilson, Type $\textrm {II}$ redux, Semigroups and their applications (Chico, Calif., 1986) Reidel, Dordrecht, 1987, pp. 201–205. MR 900660
Bret R. Tilson, Appendix to “Algebraic theory of finite semigroups”. On the $p$-length of $p$-solvable semigroups: Preliminary results, Semigroups (Proc. Sympos., Wayne State Univ., Detroit, Mich., 1968) Academic Press, New York, 1969, pp. 163–208. MR 0277636