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

Voir la notice de l'article provenant de la source Numdam

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 : 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
Mots-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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | MR | mathdoc-id

[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 :