Strongly automatic semigroups
[Semi-groupes fortement automatiques]
Bulletin de la Société Mathématique de France, Tome 141 (2013) no. 3, pp. 423-479.

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é.

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},
     pages = {423--479},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {141},
     number = {3},
     year = {2013},
     doi = {10.24033/bsmf.2653},
     language = {en},
     url = {http://archive.numdam.org/articles/10.24033/bsmf.2653/}
}
Mercat, Paul. Strongly automatic semigroups. Bulletin de la Société Mathématique de France, Tome 141 (2013) no. 3, pp. 423-479. doi : 10.24033/bsmf.2653. http://archive.numdam.org/articles/10.24033/bsmf.2653/

[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