×

On finitely generated monoids of matrices with entries in \({\mathbb{N}}\). (English) Zbl 0721.20042

Let \(\Gamma\) denote a finite set of n by n matrices over \({\mathbb{N}}\) such that the multiplicative monoid M generated by \(\Gamma\) is finite. The authors show that \(M=\{I_ n\}\cup \Gamma \cup \Gamma^ 2\cup...\cup \Gamma^ N\), where \(N=\lceil e^ 2.n!\rceil -2\). Such an N must anyway be \(\geq 2^{n-2}-1\). The exact bound is not known. In the case where \(\Gamma\) has only one element, an exact bound is \(N=\max_{0\leq \ell \leq n}(\ell +g(n-\ell))-1\), where g is Landau’s function.

MSC:

20M20 Semigroups of transformations, relations, partitions, etc.
11N45 Asymptotic results on counting functions for algebraic and topological structures
20M05 Free semigroups, generators and relations, word problems

References:

[1] ChI83. T.-H. CHAN and O. IBARRA, On the Finite-Valuedness Problem for Sequential Machines, TCS, 1983, 23, pp. 95-101. Zbl0503.68037 MR693072 · Zbl 0503.68037 · doi:10.1016/0304-3975(88)90012-6
[2] E74. S. EILENBERG, Automata, Languages, and Machines, Academic Press, New York, N.Y., 1974, A. MR530382
[3] Hs78. M. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass., 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[4] HoU79. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[5] Ja77. G. JACOB, Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices, T.C.S., 1977, 5, pp. 183-204. Zbl0388.15001 MR473075 · Zbl 0388.15001 · doi:10.1016/0304-3975(77)90006-8
[6] Ku88. W. KUICH, Finite Automata and Ambiguity, Report 253 of the IIG, Technische Universität Graz, 1988.
[7] La09. E. LANDAU, Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig, 1909. JFM40.0232.08 · JFM 40.0232.08
[8] Le87. H. LEUNG, An Algebraic Method for Solving Decision Problems in Finite Automata Theory, Ph. D. Thesis, The Pennsylvania State University, 1987.
[9] MaSi77. A MANDEL and I. SIMON, On Finite Semigroups of Matrices, T.C.S., 1977, 5, pp. 101-111. Zbl0368.20049 MR473070 · Zbl 0368.20049 · doi:10.1016/0304-3975(77)90001-9
[10] Ms84.1. J.-P. MASSIAS, Ordre maximum d’un élément du groupe symétrique et applications, Thèse 3e cycle, Université de Limoges, 1984.
[11] Ms84.2. J.-P. MASSIAS, Majoration explicite de l’ordre maximum d’un élément du groupe symétrique, Annales Faculté des Sciences Toulouse, 1984, VI, pp. 269-281. Zbl0574.10043 MR799599 · Zbl 0574.10043 · doi:10.5802/afst.612
[12] MsNRo88. J.-P. MASSIAS, J.-L. NICOLAS and G. ROBIN, Evaluation asymptotique de l’ordre maximum d’un élément du groupe symétrique, Acta Arithmetica, 1988, 50, pp. 221-242. Zbl0588.10049 MR960551 · Zbl 0588.10049
[13] McZ75. R. MCNAUGHTON and Y. ZALCSTEIN, The Burnside Problem for Semi-groups, J. Algebra, 1975, 34, pp. 292-299. Zbl0302.20054 MR374301 · Zbl 0302.20054 · doi:10.1016/0021-8693(75)90184-2
[14] Re77. C. REUTENAUER, Propriétés arithmétiques et topologiques de séries rationnelles en variables non commutatives, Thèse 3e cycle, Université Paris-VI, 1977.
[15] Se89. H. SEIDL, On the Finite Degree of Ambiguity of Finite Tree Automata, Acta Informatica, 1989, 26, pp. 527-542. Zbl0683.68049 MR1006265 · Zbl 0683.68049 · doi:10.1007/BF00263578
[16] Sr88. L. STAIGER, personal communication.
[17] WeSe86. A. WEBER and H. SEIDL, On the Degree of Ambiguity of Finite Automata, Proc. M.F.C.S., 1986, in: L.N.C.S. 233, Springer-Verlag, pp. 620-629. Zbl0617.68055 MR874641 · Zbl 0617.68055
[18] Tu90 P. TURAKAINEN, On the Finitness of the Multiplicative Monoid generated by a Nonnegative Matrix. Bull. EATCS, 1990, 40, pp. 270-272. Zbl0746.20047 · Zbl 0746.20047
[19] We87. A. WEBER, Über die Mehrdeutigkeit und Wertigkeit von endlichen Automaten und Transducern, Dissertation, Goethe-Universität Frankfurt am Main, 1987.
[20] WeSe88. A. WEBER and H. SEIDL, On the Degree of Ambiguity of Finite Automata, Preprint, Goethe-Universität Frankfurt am Main, 1988, T.C.S. (to appear). Zbl0738.68059 MR874641 · Zbl 0738.68059 · doi:10.1016/0304-3975(91)90381-B
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.