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 un demi-groupe et soit un ensemble fini de générateurs. Une structure automatique pour relativement à est composée d'un langage rationnel sur tel que tout élément de possède au moins un représentant dans et tel que, pour tout , la relation composée des couples , avec 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 . en 2001.
Contrairement aux groupes automatiques (tels que décrits notamment dans le livre d'Epstein .), 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. 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 . et les demi-groupes plongeables dans un groupe..
Demi-groupe quasi-automatique Blanchette . introduisent une généralisation des demi-groupes automatiques appelés quasi-automatiques.
Soit un demi-groupe et soit un ensemble fini de générateurs. Soit qui associe à un mot l'élément de représenté par . Une structure quasi-automatique pour est formée d'un langage sur et, pour toute lettre , d'une relation rationnelle telles que
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 ..
Une autre variante est celle de Paul Mercat. ; ces demi-groupes sont appelés fortement automatiques.
Notes et références
Bibliographie .
. . . . .
.
. . .
Articles liés Groupe automatique Relation rationnelle Demi-groupe Langage rationnel
Automatique Catégorie:Calculabilité