Strongly automatic semigroups
[Semi-groupes fortement automatiques]
Mercat, Paul
Bulletin de la Société Mathématique de France, Tome 141 (2013), p. 423-479 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

In this paper, we introduce the notion of strongly automatic semigroup, which implies the usual notion of automaticity. We focus on semigroups of β-adics developpements, for which we obtain a criterion of strong automaticity.

Dans cet article, nous introduisons la notion de semi-groupe fortement automatique, qui entraîne la notion d’automaticité des semi-groupes usuelle. On s’intéresse particulièrement aux semi-groupes de développements en base β, pour lesquels on obtient un critère de forte automaticité.

Publié le : 2013-01-01
DOI : https://doi.org/10.24033/bsmf.2653
Classification:  20M17,  20M05,  20M35,  11A63,  68R15
Mots clés: semi-groupes, monoïdes, présentation finie, automaticité, automates finis, langages rationnels, nombres algébriques, nombres de Salem, développements β-adiques, croissance 
@article{BSMF_2013__141_3_423_0,
     author = {Mercat, Paul},
     title = {Strongly automatic semigroups},
     journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
     volume = {141},
     year = {2013},
     pages = {423-479},
     doi = {10.24033/bsmf.2653},
     language = {en},
     url = {http://dml.mathdoc.fr/item/BSMF_2013__141_3_423_0}
}

Mercat, Paul. Strongly automatic semigroups. Bulletin de la Société Mathématique de France, Tome 141 (2013) pp. 423-479. doi : 10.24033/bsmf.2653. http://gdmltest.u-ga.fr/item/BSMF_2013__141_3_423_0/

[1] J. Berstel - Transductions and context-free languages, Leitfäden der Angewandten Mathematik und Mechanik, vol. 38, B. G. Teubner, 1979. | MR 549481

[2] A. Cain - « Presentations for subsemigroups of groups », Thèse, University of St Andrews, 2005.

[3] O. Carton - Langages formels, calculabilité et complexité, Vuibert, 2008.

[4] J. Cassaigne & F. Nicolas - « On the decidability of semigroup freeness », RAIRO Theor. Inform. Appl. 46 (2012), p. 355-399. | Numdam | MR 2981675

[5] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson & W. P. Thurston - Word processing in groups, Jones and Bartlett Publishers, 1992. | MR 1161694

[6] R. Kenyon - « Projecting the one-dimensional Sierpinski gasket », Israel J. Math. 97 (1997), p. 221-238. | MR 1441250

[7] S. P. Lalley - « β-expansions with deleted digits for Pisot numbers β », Trans. Amer. Math. Soc. 349 (1997), p. 4355-4365. | MR 1451608

[8] S. Lang - Algebraic number theory, second éd., Graduate Texts in Math., vol. 110, Springer, 1994. | MR 1282723

[9] J. Sakarovitch - « Easy multiplications. I. The realm of Kleene's theorem », Inform. and Comput. 74 (1987), p. 173-197. | MR 906959