Semiautomaton

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.

À 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.

Publications associées (5)

Unités associées (1)

Concepts associés (11)

Séances de cours associées (3)

Semigroup action

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup (using the semigroup operation) is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set.

String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. A string is a finite sequence of characters. The empty string is denoted by . The concatenation of two string and is denoted by , or shorter by . Concatenating with the empty string makes no difference: .

Demi-groupe de transformations

En algèbre, un demi-groupe de transformations est un ensemble de fonctions d'un ensemble X dans lui-même qui est fermé pour l'opération de composition. S'il contient l'application identité, c'est un monoïde de transformations. C'est l'analogue, pour les demi-groupes, d'un groupe de permutations. Un analogue du théorème de Cayley vaut pour les demi-groupes : tout demi-groupe est isomorphe à un demi-groupe de transformations sur un ensemble. Un demi-groupe de transformations est un couple , où est un ensemble, et est un demi-groupe de transformations sur .

Groupes autosimilaires: Aut(X*) et ses sous-groupes

Explore l'autosimilarité en groupes, en se concentrant sur Aut(X*) et ses sous-groupes.

Preuve de l'embouteillage : stratégie MATH-680: Monstrous moonshine

Couvre la stratégie de preuve de Borcherds, en soulignant la signification des racines simples et des vecteurs Weyl.

Endomorphismes et automorphismes des groupes compacts locaux totalement déconnectés III

Explore les propriétés des endomorphismes et des automorphismes des groupes compacts locaux, en mettant l'accent sur l'invariance, la théorie de la représentation des arbres et les sous-groupes minimaux.

Dynamical generalizations of the Prime Number Theorem and disjointness of additive and multiplicative semigroup actions

Florian Karl Richter

We establish two ergodic theorems which have among their corollaries numerous classical results from multiplicative number theory, including the Prime Number Theorem, a theorem of Pillai-Selberg, a theorem of Erd\H{o}s-Delange, the mean value theorem of Wi ...

2020

New Approach to Identifying Critical Initial Conditions for Extreme Flood Simulations in a Semicontinuous Simulation Framework

Anton Schleiss, Javier García Hernández, Bettina Schaefli, Fränz Zeimetz, Guillaume Mathieu Artigue

Extreme flood simulation with synthetic extreme precipitation events raises unavoidable questions about the choice of initial conditions. State-of-the-art extreme flood estimation frameworks propose to address these questions with the help of semicontinuou ...

2018

Deciding Conditional Termination

We address the problem of conditional termination, which is that of defining the set of initial configurations from which a given program always terminates. First we define the dual set, of initial configurations from which a non-terminating execution exis ...

Tech Univ Braunschweig2014