no. 1
The finiteness problem for monoids of morphisms
Honkala, Juha1 idref
1Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland
RAIRO. Theoretical Informatics and Applications, Tome 49 (2015) no. 1, pp. 61-65

We study finitely generated monoids consisting of endomorphisms of a free monoid. We give a necessary and sufficient condition for such a monoid to be infinite and show that this condition is decidable. As a special case we discuss the morphism torsion problem.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2014028
Classification : 20M05, 68Q45
Keywords: Free monoid morphism, finiteness problem, decidability

Honkala, Juha  1

1 Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland 
@article{ITA_2015__49_1_61_0,
     author = {Honkala, Juha},
     title = {The finiteness problem for monoids of morphisms},
     journal = {RAIRO. Theoretical Informatics and Applications},
     pages = {61--65},
     year = {2015},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     doi = {10.1051/ita/2014028},
     mrnumber = {3342173},
     zbl = {1314.20045},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2014028/}
}
TY  - JOUR
AU  - Honkala, Juha
TI  - The finiteness problem for monoids of morphisms
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2015
SP  - 61
EP  - 65
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2014028/
DO  - 10.1051/ita/2014028
LA  - en
ID  - ITA_2015__49_1_61_0
ER  - 
%0 Journal Article
%A Honkala, Juha
%T The finiteness problem for monoids of morphisms
%J RAIRO. Theoretical Informatics and Applications
%D 2015
%P 61-65
%V 49
%N 1
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2014028/
%R 10.1051/ita/2014028
%G en
%F ITA_2015__49_1_61_0
Honkala, Juha. The finiteness problem for monoids of morphisms. RAIRO. Theoretical Informatics and Applications, Tome 49 (2015) no. 1, pp. 61-65. doi: 10.1051/ita/2014028

J. Berstel and C. Reutenauer, Noncommutative Rational Series with Applications. Cambridge University Press (2011). | MR | Zbl

J. Cassaigne and F. Nicolas, On the decidability of semigroup freeness. RAIRO: ITA 46 (2012) 355–399. | MR | Zbl | Numdam

G. Jacob, La finitude des représentations linéaires des semi-groupes est décidable. J. Algebra 52 (1978) 437–459. | MR | Zbl | DOI

L. Kari, G. Rozenberg and A. Salomaa, L systems. In vol. 1 of Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer (1997) 253–328. | MR | Zbl

A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1977) 101–111. | MR | Zbl | DOI

R. Mcnaughton and Y. Zalcstein, The Burnside problem for semigroups. J. Algebra 34 (1975) 292–299. | MR | Zbl | DOI

A. Salomaa, On exponential growth in Lindenmayer systems. Indag. Math. 35 (1973) 23–30. | MR | Zbl | DOI

Cité par Sources :