Accueil🇫🇷Chercher

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 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 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 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[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

Bibliographie

  • Benjamin Blanchette, Christian Choffrut et Christophe Reutenauer, « Quasi-automatic semigroups », Theoretical Computer Science, vol. 777,‎ , 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, no 3,‎ , p. 285–295 (DOI 10.1093/qmath/hai023, CiteSeerx 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, no 3,‎ , 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, nos 1–2,‎ , 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, no 3,‎ , 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, no 3,‎ , 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, , 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, (zbMATH 1031.20047), p. 379–406
  • Michael Hoffmann et Richard M. Thomas, « A geometric characterization of automatic semigroups », Theoretical Computer Science, vol. 369, nos 1-3,‎ , p. 300–313 (DOI 10.1016/j.tcs.2006.09.008).

Articles liés

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.