Demi-groupe automatique

En mathématiques et en informatique théorique, un demi-groupe automatique est un demi-groupe finiment engendré équipé de langages rationnels sur un alphabet représentant l'ensemble des générateurs. Un de ces langages détermine des « formes canoniques » des éléments du demi-groupe, les autres langages permettent de déterminer si deux formes canoniques peuvent se déduire l'une de l’autre par multiplication avec un générateur.

Définition

Formellement, soit ${\displaystyle S}$ un demi-groupe et soit ${\displaystyle A}$ un ensemble fini de générateurs. Une structure automatique pour ${\displaystyle S}$ relativement à ${\displaystyle A}$ est composée d'un langage rationnel ${\displaystyle L}$ sur ${\displaystyle A}$ tel que tout élément de ${\displaystyle S}$ possède au moins un représentant dans ${\displaystyle L}$ et tel que, pour tout ${\displaystyle a\in A\cup \{\varepsilon \}}$, la relation composée des couples ${\displaystyle (u,v)}$, avec ${\displaystyle ua=v}$ est une relation rationnelle. La notion de demi-groupe automatique est une généralisation de celle des groupes automatiques, généralisation introduite par Campbell et al.[1] en 2001.

Contrairement aux groupes automatiques (tels que décrits notamment dans le livre d'Epstein et al.[2]), un demi-groupe peut posséder une structure automatique pour un ensemble de générateurs sans en posséder nécessairement pour un autre. Toutefois, un demi-groupe automatique avec identité, donc un monoïde automatique, possède une structure automatique relativement à tout ensemble de générateurs[3].

Exemples

Le demi-groupe bicyclique est automatique ; tout sous-demi-groupe finiment engendré d'un demi-groupe libre est automatique.

Problèmes de décision

Comme pour les groupes automatiques, le problème des mots est décidable en temps quadratique pour les demi-groupes automatiques. Kambites et Otto ont prouvé[4] qu'il est indécidable si un monoïde automatique possède un inverse à droite.

Cain[5] a démontré que la simplifiabilité et la simplifiabilité à gauche sont tous deux indécidables pour les demi-groupes automatiques. En revanche, la simplifiabilité à droite est décidable pour les demi-groupes automatiques[6].

Un caractérisation géométrique

Les structures automatiques de groupes admettent une caractérisation géométrique élégante appelée fellow traveller property[2]: ch. 2. Les structures automatiques de groupes possèdent la fellow traveller property mais ne sont en général pas caractérisées par elle[1]. Toutefois, la caractérisation peut être étendue à certains demi-groupes « proches » de groupes, notamment les demi-groupes complètement simples (en)[7] et les demi-groupes plongeables dans un groupe[8].

Demi-groupe quasi-automatique

Blanchette et al.[9] introduisent une généralisation des demi-groupes automatiques appelés quasi-automatiques.

Soit ${\displaystyle S}$ un demi-groupe et soit ${\displaystyle A}$ un ensemble fini de générateurs. Soit ${\displaystyle \mu :A^{+}\to S}$ qui associe à un mot ${\displaystyle w}$ l'élément ${\displaystyle \mu (w)}$ de ${\displaystyle S}$ représenté par ${\displaystyle w}$. Une structure quasi-automatique pour ${\displaystyle S}$ est formée d'un langage ${\displaystyle L}$ sur ${\displaystyle A}$ et, pour toute lettre ${\displaystyle a}$, d'une relation rationnelle ${\displaystyle R_{a}\subset A^{+}\times A^{+}}$ telles que

1. ${\displaystyle \mu (L)=S}$
2. ${\displaystyle R=\{(u,v)\in L\times L\mid \mu (u)=\mu (v)\}}$
3. ${\displaystyle R_{a}=\{(u,v)\in L\times L\mid \mu (ua)=\mu (v)\}}$

Les demi-groupes quasi-automatiques sont strictement plus généraux que les demi-groupes quasi-automatiques ci-dessus, et aussi que les demi-groupes rationnels tels que définis par Pelletier et Sakarovitch[10]. Ils contiennent aussi les demi-groupes automatiques asynchrones de Wei et al.[11].

Une autre variante est celle de Paul Mercat[12] ; ces demi-groupes sont appelés fortement automatiques.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « automatic semigroup » (voir la liste des auteurs).

1. Campbell et al. Thomas.
2. Epstein et al. 1992.
3. Duncan, Robertson et Ruskuc 1999.
4. Kambites et Otto 2006.
5. Cain 2006.
6. Silva et Steinberg 2004.
7. Campbell et al. 2002.
8. Cain, Robertson et Ruskuc 2006.
9. Blanchette, Choffrut et Reutenauer 2019.
10. Pelletier et Sakarovitch 1990.
11. Wei, Wang et Deng 2010.
12. Mercat 2013.

Bibliographie

• Benjamin Blanchette, Christian Choffrut et Christophe Reutenauer, « Quasi-automatic semigroups », Theoretical Computer Science, vol. 777,‎ 2019, p. 111–120 (DOI 10.1016/j.tcs.2019.01.002, arXiv 1906.02842).
• Alan J. Cain, « Cancellativity is undecidable for automatic semigroups », Quarterly Journal of Mathematics, vol. 57, n^o 3,‎ 2006, p. 285–295 (DOI 10.1093/qmath/hai023, CiteSeer^x 10.1.1.106.6068)
• Alan J. Cain, Edmund F. Robertson et Nik Ruskuc, « Subsemigroups of groups: presentations, Malcev presentations, and automatic structures », Journal of Group Theory, vol. 9, n^o 3,‎ 2006, p. 397–426 (DOI 10.1515/JGT.2006.027).
• Colin M. Campbell, Edmund F. Robertson, Nik Ruskuc et Richard M. Thomas, « Automatic semigroups », Theoretical Computer Science, vol. 250, n^os 1–2,‎ 2001, p. 365–391 (DOI 10.1016/S0304-3975(99)00151-6, lire en ligne).
• Colin M. Campbell, Edmund F. Robertson, Nik Ruskuc et Richard M. Thomas, « Automatic completely simple semigroups », Acta Mathematica Hungarica, vol. 95, n^o 3,‎ 2002, p. 201–215 (DOI 10.1023/A:1015632704977).
• Andrew J. Duncan, Edmund Frederick Robertson et Nik Ruškuc, « Automatic monoids and change of generators », Mathematical Proceedings of the Cambridge Philosophical Society, vol. 127, n^o 3,‎ 1999, p. 403–409 (MR 1713118, zbMATH 0941.20065).
• (en) David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson et William P. Thurston, Word Processing in Groups, Boston, MA, Jones and Bartlett Publishers, 1992, 330 p. (ISBN 0-86720-244-0).
• Michael Hoffmann, Dietrich Kuske, Friedrich Otto et Richard M. Thomas, « Some relatives of automatic and hyperbolic groups », dans Gracinda M. S. Gomes, Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001, Singapore, World Scientific, 2002 (zbMATH 1031.20047), p. 379–406
• Michael Hoffmann et Richard M. Thomas, « A geometric characterization of automatic semigroups », Theoretical Computer Science, vol. 369, n^os 1-3,‎ 2006, p. 300–313 (DOI 10.1016/j.tcs.2006.09.008).

• Mark Kambites et Friedrich Otto, « Uniform decision problems for automatic semigroups », Journal of Algebra, vol. 303, n^o 2,‎ 2006, p. 789–809 (DOI 10.1016/j.jalgebra.2005.11.028, arXiv math/0509349)
• Paul Mercat, « Strongly automatic semigroups », Bulletin de la Société mathématique de France, vol. 141, n^o 3,‎ 2013, p. 423–479 (DOI 10.24033/bsmf.2653, lire en ligne)
• Maryse Pelletier et Jacques Sakarovitch, « Easy multiplications II. Extensions of rational semigroups », Information and Computation, vol. 88, n^o 1,‎ 1990, p. 18–59 (DOI 10.1016/0890-5401(90)90003-Z).
• Pedro V. Silva et Benjamin Steinberg, « A geometric characterization of automatic monoids », Quarterly Journal of Mathematics, vol. 55, n^o 3,‎ 2004, p. 333-356 (DOI 10.1093/qmath/hah006, zbMATH 1076.20041, CiteSeer^x 10.1.1.36.1681).
• Lin Wei, Xiaofeng Wang et Li Deng, « Geometric properties and asynchronously automatic semigroups », Southeast Asian Bulletin of Mathematics, vol. 34, n^o 6,‎ 2010, p. 1043–1054 (zbMATH 1224.20081).

Articles liés

• Groupe automatique
• Relation rationnelle
• Demi-groupe
• Langage rationnel