Semiautomaton

From Wikipedia, the free encyclopedia

In mathematics and computer science, a semiautomaton or M-act is the multiplicative operation of a monoid on a set. From an algebraic point of view, it is very nearly identical to the concept of an action of a group. From the computer science point of view, it is an automaton having only an input, and no output. From the category theoretic point of view, acts are important as functors on categories.

The concept is also known under the equivalent names of S-set, M-set, M-operand, S-system, S-automata, transition system, operator monoid, transformation semigroup or transition monoid. This article takes some care to show how these all represent the same concept, despite a wide variety of notation and terminology in use.

1 Transformation semigroup
2 M-act
3 Full transformation monoid
4 Semiautomata
5 M-homomorphism
6 Properties
7 Category Act
8 References

[edit] Transformation semigroup

A transformation semigroup or transformation monoid is a pair $(M, Q)$ consisting of a set Q, (often called the "set of states"), and a monoid or semigroup M of functions, or "transformations", mapping Q to itself. They are functions in the sense that every element m of M is a map $m:Q\to Q$ . If s and t are two different elements of the transformation semigroup, then the semigroup product follows trivially from function composition, so that one defines $(s t)(q)$ as $(s\circ t)(q)=s(t(q))$ . The transformation semigroup is exactly the same thing as an M-act, defined below, using a slightly more abstract language.

A note on the use of "semigroup" versus "monoid": Although some authors define these two to be the same thing, many others (including Wikipedia) make a distinction: a monoid is a semigroup with an identity element; a semigroup is almost a monoid except that it may not have an identity element. Since the notion of functions acting on a set always includes the notion of an identity function, which applied to the set, does nothing, the transformation semigroup is more precisely called a transformation monoid. From here on out, the term "monoid" will be used.

[edit] M-act

Let M be a monoid and Q be a non-empty set. If there exists a multiplicative operation

$\mu: Q\times M \to Q$

$(q,m)\mapsto qm=\mu(q,m)$

which satisfies the properties

q 1 = q

for 1 the unit of the monoid, and

q (s t) = (q s) t

for all $q\in Q$ and $s,t\in M$ , then the triple $(Q, M,μ)$ 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 $Q M$ .

The left act is defined similarly, with

$\mu: M\times Q \to Q$

$(m,q)\mapsto mq=\mu(m,q)$

and is often denoted as $\,_MQ$ .

Although the M-act is exactly the same thing as the transformation semigroup defined above, note a subtle shift in terminology: the elements of M need not be functions per se, they are just elements of some monoid. Therefore, one must demand that the action of $μ$ be consistent with multiplication in the monoid (i.e. $μ(q, s t) = μ(μ(q, s), t)$ ), as, in general, this might not hold for some arbitrary $μ$ , in the way that it does for function composition. Once one makes this demand of consistency, the two amount to the same thing.

Furthermore, once one makes this demand, it is completely safe to drop all parenthesis, as the monoid product and the action of the monoid on the set are completely associative. In particular, this allows elements of the monoid to be represented as strings of letters, in the computer-science sense of the word "string". This abstraction then allows one to talk about string operations in general, and eventually leads to the concept of formal languages as being composed of strings of letters.

[edit] Full transformation monoid

The full transformation monoid (or full transformation semigroup) is the collection of all maps $m:Q\to Q$ . The full transformation monoid is a free monoid, in that all possibilities are allowed. A special case of the full transformation monoid is the permutation group. This consists only of those functions that shuffle around the elements of Q.

[edit] Semiautomata

A semiautomaton is a triple $(Q,Σ, T)$ where $Σ$ is a non-empty set, called the input alphabet, Q is a non-empty set, called the set of states, and T is the transition function,

$T: Q\times \Sigma \to Q$

When the set of states Q is a finite set (it need not be!), a semiautomaton may be thought of as a deterministic finite automaton $(Q,Σ, T, q 0, A)$ , but without the initial state $q 0$ or set of accept states A. Alternately, it is a finite state machine which has no output, and only an input.

One of the primary claims of monoid theory is that semiautomata are equivalent to acts; so that for any act, there is a unique semiautomaton, and conversely, for any semiautomaton, there is a unique act. This may be demonstrated as follows.

Let $Σ *$ be the free monoid generated by the alphabet $Σ$ , (so that the superscript * is understood to be the Kleene star); it is the set of all finite-length strings composed of the letters in $S i g m a$ .

For every word w in $Σ *$ , let $T_w:Q\to Q$ be the function, defined recursively, as follows, for all q in Q:

If $w=\varepsilon$ , then $T_\varepsilon(q)=q$ , so that the empty word $\varepsilon$ does not change the state.

If $w = σ$ is a letter in $Σ$ , then $T σ (q) = T (q,σ)$ .

If $w = σ v$ for $\sigma\in\Sigma$ and $v\in \Sigma^*$ , then $T w (q) = T v (T σ (q))$ .

Let $M (Q,Σ, T)$ be the set

$M(Q,\Sigma,T)=\{T_w \vert w\in\Sigma^* \}$

The set $M (Q,Σ, T)$ is closed under function composition; that is, for all $v,w\in\Sigma^*$ , one has $T_w\circ T_v=T_{vw}$ . It also contains $T_\varepsilon$ , which is the identity function on S. Since function composition is by definition associative, the set $M (Q,Σ, T)$ is a monoid: it is called the input monoid, characteristic monoid, characteristic semigroup or transition monoid of the semiautomaton $(Q,Σ, T)$ .

[edit] M-homomorphism

An M-homomorphism is a map

$f:Q_M\to B_M$

such that

f (q m) = f (q) m

for all $q\in Q$ and $m\in M$ . The set of all M-homomorphisms is commonly written as $Hom(Q M, B M)$ or $Hom M (Q, B)$ .

[edit] Properties

If the set of states Q is finite, then the transition functions are commonly represented as state transition tables. The construction of all possible transitions driven by strings in the free group has a graphical depiction as de Bruijn graphs.

The set of states Q need not be finite, or even countable. As an example, semiautomata underpin the concept of quantum finite automata. There, the set of states Q are given by the complex projective space $\mathbb{C}P^n$ , and individual states are referred to as n-state qubits. State transitions are given by unitary n×n matrices. The input alphabet $Σ$ remains finite, and other typical concerns of automata theory remain in play. Thus, the quantum semiautomaton may be simply defined as the triple $(\mathbb{C}P^n,\Sigma,\{U_{\sigma_1},U_{\sigma_2},\cdots,U_{\sigma_p},\})$ when the alphabet $Σ$ has p letters, so that there is one unitary matrix $U σ$ for each letter $\sigma\in\Sigma$ . Stated in this way, it is obvious that the quantum semiautomaton has many geometrical generalizations. Thus, for example, one may take a Riemannian symmetric space in place of $\mathbb{C}P^n$ , and selections from its group of isometries as transition functions.

The syntactic monoid of a formal language is isomorphic to the transition monoid of the minimal automaton accepting the language.

[edit] Category Act

The algebraic relations defining a right action form a category Act. The objects are the M-acts,and the morphisms of the category are the M-homomorphisms.

[edit] References

John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories (2000), Walter de Gruyter, Berlin ISBN 3-11-015248-7
A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups. American Mathematical Society, (1961) volume 1, (1967) volume 2.
F. Gecseg and I. Peak, Algebraic Theory of Automata (1972), Akademiai Kiado, Budapest.
Nico F. Benschop, Associative Digital Network Theory An Associative Algebra Approach to Logic, Arithmetic and State Machines (2003) Amspade Research, Geldrop, The Netherlands.

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Semiautomaton

From Wikipedia, the free encyclopedia

Contents

[edit] Transformation semigroup

[edit] M-act

[edit] Full transformation monoid

[edit] Semiautomata

[edit] M-homomorphism

[edit] Properties

[edit] Category Act

[edit] References

Views

Navigation

Interaction

Search

Languages