SemiautomatonIn mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q.
Relations de GreenEn mathématiques, les relations de Green sont cinq relations d'équivalence qui décrivent les éléments d'un demi-groupe par les idéaux principaux qu’ils engendrent. Les relations sont nommées d'après James Alexander Green, qui les a introduites dans un article paru en 1951. Les relations sont fondamentales pour comprendre la structure d'un demi-groupe : ainsi, pour John M. Howie, un théoricien bien connu des demi-groupes, ces relations sont .
Demi-groupe bicycliqueEn 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.
Monoïde syntaxiqueEn informatique théorique, et en particulier dans la théorie des automates finis, le monoïde syntaxique d'un langage formel est un monoïde naturellement attaché au langage. L'étude de ce monoïde permet de refléter certaines propriétés combinatoires du langage par des caractéristiques algébriques du monoïde. L'exemple le plus célèbre de cette relation est la caractérisation, due à Marcel-Paul Schützenberger, des langages rationnels sans étoile (que l'on peut décrire par des expressions rationnelles avec complément mais sans l'étoile de Kleene) : ce sont les langages dont le monoïde syntaxique est fini et apériodique, c'est-à-dire ne contient pas de sous-groupe non trivial.
Free monoidIn abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
Demi-groupeEn mathématiques, plus précisément en algèbre générale, un demi-groupe (ou semi-groupe) est une structure algébrique constituée d'un ensemble muni d'une loi de composition interne associative. Il est dit commutatif si sa loi est de plus commutative. Un demi-groupe est un magma associatif. Un monoïde est un demi-groupe unifère, c'est-à-dire possédant un élément neutre. L'ensemble des entiers naturels non nuls muni de l'addition est un demi-groupe. Tout monoïde est un demi-groupe. Tout groupe est un demi-groupe.
