Injective Morphisms of the Machine Semigroups
by
Jānis Buls
Department of Mathematics, University of Latvia
Coauthors: Ieva Zandere

Simulation was first discussed by Hartmanis [2] more than forty years ago. This concept describes the possibility on abstract level in which one machine could be replaced by other in applications, for example, cryptography, especially, cryptanalysis of cryptographic devices. If we like to treet the machines by semigroups as it done till now and develop the theory not only as selfsufficient discipline the connections between simulation and semigroups should be considered from every point of view too. Thus we say that a transition from machines to semigroups through some representation is successful if it adequatly characterizes the simulation.

Let V=<Q, A, B, o , * > be a Mealy machine, where Q, A, B are finite, nonempty sets; o : Q×A --> Q is a function and * : Q×A --> B is a surjective function. Let T(Q) denote the semigroup of all transformations on the set Q and let Fun(Q, B) denote the set of all maps from Q to B. On the set     S(Q, B)=T(Q)×Fun(Q, B)    define the multiplication by     (g₁, p₁)(g₂, p₂)=(g₁g₂, g₁p₂)     where g₁, g₂ are elements of T(Q) and p₁, p₂ are elements of Fun(Q, B). Under this operation S(Q, B) is easily seen to be a semigroup. Let    Q={ q₁, q₂, ... , q_k}, A={a₁, a₂, ... , a_m},     B={b₁, b₂, ... , b_n}. Define two mappings f₁ : A --> T(Q) and f₂ : A --> Fun(Q, B) as follows. For each element a_i of A define f₁(a_i) as element of T(Q) and f₂(a_i) as element of Fun(Q, B) by

f1(ai)= æ ç è q1 q2 ... qk q'1 q'2 ... q'k ö ÷ ø ,       f2(ai)= æ ç è q1 q2 ... qk b'1 b'2 ... b'k ö ÷ ø ,

where for every s (q'_s=q_s o a_i /\ b'_s=q_s * a_i). Now the representation f₀ : A --> S(Q, B) is defined [4] by setting f₀ (a_i)=(f₁ (a_i), f₂ (a_i)). The semigroup <V> generated by f₀(A) is called the machine V semigroup.

Definition 1 [1]. Let V=<Q, A, B>, 'V=<'Q, 'A, 'B> be machines. We say that 'V simulates V by

h1 : Q --> 'Q,     h2 : A --> 'A*,    h3 : 'B* --> B       if

q o u * a=h₃(h₁(q) o h₂(u) * h₂(a))   for all elements   (q, u, a) of Q×A^*×A.

We generalize the concept of similar transformation semigroups [3] to machine semigroups as follows.

Definition 2. Let V=<Q, A, B >, 'V=<'Q, 'A, 'B > be machines. We say that \psi: <V> --> <'V> is the s-morphism of machine semigroup <V> to <'V> if there exist maps g : Q --> 'Q,   h : B --> 'B such that the diagram

Q × Q \sigma -->   Q × B g \downarrow \downarrow g g \downarrow \downarrow h 'Q × 'Q \psi(\sigma) -->   'Q × 'B

commutes for every \sigma of <V>. If h is an injection the s-morphism is called the injective s-morphism. We say an s-morphism
\psi: <V> --> <'V> is an s-homomorphism if it is a semigroup homomorphism.

Theorem. Let V=<Q, A, B >, 'V=<'Q, 'A, 'B > be machines. If exists the injective s-homomorphism \psi: <V> --> <'V> then 'V simulates V.

References

[1] Buls, J. (1986) Ocenka dlini slova pri modelirovanii konechnix determinirovannix avtomatov. Teoreticheskie osnovi matematicheskogo obespechenija EVM, Riga: LGU im. P. Stuchki, pp.25-35 (Russian).

[2] Hartmanis J. (1961) On the State Assignment Problem for Sequential Machines I. IRE Transactions on Electronic Computers. Vol. EC-10, No.2(June), pp.157-165.

[3] Lallement G. (1979) Semigroups and Combinatorial Applications John Wlley & Sons, New York, Chichester, Brisbane, Toronto

[4] Plotkin B. I., Greenglaz I. Ja., Gvaramija A. A. (1992) Algebraic Structures in Automata and Databases Theory World Scientific, Singapore, New Jersey, London, Hong Kong.

Date received: January 29, 2003