Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Semiautomaton
Résumé
In 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. This may be viewed either as an action of the free monoid of strings in the input alphabet Σ, or as the induced transformation semigroup of Q.
In older books like Clifford and Preston (1967) semigroup actions are called "operands".
In , semiautomata essentially are functors.
semigroup action
A transformation semigroup or transformation monoid is a pair consisting of a set Q (often called the "set of states") and a semigroup or monoid M of functions, or "transformations", mapping Q to itself. They are functions in the sense that every element m of M is a map . If s and t are two functions of the transformation semigroup, their semigroup product is defined as their function composition .
Some authors regard "semigroup" and "monoid" as synonyms. Here a semigroup need not have an identity element; a monoid is a semigroup with an identity element (also called "unit"). Since the notion of functions acting on a set always includes the notion of an identity function, which when applied to the set does nothing, a transformation semigroup can be made into a monoid by adding the identity function.
Let M be a monoid and Q be a non-empty set. If there exists a multiplicative operation
which satisfies the properties
for 1 the unit of the monoid, and
for all and , then the triple is called a right M-act or simply a right act. In long-hand, is the right multiplication of elements of Q by elements of M. The right act is often written as .
A left act is defined similarly, with
and is often denoted as .
An M-act is closely related to a transformation monoid.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.