no. 3
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 : 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
Mot clés : semi-groupes, monoïdes, présentation finie, automaticité, automates finis, langages rationnels, nombres algébriques, nombres de Salem, développements $\beta $-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://www.numdam.org/articles/10.24033/bsmf.2653/}
}
TY  - JOUR
AU  - Mercat, Paul
TI  - Strongly automatic semigroups
JO  - Bulletin de la Société Mathématique de France
PY  - 2013
SP  - 423
EP  - 479
VL  - 141
IS  - 3
PB  - Société mathématique de France
UR  - http://www.numdam.org/articles/10.24033/bsmf.2653/
DO  - 10.24033/bsmf.2653
LA  - en
ID  - BSMF_2013__141_3_423_0
ER  - 
%0 Journal Article
%A Mercat, Paul
%T Strongly automatic semigroups
%J Bulletin de la Société Mathématique de France
%D 2013
%P 423-479
%V 141
%N 3
%I Société mathématique de France
%U http://www.numdam.org/articles/10.24033/bsmf.2653/
%R 10.24033/bsmf.2653
%G en
%F BSMF_2013__141_3_423_0
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://www.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

[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

[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

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

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

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

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

Cité par Sources :