Demi-groupe automatique

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.

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

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

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.