Strongly automatic semigroups
Bulletin de la Société Mathématique de France, Volume 141 (2013) no. 3, p. 423-479

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

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.

DOI : https://doi.org/10.24033/bsmf.2653
Classification:  20M17,  20M05,  20M35,  11A63,  68R15
Keywords: semigroups, monoids, finite presentation, automaticity, finite-state automatons, regular languages, algebraic numbers, Salem numbers, radix expansions, growth
@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},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {141},
     number = {3},
     year = {2013},
     pages = {423-479},
     doi = {10.24033/bsmf.2653},
     language = {en},
     url = {http://www.numdam.org/item/BSMF_2013__141_3_423_0}
}
Mercat, Paul. Strongly automatic semigroups. Bulletin de la Société Mathématique de France, Volume 141 (2013) no. 3, pp. 423-479. doi : 10.24033/bsmf.2653. http://www.numdam.org/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