# 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 $S$ un demi-groupe et soit $A$ un ensemble fini de générateurs. Une structure automatique pour $S$ relativement à $A$ est composée d'un langage rationnel $L$ sur $A$ tel que tout élément de $S$ possède au moins un représentant dans $L$ et tel que, pour tout $a\in A\cup \{\varepsilon \}$, la relation composée des couples $(u,v)$, avec $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. en 2001.
Contrairement aux groupes automatiques (tels que décrits notamment dans le livre d'Epstein et al.), 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.

### 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é qu'il est indécidable si un monoïde automatique possède un inverse à droite.
Cain 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.

## 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$^{: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. Toutefois, la caractérisation peut être étendue à certains demi-groupes « proches » de groupes, notamment les demi-groupes complètement simples (en) et les demi-groupes plongeables dans un groupe.

## Demi-groupe quasi-automatique

Blanchette et al. introduisent une généralisation des demi-groupes automatiques appelés quasi-automatiques.
Soit $S$ un demi-groupe et soit $A$ un ensemble fini de générateurs. Soit $\mu :A^{+}\to S$ qui associe à un mot $w$ l'élément $\mu (w)$ de $S$ représenté par $w$. Une structure quasi-automatique pour $S$ est formée d'un langage $L$ sur $A$ et, pour toute lettre $a$, d'une relation rationnelle $R_{a}\subset A^{+}\times A^{+}$ telles que
* $\mu (L)=S$
* $R=\{(u,v)\in L\times L\mid \mu (u)=\mu (v)\}$
* $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. Ils contiennent aussi les demi-groupes automatiques asynchrones de Wei et al..
Une autre variante est celle de Paul Mercat ; ces demi-groupes sont appelés fortement automatiques.