Affordable Access

On finitely generated monoids of matrices with entries in $\mathbb{N}$

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

On finitely generated monoids of matrices with entries in N INFORMATIQUE THÉORIQUE ET APPLICATIONS ANDREASWEBER HELMUT SEIDL Onfinitely generatedmonoids ofmatrices with entries inN Informatique théorique et applications, tome 25, no 1 (1991), p. 19-38. <http://www.numdam.org/item?id=ITA_1991__25_1_19_0> © AFCET, 1991, tous droits réservés. L’accès aux archives de la revue « Informatique théorique et applications » im- plique l’accord avec les conditions générales d’utilisation (http://www.numdam. org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 25, n° 1, 1991, p. 19 à 38) ON FINITELYGENERATED MONOIDS OF MATRICES WITH ENTRIES IN M (*) by Andréas WEBER (X) and Helmut SEIDL (2) Communicated by J. BERSTEL Abstract. — Let T be a nonempty, finite set of square matrices of size n with entries in the semiring N, Consider the matrix-monoid F* = \J Tx generaled by F. We show: If F* is finite, x > o N then F*= \J Fx where N= re2-n\~l - 2 . This assertion is false for any N smaller than 2n~2. If N n F has exactly one member and F* is finite\ then F* = \J Tx where A^=max (/+g (n — f))— 1 1=0 1=0 (g dénotes Landau's function). In the last assertion N is V minimal. Résumé. — Soit F un ensemble non vide et fini des matrices carrées de dimension n à entrées dans le semi-anneau N. Considérons le monoïde de matrices F*= \J Tx engendré par T. Nous x>o JV démontrons : Si F* est fini, alors F*= \J Tx où N= (~e2*«!~l — 2. Cette assertion est fausse pour x = o N chaque N plus petit que 2n~2. Si F a exactement un élément et F* est fini, alors F*= U Tx où 7V=max(/+g(n — /))— 1 (g représente la fonction de Landaü). Dans la

There are no comments yet on this publication. Be the first to share your thoughts.