Demi-groupe bicyclique

En mathématiques, et en informatique théorique, le demi-groupe bicyclique est un demi-groupe particulier. Cet objet est important dans la théorie structurelle des demi-groupes et un important exemple de monoïde syntaxique. Même s'il est appelé demi-groupe bicyclique, c'est en fait un monoïde. La première description dans la littérature en a été donnée par Evgenii Sergeevich Lyapin en 1953. Alfred H. Clifford et Gordon Preston, dans leur livre, disent que l'un d'entre eux avait découvert ce monoïde avant 1943, en collaboration avec David Rees, mais n'avait pas publié le résultat. Il existe plusieurs méthodes de construction du demi-groupe bicyclique, et plusieurs notations pour le désigner. Lyapin le note ; Clifford et Preston emploient la notation ; les livres plus récents tendent à utiliser . C'est cette notation qui est adoptée ici. Le demi-groupe bicyclique est le quotient du demi-groupe libre sur deux générateurs et , par la congruence engendré par la relation (voir « »). En d'autre termes, tout élément du demi-groupe est un mot sur et , avec la condition que le facteur n'apparaît pas dans le mot. L'opération du demi-groupe est la concaténation de mots, suivie d'une réduction par la relation si nécessaire ; elle est clairement associative. On peut montrer que tout élément de est en fait de la forme , pour des entiers naturels et . L'opération de composition admet alors l'expression : (qa pb) (qc pd) = qa + c − min{b, c} pd + b − min{b, c}. Dans la construction précédente, l'opération s'exprime sur les exposants des éléments. Ceci suggère que les symboles et peuvent être omis, ne laissant subsister que les opérations sur les exposants et . Ainsi, s'identifie à l'ensemble des couples d'entiers naturels (y compris zéro) avec l'opération suivante : (a, b) (c, d) = (a + c − min{b, c}, d + b − min{b, c}). Ceci définit , comme dans la première construction, sauf qu'ici, a les deux générateurs et , et l'élément neutre . Si trois éléments , et d'un demi-groupe vérifient les conditions suivantes : alors le demi-groupe engendré par et est isomorphe au demi-groupe bicyclique.