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 \{\epsilon \}$, 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 Modèle:Et al en 2001.

Contrairement aux groupes automatiques (tels que décrits notamment dans le livre d'Epstein Modèle: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 propertyModèle:Rp. 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 Modèle:Lien et les demi-groupes plongeables dans un groupe.

Demi-groupe quasi-automatique

Blanchette Modèle: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

1. $\mu (L)=S$
2. $R=\{(u,v)\in L\times L\mid \mu (u)=\mu (v)\}$
3. $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 Modèle:Et al.

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

Bibliographie

• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Chapitre
• Modèle:Article.

• Modèle:Article
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Articles liés

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