**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Semiautomaton

Summary

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (5)

Related concepts (11)

Related lectures (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: .

Transformation semigroup

In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transformation (or composition) monoid. This is the semigroup analogue of a permutation group. A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being faithful, i.e., if two elements of the semigroup have the same action, then they are equal.

Self-similar groups: Aut(X*) and its subgroups

Explores self-similarity in groups, focusing on Aut(X*) and its subgroups.

Borcherds' Proof: Strategy

Covers Borcherds' proof strategy, emphasizing the significance of simple roots and Weyl vectors.

Endomorphisms and automorphisms of totally disconnected locally compact groups III

Explores the properties of endomorphisms and automorphisms of locally compact groups, emphasizing invariance, tree representation theory, and minimal subgroups.

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

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

2020Anton 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