This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
-product B\ x • • • x Bn(( ,..., 'n, X) in the following manner. For every t = , . . . , « , consider a fixed element dt of B't and define the mapping : Bt At such that
Moreover, let pt denote an ordering on X't. In addition, define (bi,... ,bn,x) = x' such that x' X't is the minimal input sign (with respect to pt) having t,2(x') = x" with ( (ri(bi),...,Tn(bn),x) =x". First we prove that B\ x • • • x Bn(( {,..., ( n, X) is a D-product. Consider t {1,...,«} and let { , t),..., (tm, t)} = E n {1,...,«} x {t}, where E denotes the set of edges of D. Then for every t {1,..., n}, (b\,..., bn) 6 B\ x • • • x Bn, x e X,
64
Chapter 2. Directed Graphs, Automata, and Automata Networks
let
For every such that. with
defined bv ive have and is the minimal input sign (with respect to pt) having This means that
Therefore, is a state-homomorphism (state-isomorphism) of a state-subautomaton of the D-product onto A. Ihe proot is complete. We have the following direct consequence of the above statement. Proposition 2.54. Consider a class K. of automata and two classes A, A of digraphs having the property that every -product of .-products of automata from 1C is also a A-product of automata from K. Suppose that an automaton A can be represented homomorphically (isomorphically) by a A-product of automata Ai,... ,An, and assume that for every t = 1,..., n, At can be represented homomorphically (isomorphically) by a Aproduct ofautomata from K. Then A can be represented homomorphically (isomorphically) by a A-product of automata from K.. Here and throughout this monograph, if we are dealing with a class K. of automata, we always assume that k is nonvoid. A class of automata is called complete with respect to homomorphic (isomorphic) simulations under the given type 0 of products if every automaton can be simulated homomorphically (isomorphically) by a product of automata inK. K is called finite if it has a finite number of elements. Furthermore, it is said that /C is minimal if for every A K, k \ A is not a complete class of automata with respect to homomorphic (isomorphic) simulations under the 0-product. The complete (finite complete, minimal complete) classes of automata with respect to homomorphic (isomorphic) simulations by nonempty words are analogously defined. The next statement is clear. Proposition 2.55. Given a digraph D, let M = A\ x • • • x An(X, i,..., < ) be a product of automata A\,..., An such that M. homomorphically (isomorphically) simulates an automaton A by some mappings : B A, 12 : Y • X*. Then there exists a D-product M' = AI x • • • x An(X', (,...,
• A, T2 : Y -» X'* having the following properties: \T2(y)\ = ^(y)!,}? e Y; moreover, for every positive integer k, I and ji, y2 € F, the kth letter ofr^yi) and the tth letter of 2) coincide only ifk = t andy\ = Y2Given a digraph D = (V,E), letDl = (V, E') be a digraph with E' = EU{(i, i) \i € V}. Similarly, if is a (nonempty) class of digraphs, then we put = {Dl \ D A). Thus, £ for every digraph D, a D -product of automata is a general product having an underlying graph Dl. Similarly, if M is a Dlproduct of automata and D A holds for a class of 9) wim (at, ytqt) = at because then At has either Letichevsky's criterion or the semi-Letichevsky criterion. The next two observations show that a statement analogous to Proposition 2.71 does not hold for the semi-Letichevsky criterion. Proposition 2.73. There exists an automaton having Letichevsky criterion such that it has a single-factor product satisfying the semi-Letichevsky criterion. Proof. Let A = ({0,1, 2}, {x0, x1, x2], 8) be defined by 5(0, xi) = i, (1, xi) = 0, 5(2, xi) = 2, i = 0, 1, 2. Let .A({x, y), p) be given with p(i, x) = x1, p(i, y) = x2, i = 0, 1, 2. Then (0, (0, x)) = 0, (0, p ( 0 , y)) = 2, 5(2, p(2, x)) = 5 ( 2 , ( 2 , y ) ) = 2, and 5(1, (1, x)) = 5(1, (l, y)) = 0. It is easy to check that A satisfies Letichevsky's criterion, but the product A({x, y}, 2, we obtain (i, z • uq,p e Bp is bijective with inverse z' *-> z' • uq,p. For sq e Hq, the map sq i->> Uq,psqUqtp € Hp is an isomorphism of groups with (z-uq,p)-uq,psquq,p = (z-Sq)'Uqtp. Hence, we have an isomorphism of permutation groups. Now for each q let uq = uq \ x • • • x T>m(X, 1 and T>i,..., T>m-\ are counters. Then a cascade product C x T>m(X, \jr\, ^2) also has a nonautonomous strongly connected subautomaton, where C is a counter Ck. (C can be a trivial counter having only one state if m = 1). Let us denote this subautomaton by D= (D, X, 8"). The automaton Dm cannot be a counter, so it is Bn for a particular n. Since D is a nonautonomous strongly connected automaton, no state in D has be fixed the symbol * as its second component. Let and with Put Thus, If = a-y. then, bv A and the definition of Bn, we have But then b\ = bi follows. Therefore, » and, consequently, one of and has the symbol * as its second component. Hence, m > 1 and there exists a k, 1 k < m, such that £>* = BI for £ particular 1. Denote again D = (D,X, 8") a nonautonomous strongly connected l.jc' € X,}, i = 1, . . . , m . Recall that for arbitrary MI, M2 6 (L*)Xi • • -X r , t = l , . . . , n , with |ui| = |M 2 | and x e Xt+i(modn), (p2(a{, ...,a'n,x) = (b, w)) = b. Indeed, let Y be an arbitrary nonempty set having at least 3\p\ + \r \ elements. Thus there are words u, v, w e Y+ with \u\ = \p\, \v\ = \v'\ = \v"\ = \pr\, \w\ = \w'\ = \w"\ = \p\ such that uvw does not contain letters in Y+ with double occurrences. Define • X such that k+i) such that : A ->• {0, l}n+1 given by 1 (i.e., \p | > 0). For technical reasons, we put a\ — a and xp = x\- --xr such that xi,...,xr € X, r > 1. Moreover, we put a (+ i = 8(a, x\ • • • jc(), 1 < i < k, and A' = { f l 1 ( . . . , 0 r } . \A\ — 1, 8(a, q) ^ 8(a, q'\ then for every pair of words r, r' e X*, \r\ = \r'\, we have 8(a, qr) ^ 8(a, q'r'). Proof. Suppose that our statement does not hold, i.e., there are a e A, q, q', r, r' e X*, \q\ = \q'\ > \A\ - 1, |r| = |r'| having 8(a, q) ^= 8(a, q') and 8(a, qr) = 8(a, q'r'). Then, of course, |r| = |r'| > 0. We distinguish the following three cases. Case 1. There are qi,n, q2,r2,q{, r[,q'2,r'2 with q = q\r\ = q2r2,q' = q{r( = q2r2, \qi\ < \q2\, \q[\ < \q'2\ such that 8(a, q{) = 8(a, 2), 8(a, q{) = 8(a, ^).20 But then, by Proposition 4.16, 8(a,q\w) = 8(a,qiw') and 8(a,q{w) = 8(a,q(w') for every w, w' eX*, |u;| = |iy'|. Thus, because of &(a,q\) = 8(a,q2) and5(a, q() = 8(a,q2), we obtain that for every w, w' € X* there are z, z' e X* with 8(a, q\wz] = 8(a, q\) and 8(a, q w'z') = 8(a, q{). Thus q\r\—q, q'^ =q' imply that 8(a, qrz} = 8(a, q\) and 8(a, q'r'z') = 8(a, q{) hold for some z, z' e X*. This means that 8(a,qrzri) = S(a,#)and 8(a, q'r'z'rQ = 8(a, q'). Putb = 8(a, qr)(= 8(a, q'r')), c = 8(a, q), c' = 8(a, q'). Then 8(b, zr1) = c c' = 8(b, z'r{) and 8(c, r) = 8(c', r') = b. Therefore, by Proposition 2.70, A satisfies Letichevsky's criterion, a contradiction. 20 A, ' : AxX -> A having the following properties. Let*', y' e X be arbitrary fixed-input letters and for every b e A, y X, let |A| — 1. Assume that 8(a, q) 8(a, q') holds for some q, q' e X*, \pq\ = \pq'\ < |A| — 1 and let q, q' be words of maximal length having this property. Then there are q = uv, q' = uv' (having \q\ = \q'\ < |A| — 1) such that we have the following properties: (1) For all prefixes r ofv andr' ofv' with \r\ = \r'\ > 0, we have 8(a, ur) ^ 8(a, Mr'). (2) For all prefixes wx of v and w'x' of v' with ww' ^ X and x,x' € X, 8(a, uw) = 8(a, MW/) implies x = x'. (3) For all distinct prefixes p\, P2 of pq, 8(a0, p\) 8(ao, P2)(4) For all words r, r' with \r\ = |r'| > \q\(= \q'\), 8(a, r) = 8(a, r'). Proof. Consider a e A and suppose that our conditions hold. Suppose that for every prefix u of q and u' of q', 8 (a, u) = 8(a, «')impliesw = u' = A.. Obviously then (1) and (2) hold.
2.4. Automata Networks and Products of Automata digraphs, then M is also said to be -product. In this sense we will speak about product, -product, product, etc. The following statement is obvious.
65 -
Proposition 2.56. Given a digraph D, an automaton is a Dl -product of automata At, t = 1,..., n, if and only if it is a TJ-product of products At(Xt,
66
Chapter 2. Directed Graphs, Automata, and Automata Networks Next we prove the following.
Proposition 2.66. Let be a product of automata having an underlying graph = ({1, ...,»},£), vertices with such that ( suppose that for any pair implies Then there exists a product having the underlying graph with nodes and edges such that for any
whenever
Proof. By the condition on edges, components. MX any arbitrary functions:
do not depend on their (i + l)th,..., nth-state We construct the following feedback
where It is easy to check that the product A' having the above feedback function components satisfies the required conditions. Corollary 2.67. Every cascade of automata can be isomorphically represented by a cascade of (copies of the same) automata such that for each i, at most one feedback function
2.4. Automata Networks and Products of Automata
67
Theorem 2.68 (Gluskov decomposition theorem). A class 1C of automata is complete with respect to isomorphic representations under the general product if and only if there exists an automaton A = (A,X,8) in K. which has input letters x\, X2, x^, X4 € X and distinct states ao,a A such that <S(0o>*i) = oo ( ,X2) = a,8(a,X3) = a, and 8(a,X4) = hold.
GLU§KOV CRITERION be a product Proof. For the proof of necessity, let such that a subautomaton of B has an isoof automata ana inmorphism onto A. For appropriate states put letters let Let with Because of there exists and . Thus t has the Then conditions 01 necessity. can be represented Conversely, prove that an arbitrary automaton isomorohicalry bv a power or A. Using the transitive property of isomorphic representation, without loss of generality Define the functions we mav assume that such that for every whenever implies Clearly, then the power isomorphically represents M, where the appropriate isomorphism is having and The proof is complete. Note that in the proof of sufficiency of the above theorem, the automaton M. can also be represented by a power of A having k > Iog2 n factors. (We leave to the reader the proof of this statement.) For homomorphic representations by automata networks, the minimal computational elements required to achieve an arbitrary finite state computation are characterized in the Letichevsky decomposition theorem by a simple criterion. Necessity of the criterion will be shown in Proposition 2.71. Although giving a proof of sufficiency is not difficult, we delay this until the end of Chapter 5. There two proofs of sufficiency are derived from much stronger independently proved results (e.g., Theorem 5.26). Theorem 2.69 (Letichevsky decomposition theorem). A class K, of automata is complete with respect to homomorphic representations under the general product if and only if there
68
Chapter 2. Directed Graphs, Automata, and Automata Networks
exists an automaton A= (A, X, 8) which has a state a € A, two input letters x,y and two input words p, q € X , under which
X,
It is said that an automaton A satisfies Letichevsky's criterion if it has the above property (*). If A = (A, X, 8) does not satisfy Letichevsky's criterion but we have
LETICHEVSKY CRITERION 8(ao, x) 5(0o. y), and (« *P) = « f o r some o G A, jc, y X, and /? X*, then A satisfies the semi-Letichevsky criterion. Otherwise we say that A does not satisfy any Letichevsky criteria or is without Letichevsky criteria. Proposition 2.70. Let there be given an automaton A = (A, X, 5), a state O A, four input words u, v, p,q € X* with \p\ = \q\ under which (ao, u) ^ 8( ao, v), and8(ao, up) = 8(ao, vq) = a$. Then A satisfies Letichevsky's criterion. Proof. We shall use the following simple fact. Assume that there are w\, W2, w(, w'2 e X*, x,y e X w\xw2, w(yw'2 € {up, vq} such that 8(ao, w\) = 8(ao, w(), 8(ao, w\x) ^ 8(ao, w(y). Then we obtain Letichevsky's criterion by setting ao, u, v, p, q to 8(ao, w\)(= 8(ao, w()), x, y, W2U)\, w2wi, respectively. Therefore, it remains to study the case when for every w\, W2, w{, w'2 e X*, x, y e X with w\xw2, w[yw'2 € {up, vq} and5(oo, ^i) = 8(ao, w'i), it holds that 8(ao, w\x) = 8(ao, w(y}. In this case, there are x\,.. .xn € X having u = xi • • • x,,, p = xi+i •••XH(XI--- xny, v = xi • • • x},, q = xj+i • • • xn(xi • • • xn)1 for appropriate s, t 0. But (ao, ) (a ,v) implies i j. Hence \p\ ^ \q\, a contradiction. D If a class 1C of automata contains an automaton satisfying Letichevsky's criterion, then we also say that /C satisfies Letichevsky's criterion. Otherwise, we say that /C does not satisfy it. If K does not satisfy Letichevsky's criterion but there exists A fC such that A satisfies the semi-Letichevsky criterion, then it is also said that 1C satisfies the semiLetichevsky criterion. Otherwise, we also say that 1C does not satisfy Letichevsky criteria or 15 without any Letichevsky criteria. As already mentioned, necessity of the Letichevsky criterion in proving the Letichevsky decomposition theorem follows by the next statement. Proposition 2.71. Suppose that a product of automata satisfies Letichevsky's criterion. Then it has a factor with this property.
2.4. Automata Networks and Products of Automata
69
SEMI-LETICHEVSKY CRITERION
WITHOUT LETICHEVSKY CRITERIA Proof. Let
) be a product of automata Suppose that A satisfies Letichevsky's criterion. Then there are a state such that , input letters input words and,
simultaneously,
. But then there are
and simultaneously,
with
such that and, But then At has Letichevsky s criterion.
70
Chapter 2. Directed Graphs, Automata, and Automata Networks
Proposition 2.72. Suppose that a product of automata satisfies the semi-Letichevsky criterion. Then it has either a factor with Letichevsky's criterion or a factor with the semiLetichevsky criterion. Proof. Let A = A1 x • • • xAn(X, ,..., (pn) be a product of automata At — (At, Xt, t), t = 1 , . . . , n . Suppose that A satisfies the semi-Letichevsky criterion. Then there are a state ( a 1 , . . . , an e A1 x • • • x An, input letters x, y e X, input words p, q e X* such that ( 1 (a 1 , 1 (a 1 , ...,a n ,*)),... , n(an, p n (a 1 , ...,an, x ) ) ) ( a 1 , (a 1 , ...,an,y)),..., (an, n ( a 1 , . . . , a n , y ) ) ) , and, simultaneously, ( 1 (a 1 , 1 (a 1 ,..., an, xp)) ,..., n(an, n ( a 1 , . . . ,an, xp))) = ( a 1 , . . . , an). But then there are t e {1,...,n}, x t =
2.5. Bibliographical Remarks
71
criterions or the semi-Letichevsky criterion, which is a contradiction. Therefore, the considered product is without Letichevsky criteria. Proposition 2.76. Let A be an arbitrary noncommutative strongly connected automaton. Suppose that an automaton B homomorphically simulates A. Then B satisfies Letichevsky's criterion. Proof. Consider a noncommutative strongly connected automaton A = (A, X, ). Suppose that A can be simulated homomorphically by an automaton B = (B, , SB) under T\ : B' A, TI : X XB*. Suppose that B' is minimal such that it has no proper subset B" for which B homomorphically simulates A under some ( : B" A, : X ->• XB*. Then, by the strong connectivity of A, for every b\, bi B' there exist x\,... ,Xk € X with . In addition, because 01 the noncommutativity 01 A, there are a state and input words having Consider the natural extension with Then tor every In addition, by the minimality or B , there exist words with On the other hand. implies that Indeed leads esultmg in a contradiction. Therefore, there are such that and, moreover, Let and Obviously, then The proof is complete.
2.5
Bibliographical Remarks
Section 2.1. Extensive treatment of graph theory is given by F. Harary [1969]. Theorem 2.1 is from K. Kuratowski [1930]. A nice presentation of this result was developed by G. A. Dirac and S. Schuster [1954], Theorem 2.2 was found by G. Chartrand and F. Harary [1967]. Lemmas 2.6,2.7,2.8,2.9, and 2.10, Theorem 2.11, Proposition 2.13, and Theorems 2.15 and 2.16 can be found in Ananichev, Domosi, and Nehaniv [in press]. Lemmas 2.8 and 2.9 can also be derived from Z. Esik [1989b]. The concept of digraph completeness is from Z. Esik [1991a]. Corollaries 2.19 and 2.20 are in Esik [1991a]. The other parts of this section are essentially new. Section 2.2. Many books have given accounts of various aspects of the algebraic theory of automata—for example, Bavel [1983], Eilenberg [1974], Gecseg and Peak [1972], Gecseg [1986], Ginzburg [1968], Hartmanis and Steams [1966], Holcombe [1982], Nelson [1968], Salomaa [1969], and Simon [1999]. The concept of automaton mapping is given and intensively studied in Raney [ 195 8] and Horejs [ 1963]. The generating systems of semigroups and groups of automaton mappings are intensively studied in Csakany and Gecseg [1965], Gecseg [1965], and Zarovnyi [1965]. Theorem 2.30 is due to S. V. Alesin [1970a] and P. Domosi [1972]. (In the present book a new and simpler proof of this statement has been produced.) S. V. Alesin [1970b] stated that the answer to Problem 2.31 is in the affirmative. But, unfortunately, there is a gap in the proof of his Lemma 3, and so the validity of
72
Chapter 2. Directed Graphs, Automata, and Automata Networks
his results may be questionable. (See also Csakany, Mathematical Reviews 45 1687.) The other results are new but elementary. Section2.3. Proposition 2.34 issued from Eilenberg[l 974]. Proposition 2.47 is new. Proposition 2.49 was proved by Z. Esik [199la]. All the other statements are folklore. Section 2.4. Investigation of finite automata networks goes back to W. S. McCulloch and W. Pitts [1943], J. von Neumann [1966], E. F. Codd [1968], M. Minsky and S. Papert [1969], A. W. Burks [1970], and C. Choffrut [1986]. An extensive algebraic treatment of automata networks was given by M. Tchuente [1979,1982,1983,1985,1986] and by F. Fogelman-Soulie, Y. Robert, and M. Tchuente [1987]. Structural and behavioral equivalence relations in automata networks were studied by T. Saito and H. Nishio [1989]. A verification tool for distributed systems using reduction of finite automata networks was described by E. Madelaine and D. Vergamini [1989]. Finite (and infinite) automata systems as parallel communicating finite (and infinite) automata networks were intensively investigated by Z. Fiilop [1991], C. Martin-Vide and Gh. PSun [1999], C. Martin-Vide and V. Mitrana [2000, 2001], C. Martin-Vide, A. Mateescu, and V. Mitrana [2002], and I. Babcs&ryi and A. Nagy [2004]. Product and completeness of automata were intensively investigated by F. Gecseg and I. Pea* [1972], S. Eilenberg [1974,1976], J. Dassow [1981], and F. Gecseg [1986]. The concept of the Gluskov-type product is introduced by V. M. Gluskov [1961]. Several specialized types of the Glu§kov-type product were defined. The concepts of Dproduct and A-product were proposed by Z. Esik [1991b]. The quasi-direct product was given by F. Gecseg and I. Peak [1972]. The cascade product is from M. Yoeli [1961]. The loop product was defined by Z. Esik [1987a]. The family of a,-products was introduced and intensively studied by F. Gecseg [1974,1976a, 1986]. The family of v,-products is due to P. Domosi and B. Imreh [1989]. The family of a,-v,-products was given by F. G6cseg and H. Jiirgensen [1991]. Products of automata with identity are from Z. Esik and J. Viragh [1986]. Theorem 2.68 was proved by V. M. GluSkov [1961]. Theorem 2.69 can be found in Letichevsky [1961]. The proof of Proposition 2.76 is new.
Chapter 3
Krohn-RhodesTheory and Complete Classes
While the fundamental information concerning complete classes with respect to homomorphic representations under the general (Gluskov-type) product is concentrated in the celebrated classical criterion of A. A. Letichevsky, the well-known Krohn-Rhodes decomposition theorem is the basis for studying the cascade product of automata. The cascade product of automata is a general model of automata networks without feedback, and the theorem describes how to synthesize any finite state automaton using such a cascade, and, moreover, it describes the necessary irreducible components in detail. We shall derive the Krohn-Rhodes decomposition theorem from a sophisticated result called the holonomy decomposition theorem, which generally yields much more efficient decompositions than in the original proofs of the former. Characterization ofhomomorphic representation is important since one of the major tools for representations is homomorphism. While it is not too general, it is powerful enough. We study homomorphic representation in networks of automata with no feedback (cascade and quasi-direct products) and with low bounds on feedback length (a -products for i 2) here.
3.1
Krohn-Rhodes and Holonomy Decomposition Theorems
Theorem 3.1 (Krohn-Rhodes decomposition theorem). Given a finite automaton A, let F be the flip-flop monoid (the smallest monoid with two right-zero elements); moreover, let GI, ... ,Gn denote all simple groups that divide the characteristic semigroup S(A). Then A can be represented homomorphically by a cascade product of components from {Af, Ad, • • •, Acn }• Moreover, if A is a nontrivial permutation automaton, then the factor AF may be excluded. Conversely, let i be a cascade product of automata which homomorphically represents the automaton A. If a subsemigroup S of the flip-flop monoid or a simple group S is a homomorphic image of a subsemigroup of S(A), then S is a homomorphic image of a subsemigroup of S(Bt) for some component automaton Bt (t € {1,..., n}). In addition, a subsemigroup S of'the monoid¥with two right-zero elements 73
74
Chapter 3. Krohn-Rhodes Theory and Complete Classes
can be embedded isomorphically into a finite semigroup T whenever T has a subsemigroup that can be mapped homomorphically onto S. Irreducibility. A finite semigroup S is irreducible if whenever S divides a wreath product of finite transformation semigroups (x2, s2) (X\, S\), then S divides s2 or S divides S\. Equivalently, if 5 divides the cascade product of finite automata A and B, then either S < A or S < B. Or again, equivalently, "S is irreducible" means that if S divides the -product of finite automata, then it divides one of the factors. For any finite automaton A, let PRIMES(A) denote the set of simple groups that divide S(A). This notation also applies to transformation semigroups viewed as automata. We will derive Theorem 3.1 from the following, for whose proof we shall rely on the holonomy decomposition theorem and a series of lemmas. Theorem 3.2. (Krohn-Rhodes prime decomposition theorem for transformation semigroups). Let (A, S) be a finite transformation semigroup. Then (A, S) divides a wreath product of transformation monoids (M,-, M/) such that each M, 6 PRIMES(S) or M{ is the flip-flop monoid. In the case that (A, S) is a permutation group, then the flip-flop monoid is not required and the division can be chosen to be an embedding. Conversely, for every wreath product of finite transformation semigroups (Bi, si,) which (A, S) divides, we have that G PRIMES(S) implies that G divides si, for some i. Moreover, if M is any divisor of the flip-flop monoid which divides S, then M embeds into some 5,. The subsemigroups of flip-flop monoid F are the monoid F with two-right-zero elements itself, the two-element monoid with zero elements, the semigroup with two right-zero elements, and the trivial monoid. It is clear that any divisor of F is actually isomorphic to one of these. Thus the second part of this theorem characterizes the irreducible finite semigroups as the finite simple groups and the subsemigroups of the flip-flop monoid. We will say that the class JC of automata satisfies Krohn and Rhodes' criterion if for every finite simple group S there is an automaton A tC having that 5 is a homomorphic image of a subsemigroup of S(A), and, moreover, following the last part of the KrohnRhodes decomposition theorem, a class K, satisfying the Krohn-Rhodes criterion, must contain an automaton A such that a subsemigroup of S(A) is isomorphic to the monoid F with two right-zero elements. These two forms of the Krohn-Rhodes theorem yield an immediate corollary. Corollary 3.3. A finite transformation semigroup (resp., finite automaton) divides the wreath product (resp., cascade product) of flip-flops if and only if it has no nontrivial group divisors, or, equivalently, if and only if it has no simple group divisors. Such transformation semigroups (resp., automata) all of whose group divisors are trivial are called aperiodic, and the result shows that they can be represented homomorphically by cascades of flip-flops (resp., divide a wreath product of flip-flops). We begin with last part of Theorem 3.2.
3.1. Krohn-Rhodes and Holonomy Decomposition Theorems
75
Lemma 3.4. If S is a subsemigroup of the flip-flop monoid F and S divides a finite semigroup T, then S is isomorphic to a subsemigroup ofT. Proof.
with identity e and xy = y for any We have Take such that maps them to e, I, and r, respectively. By replacing e by its unique idempotent power and r and by the unique idempotent powers of ere and ete, we may assume that ere = r and ele = 1. Let f = (lr)m be the unique idempotent power of Let be the unique idempotent power of fl. Then and and
Clearly ana and g are distinct. Thus {e, /, g} makes up a subsemigroup of T isomorphic to F. Simplifications of this proof establish the result for the other subsemigroups of F. Next we do some work toward establishing which semigroups are irreducible. Lemma 3.5. The flip-flop monoid F and all its subsemigroups are irreducible. Proof. Suppose F divides a wreath product of transformation semigroups (X x Y, W) = (X, S) z (Y, T); then by the above lemma F W. Let (E, e) be the identity and (L, 1} and (R, r) be the two right-zeros in the embedded copy of the flip-flop. Case 1. r t. Since (R, r)(L,£) = (L, ), we have rt = l and, similarly, re = r, whence t cannot equal e. Similarly one shows r cannot equal e. Thus e, r, l T are pairwise distinct, so the projection from W to T is injective on the embedded copy of F. Thus F embeds in T. Case 2. r = t. We examine the right coordinates of the embedded flip-flop monoid. We have E,R,L : Y S. Since (L, l) and (R, r) = (R, t) are right-zeros in the embedded copy, for all y e Y, L(y)L(y • I) = L(y), R(y)R(y • t) = R(y), L(y)R(y • I) = R(y), R(y)L(y • t) = L(y). Similarly, since (E, e) is the identity in this copy of F, also E(y)F(y • e) = F(y) and F(y)E(y • e) = F(y) for each F e {E, L, R}, y € Y. Since r = t, R cannot equal L, so there exists a yo e Y with R(yo) =£ L(yo). We have R(yo)R(yo ' I) = R(yo) and R(y0)L(yQ • t) = L(JO), whence R(y0 - £) ^ L(y0 • t). Let yi = yo -1. Since te = t — et, we have y\ • e = y\ = y\ • t. Thus, the above equations applied to y = yi show that (L(yi), R(yi), £(ji)} has the multiplication table of F. We already know that L(yO /= R(yi), so L(yi)E(yi) = L(yi) andL(yi)R(yi) — R(y\) imply E(yi) ^ R(y\). Similarly E(y\) ^ L(y\). Thus we have an embedded copy of F in S. The proofs of irreducibility of other subsemigroups of F are simplifications of this one. Lemma 3.6. A nontrivial finite group is irreducible if and only if it is a simple group. Proof. Let G be a nontrivial finite group. If a group G is not simple, then it has a proper normal subgroup N, so by Lemma 1.16 G is not irreducible. Conversely, if G is a simple group and G divides (X, 5) = (^2, 52) 2 ( X i , Si) for some finite transformation semigroups (Xi, Si) (i = 1, 2), then by Proposition 1.11 there exists a permutation group (Z, G) with Z c Xi x X\ and subgroup G of S mapping homomorphically onto G.
76
Chapters. Krohn-Rhodes Theory and Complete Classes
Consider the projection homomorphism TT\ from S to S\ restricted to G. Let N = ker n\. Let lg = (i,e) denote the identity of G. Clearly, e2 = e Si. Define a homomorphism : ker i -+ ' = x ••• x (\ \ times) by \jr(h, e ) f a ) = hfa • e) for all xi e XL (This defines each jci-coordinate of the |Xi (-tuple.) Of course ty(h, e) can be considered a function from X\ to Si. Now, given (h, e), (hf, e) e N = ker n\, if \j/(h, e) = i/r(h', e), then for all fa,x\) e X2 x X\ we have (xi,x\) • (h, e) = (x2,x\) • (i,e)(h,e) = (x2 • ifa)hfa • e),xi • e) = fa • ifa)h'fa • e),x\ • e) = fa,x\) • (i,e)(h',e) = (x2,x\) • (h',e), whence (h,e) = (h',e), and so ^ is injective. We also have, for each *i € Xi, ir((h,e)(h',e))fa) = hfa • e)h'fa • e • e) = hfa • e)h'fa • e) = (ty(h, e)(xi))(ifr(h', e ) f a ) ) . Thus iff is an injective homomorphism on N. Thus G/N is isomorphic to the subgroup n\ (G) of Si and N is isomorphic to the subgroup ty (N) of S*1. Therefore every Jordan-Holder factor of G occurs as a Jordan-Holder factor of G/N or of N, then hence divides G/N or N, and hence divides S\ or S*1. But since = G 1 is simple, G is a Jordan-Holder factor of G. This proves G divides S* or Si. In the latter case, we are done. In the former case, G divides S = S2 x • • • x S2. Take H a subgroup of the direct product mapping onto G, say, r] : H G, and let HI denote the subsemigroup of S2 consisting of those elements s, of S2 such that s, occurs as the ith component of some element of H. Consider the homomorphisms pt : H, G given by Pi(si) = r / ( l , . . . , 1, Sj, 1,..., 1), si HJ-, 1 in each coordinate j i denotes the idempotent of S2 occurring in that position in the identity element of the group H. Let k = \Xi\. Then TJ(SI, ..., sjO = PI(SI) • • • Pk(sk) for all (s\,..., Sk) € H, and since the Pi(Si)Pj(sj) = Pj(sj)pi(si) (si € Hi,Sj e Hj) always holds for / / j, it follows that 77(51,..., s k ) p i ( s f ) r i ( s \ , . . . , sk)~l = Pi(si)pi(s-)pi(si)-1 e pi(H{). Thus each /?,(#/) is a normal subgroup of G. Since G is not trivial and n is surjective, these subgroups cannot all be trivial. Therefore by simplicity of G there is an / such that pi(Hj) = G, whence G divides S2. This proves that G is irreducible. Lemma 3.7. If (X, G) is a permutation-reset transformation semigroup, then (X, G) <(X,{U})KG,G). Proof. Recall that (X, {I*}) has a semigroup consisting of the identity permutation 1* and all constant maps cx : X • X, with cx(x'} = x for all x' e X. Define TJS : X x G -» X by (x, g) t-+ x • g. For g e G c G, define g by fa, gi) • g = fa • lx, gi • g) = fa, gig)- For cx € G, define cx by fa, gi) • cx = fa • cx.g-i,gi • 1) = (x • gf 1 , gi). Then ^((*i, gi) • I) = x\ • gig = Vfa, gi) • g, and ^(fa, gi) • cx) = ir(x • gf 1 , gO = x ' g^gi = x = i/ffa, gi) • cx. This proves the lemma. D Lemma 3.8. If (X, { l x } ) is a finite transformation semigroup with transformations consisting of the identity transformation and all constant maps on X, then (X, {lx}) embeds into the direct product of copies of the flip-flop. Proof. Let A = {0,1}; then the flip-flop is (A, {1A}). Let n be such that 2n > |X|. Let / : X -» A" be any injective function. Let // : X ->• A be the /th component of /. Let x' € X and s € {lx}- Then s = cx for some x e X, or s = \x- Let ^(cx) = (c/^),..., c/n(X)) and ^(Ix) = (!A» • • • > IA)- Then ty is an injective homomorphism.
3.1. Krohn-Rhodes and Holonomy Decomposition Theorems We have
77
On the other hand, This establishes the
embedding. Holonomy. We introduce the holonomy groups and related notions. First, fix a finite transformation semigroup (A, 5). The holonomy decomposition theorem (Theorem 3.9), from which we shall derive the Krohn-Rhodes prime decomposition theorem, is proved by a detailed study of how 5 acts on subsets of A. Recall that if q A and s € S, then
In this section, we write A, for the identity Let acts on Q as just described. transformation on A. Then clearlv We have a reflexive and transitive relation on Q given by there exists Consequently, we have an equivalence relation on Q,
and Observe that choose a unique representative For each equivalence class in then tor appropriate always holds, since whence and implying we have Thus, the set of representatives of the Bv svmmetrv. it follows that but not if is partially ordered by We also write equivalence classes and We say p is a tile of q and write Thus, is The set of tiles of q for any for all i implies equals Since Q contains the singletons, for denoted by the union of its tiles, Define Hq to be the set of permutations of Bq induced by elements of s Sx. That is, if for s € S\ the function sq : Q Q defined by sq(z) = z • s = {a • s \ a € z] (z € Q) restricts to sq : Bq Bq and permutes the elements of Bq, then sq Hq. Hq is called the holonomy group ofq in (A, 5), and clearly Hq divides S,16 and (Bq, Hq)isa permutation group called the holonomy permutation group of q. then we can wnte and Suppose and Since q is finite, then we claim for some Let This shows that s permutes implies Suppose Let ; we have and so the elements with be such that is the identity permutation on q, and let Let , we have Then Since 16 In the exceptional case Hq = [ q], we have that division of 5 is guaranteed since 5 contains an idempotent. In all other cases, the identity transformation on Bq is, of course, represented by the idempotent power of any nontrivial sq Hq,so that Hq is a quotient of the subsemigroup of 5 consisting of those elements s for which sq permutes Bq.
78
Chapter 3. Krohn-Rhodes Theory and Complete Classes
and. since z is a tile of a. it follows that We have or This proves if z is a tile of a, then z • s is also whence a tile of q. Moreover, if and , then Since Bq is finite, this proves s permutes the elements of Bq. Thus sq Hq as claimed. Furthermore, q = p implies that, say, (Bq, Hq) is isomorphic to (Bp, Hp). We saw s = uq>pvq>p permutes the elements of q and, similarly, vqtpuqtp permutes those of p. Take n > 1 such that (uq,pvqtp)n is the identity permutation of q. Letuq,p = vq,p(uq,pvq 1 and p p'. s, then actually p' is equivalent to p: ifh(p) = i, we have qo < •• • < qi = p < p', and so by h(p') = i the last inequality cannot be strict, i.e., p = p'. Clearly, for each i with 0 / h, Q contains at least one element having height i. For each i (1 < i < h), define (#,-, %•) to be the direct product of the holonomy permutation groups of the height i representatives in Q. Then #, = fl/tcp)^ Bj an^ Hi = Y[h(j)=i HP- Then (#/»%•) is a permutation group and (#,, 'H,) is the associated holonomy permutation-reset transformation semigroup obtained by adjoining all constant maps taking values in #,. Denote elements of #, by boldface variables b or b/. and so
Notation. Suppose that b is a tile of some p Q with height i and the p represents its equivalence class. That is, b - p and p = JJ. Then we denote by [b]p any arbitrary element of fy containing tile b in the p-position. Also, if g € Hp, then we write [g]p for any arbitrary element of , containing g in the ^-position and identity elements in all other positions. Observe that BH = BA and / Hh = HA since A is the only set of height h. Thus b/, = [bh]A =J h for all tiles bh of A and [g]A = g for all permutations g in the holonomy group of A = A. Theorem 3.9 (holonomy decomposition theorem). Let (A, S) be a finite transformation semigroup; then (A, 5) divides a wreath product of its holonomy permutation-reset transformation semigroups (B\, Hi)l"'l (Bh, 'Hh)-
3.1. Krohn-Rhodes and Holonomy Decomposition Theorems Proof. Let * be a new symbol and define goes from h to 1 by and, letting
79 inductively as i
, which we suppose has already been well defined for we define
(It is understood that the last case will apply also if /? = *.) Observe that in the second case is the representative of the equivalence class of p, and so and in fact Observe that if .Thus is not then is eithe or a singleton. If then can have no effect on the value of in the above definition. If h(p) = i, then only the -position of b, may affect the value of ni. In all cases at most one position of b, can affect the value of n(. Let * be the set of (bi,..., b/J such that ni(bi,..., b/,) is a singleton. The 17,-'s will give our covering map n by "successive approximation." Indeed, an easy induction establishes that for every Let be the unique element of the singleton be given by letting We show that
is a surjective function: given an arbitrary a € A, we choose Now assuming containing a. Then a and are defined and we proceed with by induction for and let
In the case h(p) < i, existence of elements of height i in Q guarantees that an arbitrary fixed b* exists. In the case h(p) = i, since i > 0 the fact that p is the union of its tiles guarantees the existence of a tile b' of p containing a, so b may be taken to be b' • up. It is clear that a e ni, (b,,..., b/,) and h(^ (b,,..., b/,)) < i since either (1) h(p) < i, and so ?/,-(b,-,..., b/,) = p which contains a, or (2) h(p) = i, and then /7,(bi»..., b/,) is a tile b • up of p containing a. It follows by induction that a e f ? i ( b i , . . . , b/,) and h(rii(bi,..., b/,)) < 1, whence »/i(bi,..., b/,) is the singleton {a}. This proves that r\ is surjective. We shall use Proposition 1.10 to establish the division. In the terminology of Proposition 1.10, surjectivity of r\ gives an element ( b i , . . . , b/,) e as a lift of state a. Recall that an element of the wreath product is given by describing its component actions. (See the discussion following the definition of wreath product in Section 1.3.) Thus to specify lift of an s € 5 to the wreath product we need to give appropriate functions fori For is mst an element of Such an h -tuple of functions determines a transformation in the wreath product.
80
Chapter 3. Krohn-Rhodes Theory and Complete Classes
We define a lift for a member s of S to the wreath product by defining i = h,... ,1 inductively, First,
for
We record that which has height less than the observation that Fixing for tor the moment, write Then, wnting p for ana for define inductively as i goes down from h — 1 to 1, by
This is just
for
Of course h(p) and h(q) are necessarily less than / + 1. It is understood that the third case applies also if p = *. In the first case, constant [b • uq]~ is a constant map taking a value in Bi whose g-position is a particular tile of q. Clearly this constant map lies in Hi. In the second case, we have h(D\ = i = h(a} = h(n • s} > 1. whence a = D • s == ». Therefore This implies that represents an element of so that In all cases. as required. Now we are ready to establish the division. Fixing we again write and suppose by induction for that for as defined above we have
We have already observed that this holds with / + 1 = h, and now assuming inductively that it holds for i + 1, we establish it for i (i > 0). We must show that holds. Now we shall consider four cases. Case 1. and contradicting Now
We have
-lest imply since by definition of n/ since
since where
Therefore,
according to the definition
3.1. Krohn-Rhodes and Holonomy Decomposition Theorems
81
Case 2. Now definition of ni, since h(p) = i. And since h(q} = i, by definition of ni, we have
by
by definition of
where
So Case 3. s maps Bp bijectively onto Bq. Again
We have
since
since Therefore Case 4.
This implies that and and by definition of
acts as the identity on Bq.
and i Then by definition, so the conclusion holds by induction hypothesis.
and
for all By induction we conclude that all In particular, it follows from and all that the height of the latter is less than i and from the case i = 1 holds for all that lies in and that and Moreover, lifts of distinct members of A are distinct since n] is a function, and lifts of distinct members of 5 are distinct. If s\ 82 (s\, S2 € 5), then there is an a € A such that a • s\ a - S2. Taking a lift a of a we have n(a • J/) = (0) • s,• = a • s,, but these are distinct for i = 1,2, and therefore the lifts s{ and are also distinct. By Proposition 1.10, this establishes the division and proves the holonomy theorem.
We now derive the Krohn-Rhodes theorem as a consequence of the holonomy theorem. Using the lemmas above, the following theorem implies the Krohn-Rhodes decomposition theorem for transformation semigroups. Theorem 3.10. A finite semigroup is irreducible if and only if it is a nontrivial simple group or a subsemigroup of the flip-flop monoid. Proof. By Lemmas 3.5 and 3.6, the nontrivial simple groups and subsemigroups of the flip-flop monoid are irreducible. Let 5 be any irreducible finite semigroup; ( , 5) divides a wreath product of permutation-reset transformation semigroups of the form ( ,, ) by the holonomy theorem. Since 5 is irreducible it divides one of the HI. Now (#,, Hi) < ( , { ,}) l (Hi, HI) by Lemma 3.7. So either S divides {IgJ and by Lemma 3.8 embeds
82
Chapter 3. Krohn-Rhodes Theory and Complete Classes
in the flip-flop monoid, or 5 divides the group %,. In the latter case S is a group and, by Lemma 3.6, S is a simple group or the trivial group. This completes the proof. From the holonomy decomposition theorem, the Jordan-Holder coordinate theorem for finite groups, the preceding lemmas, and Fact 1.15, we obtain the Krohn-Rhodes prime decomposition theorem for transformation semigroups. The corresponding result (Theorem 3.1) for a finite automaton A = (A,X,8) follows by taking the transformation semigroup (A, S(A)) and using the result for transformation semigroups.
3.2
Some Results Related to the Krohn-Rhodes Decomposition Theorem
In this section we characterize the complete classes of finite automata with respect to the homomorphic representation under the or, products for i = 0, 1,2. First we show an application of the Krohn-Rhodes theory. Theorem 3.11. Let then either
be an oiQ-product. IfG is a simple group with
Proof. First, we note that if we restrict ourselves to a noncyclic simple group G, then our statement is a direct consequence of the Krohn-Rhodes theorem and Proposition 2.49. We consider a direct proof of our statement which does not use this direct consequence. Let , and . Obviously, the man with and is a well-defined semigroup homomorphism. For each be the collection of those transformations 8 with If Sb is nonempty, then it is a subsemigroup of S(A) and the mapping with is a homomorphism. Since there is a subgroup H of S(A) such that G is a homomorphic image of H and Since H is a subgroup of SL4), by Proposition 2.36, there is a nonempty set with the following properties: (a) The restriction of each is a permutation of W. (b) The mapping with . is an isomorphism of H onto a permutation group over W. if and only if Thus for we have for all Let B\ be the set of the first components of the elements of define W. For each to be the permutation of B\ obtained by taking Then the restriction of with is a well-defined homomorphism of H onto a permutation group over B\. Set N = ker , so that N is a normal subgroup of H and HIN = P. Let be the homomorphism taking Clearly, is a subgroup of S(B). We can consider as a homomorphism of H onto . If tor some i then also Therefore ker Moreover, factors through . it follows that H /N is a homomorphic image 0f H\. From we also have Since
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
83
the simple group G is a homomorphic image of H and N is a normal subgroup of H, either G is a homomorphic image of H/N or N maps homomorphically onto G. In the former case G is a homomorphic image of HI and therefore G||(n)H. From now on we assume that G is a homomorphic image of N. Let b e B\ be any fixed state. If N for a word p X+, then 8i(b,
84
Chapter 3. Krohn-Rhodes Theory and Complete Classes
Proof. Let be an arbitrary reset automaton with state set Consider the nth direct power of the two state reset automaton for which Let be mappings such that for every and furthermore, if and only if Clearly then A can be under embedded isomorpmcally into Take two alphabets X and Y. For a fixed positive integer n, consider a mapping Moreover, be the automaton, where and, for arbitrary and
Lemma 3.15. For every can be represented homomorphically by a cascade product of an n-state counter and two-state reset automata. Proof. Of course, a direct product of automata can be considered as a special type of their cascade product. Therefore, using Proposition 3.14, every reset automaton can be represented homomorphically by a cascade product of two-state reset automata. To prove our lemma, therefore, it is enough to show that can be represented homomorphically by a cascade oroduct of an n-state counter and certain reset automata. be a counter. Moreover, take the automata Let and where * is an arbitrary symbol with moreover, for arbitrary and
Clearly, all the
are reset automata. Take the cascade product
with
where
and
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
85
Now we define a subautomaton with X' = X of B and that of a mapping under which R.r is a homomorphic image of B'. Let B' consist of all b 6 B for which there are words and with such that
Moreover, let where denotes the mirror image of p. It is routine work to show that Bf is a subautomaton of B, and is a homomorDhism or onto We will also use the following lemma. Lemma 3.16. Let be automata. Assume that for and an integer there exist mappings and such that the following two conditions are satisfied: for arbitrary b
B and
Then a cascade product o RT by B homomorphically represents A. where, for arbitrary
Proof. Form the cascade product
and To an arbitrary state d = ((D. va). b) of P we correspond the state then of A. Assume that D receives an input signal x in this state d. If to which the state of A is corresponded. In the opposite state, i.e., if then The state of A corresponding to this which is for arbitrary is equal to since, b € A. (Observe that in the second case a = X.) In both cases we have that the mapping given by is a homomorphism of D into A. By (2), y is a mapping onto A. We are ready to give a proof of the next statement. Theorem 3.17. A class JC of automata is complete with respect to homomorphic representations under the cascade product if and only if (1) the two-state reset automaton can be represented homomorphically by a cascade product of automata from K, (2) every counter (of prime power length) can be represented homomorphically by a cascade product of automata from /C,
86
Chapter 3. Krohn-Rhodes Theory and Complete Classes
(3a) there is an automaton A K such that a subsemigroup S ofS(A) is isomorphic to the monoid with two right-zero elements, and (3b) for every simple group G there is an automaton with Proof. The first two conditions are obviously necessary.17 The necessity of (3a) and (3b) comes directly from the Krohn-Rhodes decomposition theorem. (Actually, (3a) and (3b) constitute Krohn-Rhodes' criterion.) For the converse, first note that every counter can be represented homomorphically by a cascade product of counters with prime power length. (We omit the easy proof of this statement.) Thus we may assume by the conditions (1), (2), and Lemma 3.15 that for every r : [p• e X+ : \p\ — n} -+ [p Y+ : \p\ = n}, the automaton RT can be represented homomorphically by a cascade product of automata from K,. Let 5 be an arbitrary noncyclic, irreducible monoid. By our conditions (3a), (3b), and Proposition 2.49 we have that S\ \A for some A K. Using Proposition 2.47, we then get As\\B^n, where HAn denotes the nth diagonal power of an appropriate subautomaton B = (B, Y, SB) of the automaton A satisfying the conditions of Proposition 2.47 and n is the number of states of A. Thus, let AS\ | n under the mappings r\ : Bn S, r2 : S -> Y+. Then, denoting by e the identity element of S, we get {Ss(Ti(8'(b, r2(e))), e) : b e Bn} = {riO$'(b, T2(e))) : b e Bn} = {^(b) : b Bn] = S. Therefore (taking a, T, A, B of the lemma to be i\, 12, AS, B, respectively), we have the conditions (1) and (2) of Lemma 3.16. Then AS can be represented by a cascade product of the automaton KT2 by the direct power Bn. Therefore, combining this with (2), for every irreducible semigroup 5, we conclude that As can be represented homomorphically by a cascade product of automata from K, for every irreducible semigroup S. Using the first part of the Krohn-Rhodes decomposition theorem, this implies that /C is complete with respect to homomorphic representations under the cascade product. The proof is complete. D Theorem 3.18. None of conditions (1), (2), (3a), and (3b) of Theorem 3.17 can be omitted. Proof. For (3a) and (3b), the statement comes directly from the Krohn-Rhodes decomposition theorem. (See Theorem 3.1.) For (1), we now show that there exists a class /C satisfying (2), (3a), and (3b), which is not complete with respect to homomorphic representations under the cascade product. Let be a (countable) system of automata with
moreover, let Then
be defined by
and Thus a subsemigroup of S(A\) is isomorphic to the monoid with two
17 Although it may be counterintuitive to those used to transformation semigroups rather than automata, to obtain (2), it is not sufficient to homomorphically represent all prime-length counters with single-letter input sets. For example, using such counters, the single-letter-input modulo-four counter cannot be homomorphically represented.
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
87
right-zero elements. On the other hand, by Proposition 1.5, for every n = 2, 3 , . . . , the degree-n + 1 symmetric group is isomorphic to S(An). Since the degree-two symmetric group can be embedded isomorphically into a larger symmetric group, and, furthermore, every simple group can be embedded isomorphically into a symmetric group, then /Co satisfies (3b). Therefore, {.4o} U /Co satisfies (3a) and (3b). Let A = ({0,1}, [x, y}, 8) be an automaton having S(i, x) = 1 and 8(i, y) = 2, i = 1, 2. Then A is a two-state reset automaton. For every positive integer n, set Bn = (A x {1,..., n + 1} U {*}, A x {jc, y}, 8'n), where * is a new symbol and
with (a, b) {0,1} x {1,..., n + 1}, (c, z) {0,1} x {x, y}. Let K, consist of the counters and all automata Bn,n = 1,2,— It is now obvious that /C satisfies (2). For (3a) and (3b), first note that for every n, An is a homomorphic image of a subautomaton of a cascade product A x Bn({x, y}, \, )- (Hint: (z) = z,
88
Chapter3. Krohn-Rhodes Theory and Complete Classes
subautomaton of D1 x • • • x D m ( X , ( p 1 , . . . , pm). If V has a state for which its th component is *, then all state of V has this property. Clearly, then D can also be represented by a cascade product D1 x • • • x D-1 x Dl+1 x • • • x D m ( X , ( p ( , . . . ,
n = 1,2,.... Moreover, let A0 = ({I, 2}, {x, y}, 1) be defined by (i, x) = 1, 0(i, y) = 2,i{1,2}. By Proposition 1.5, for every n 1, S(An) is isomorphic to the degree n symmetric semigroup. Thus both of the monoid F with two right-zero elements and the degree-n symmetric group divide S(An ) if n > 1. On the other hand, Ao is a two-state reset automaton. Therefore, {Ao} U K\ satisfies the conditions (1), (3a), and (3b). Let m be an arbitrary positive integer with m > 1, and for every positive integer n set Bn = ({1,... ,m] x (1,. ..,n}U{*}, {1,... ,m} x {x, y, w}, n), where * is a new symbol and
with (a, b) e { I , . . . , m} x {1,..., n}, (c, z) e {1,..., m} x {x, y, w}. Let K2 consist of all automata Bn, n = 1,2, It is obvious that k' = {Ao} U k2 satisfies (1). For (3a) and (3b), first note that for every n > 1, An is a homomorphic image of a subautomaton of a cascade product Cm x Bn({x, y, w}, p1, p 2 ), where Cm is a counter with m states. (Hint: ^i(z) = z,
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
89
assume that G < An for some n > 1. On the other hand, we have again that An is a homomorphic image of a subautomaton of a cascade product Hence, and, using that G is noncommutative, G < Cm is impossible. Then G < Bn follows from the Krohn-Rhodes theorem. We have seen that satisfies all of the conditions (1), (3a), and (3b). To see that K' is not complete we prove that none of the nontrivial counters can be represented homomorphically by a cascade product of factors in K'. This also shows that K! does not satisfy condition (2). Let us first note that if a counter C is a homomorphic image of an automaton A, then A has a subautomaton B isomorphic to a counter which can be mapped homomorphically onto C. Moreover, the number of states in C always divides the number of states in B. Therefore, it is enough to show that whenever B = ({x}, B, a') is a subautomaton of a cascade product and B is isomorphic to a counter, then the number of states in B is not divisible by m. For this, take a b = ( b 1 , . . . , bk) € B. For every j € {1,... k}, denote by tj the least positive integer such that . We prove that m does not divide lj, j = 1, ...,k, which in the case j = k means that m does not divide . Obviously, if 7 = 1, then either D1 = A0 or b1 = * and thus t\ = 1. We prove that ej = 1 whenever tj-i = 1 and 7 > 1. Indeed,TV-Hi= 1 implies that ( b 1 , . . . ,bk,x) = t = l,...,lj,( ) = 8 ' ( ( b 1 , . . . , bk), xn), n 1. But then either Dj; = A0 or bj = *. Thus, we get lk = 1 by induction. Therefore, if B homomorphically represents a counter C, then C is trivial (having only one state). The proof is complete. Proposition 3.19. There exists a class K, of automata which is complete with respect to homomorphic representations under the cascade product such that all elements of 1C have two input letters. Proof. We consider again a two-state reset automaton A0 (having two input letters) and define K0 as the above proof of Theorem 3.18. with Let K0
n = 2, 3,...; moreover, let A\ = ({1,2}, {x, y}, ) be defined by (l, x) = (2, x) = 2, <$i(l, y) = 2, 5i(2, y) = 1. We prove the completeness of 1C" = {Ao} U Ko- Of course, it trivially satisfies conditions (1) and (2) of Theorem 3.17. On the other hand, by (l, x) = Si(2,jc)=2,5i(l,xy) = (2,xy) = 1, (l,yy) = 1, and (2, yy) = 2. The monoid F with two right-zero elements can be embedded isomorphically into A1, as we proved in the previous proof of Theorem 3.18. Thus we obtain (3a). Finally, Proposition 1.5 implies that S(A)n is isomorphic to the degree-n+1 symmetric group (as we have also already mentioned in the previous proof of Theorem 3.18). Since every simple group can be embedded into an appropriate symmetric group and every symmetric group can be embedded into a larger symmetric group, we also have condition (3b). The proof is complete. d
90
Chapter 3. Krohn-Rhodes Theory and Complete Classes
By an elementary computation we obtain the next observation. Proposition 3.20. Let Cn be a nontrivial counter, i.e., n > 1, and let 1C be a class of automata. Cn can be represented homomorphically by a cascade product of factors from 1C if there is a multiple ofm such thatCm can be embedded isomorphically by a cascade product of factors from 1C. Further, Cm can be embedded isomorphically into a cascade product of factors from K if and only if there are automata Ai = ( A i , Xi, , ) K, i = 1,..., k, k > 0, and integers 1 = mo <m\ < • • • < mk = m such that
(1) mi_1 is a divisor of mi (i e {1,...,k}), and (2) for every i e {1,..., k} there are distinct states a 1 , . . . , a mi / mi _ 1 Ai, and a word u € X* with |u| = w,-_i and
Let us call 1C of automata precomplete if it satisfies the following conditions: (i) There is an automaton A such that F is isomorphic to a subsemigroup of S(A). (ii) For every simple group G there is an A e 1C with G < S(A). The Krohn-Rhodes decomposition theorem readily implies that every complete class for the cascade product is precomplete, but the converse fails in general. It may well happen that although 1C is precomplete, any strongly connected automaton is trivial, i.e., a one-state automaton if it can be represented homomorphically by a cascade product of factors in 1C. Proposition 3.21. Let q = pl be a prime power. There exists a precomplete class K' such that for any Ko, Cq cannot be represented homomorphically by a cascade product of factors from K' U Ko unless Cq can be represented homomorphically by a cascade product of factors from /Co.
Proof. Define the automata An, n > 3, as follows: An = ({1,..., qn} U {*}, {jci,..., xq, y}, ), where, for every i {1,..., qn} and j {1,..., q},
Observe that the word x1, ...,xq induces a cyclic permutation of the states in A' = {1, q + 1,..., q(n — 1) + 1}. Moreover, yx2 --'Xq induces the transposition y (1) = q + 1, y (q + 1) = 1, y(a') = a', a' A'\{1, q+1} of A'. Consequently, by Proposition 1.5,thedegree-n symmetric group divides S(An). In addition to the automata An define A = ({1,..., 2q] U {*}, (x, y, z,*2, ...,xq,}, 5) by the following rules: 5(1, x) = (q + l,x) = (q + l,z) = 2, (1, y) = (1, z) = (q + l , y ) =q+2, (i,xi) = i + 1 (mod 2q), (q + /,*,-) =
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
91
q + i + 1 (mod 2q), i = 2 , . . . , q, and the value of the transition function 8 is * for the rest of the cases. We have 5(1, XX2 • • -xq) = 8(q + 1, XX2 • • -xq) = q + 1, 5(1, yx2 ---Xq) = 8(q + I , y x 2 •••x q ,) = 1; further, 8 ( l , z x 2 . . . . x q ) = 1, S(q + l, Z x 2 •••*,) = q + 1. Consequently, by Proposition 2.34, S(A) has a subsemigroup isomorphic to F. Besides those mentioned above, the automata An have the following property: for every i {1,..., qn] and u ( x 1 , . . . , x q , y}+ with q x |u|, it holds that (i, MM) = *. Similarly, (i, uu) = * in A whenever i e {1,..., 2q} and M e {x, y, z, X 2 , . . . , xq}+ with q x |u|. Set K' = [A] U [An | n 3}. K' is a precomplete class. Let Ko be any class of automata such that Cq cannot be represented homomorphically by a cascade composition of factors from Ko. The above property of the automata in K' and Proposition 3.20 jointly imply that for every integer m > 1, Cm can be represented isomorphically by a cascade product of factors from K' U Ko only if Cm can be represented isomorphically by a cascade product of factors from Ko- It follows that Cq cannot be represented homomorphically by any cascade product of factors from K' U Kon Now we need some auxiliary results and definitions. Let m, n be positive integers with m > 2 or n > 2. We denote by K(m, n) the class of all strongly connected automata A = (A, { }, ) satisfying the following condition: there are distinct states a 1 , . . . t a m A such that (i) (ai,, ) 8(at, y), (a i , ) = ai (ai, ) = a i+1(modm ) for all i {1,..., m}, and (ii) for every i {1,..., m}, z € {x, y}, and u, v { }* with |u|, |v| < n, we have (a i , zu) = (ai, zv) if and only if |u| = |v|. An example of an automaton in k(m, n) if m {1,..., m}, [ x , y } , ), where
2 is C(m, n) = ({1,...,n} x
for all i € {1,..., n} and j € {1,..., m}. For later use we remark that C(m, n) is just the cascade product Cn x Clm({x, y}, ) with (i, j, x) = (i, j, y) = x and
where Cn denotes a counter (with n states) and denotes a counter with identity (having m states). In particular, C(m, 1) is isomorphic to . To include the case m = 1 (so that n 2), we define C(l, n) = ({1,..., n} U (2'}, {x, y}, 5), where 5(1, x) = 2, 5(1, y) = 2', (i, ) = (i, ) = i + 1 (mod n), i = 2 , . . . , n, (2', ) = 5(2', y) = 3 (modn). We see that C(l, n) K(l, n). The proof of the following statement is omitted. Lemma 3.22. For every pair of integers m, n with m 2 or n A € k(m, n) we have that C(m, n) is a homomorphic image of A.
2 and automaton
92
Chapter 3. Krohn-Rhodes Theory and Complete Classes
Take an automaton C(l, n) so that n > 2. For technical reasons we treat the twostate reset automaton Ao as being equipped with the fixed input signs x, y, i.e., AQ = ({0, 1}, {x, y, 8}) with 8(i, x) = 0, 8(i, y) — 1, / = 0, 1. It is easy to see that for every pair of words u, v e {x, y}* if U = V (i.e., u and v induce the same transition in C(l, n)), then either u = v = or u, , and the last letter of u coincides with that of v. On the other hand, AQ also has this property. Lemma 3.23. For all A € k(l, n), AQ can be represented homomorphically by an nthdiagonal power of A. Proof. Let A = (A, {x, y}, 8) e /C(l, n) be given. Then (i) S(fli, *) (a 1 , y), ( a 1 , x n ) = (alt yn) = alt and (ii) for every z € {x, y} and u, v € {x, y}* with |u|, |v| < n, we have (a1, zu) = (a1, zu ) if and only if |u| = |v|. By (a 1 , x) (a 1 , y), we may assume without loss of generality thatai (a1, y). Consider the nth-diagonal power B = (An, X, ) = A\ ] • • • An of A with A\ = • • • = An = A and let B' = (B', X, 8") be a state-subautomaton of B generated by its state (fli, <5(fli, jc), . . . , (a\, x n - 1 ) ) . Then none of the states a\, (a\, x), . . . , ( a i , x n - 1 ) coincides with 8(a\, y); moreover, for every p e {x, y}*, z e {x, y}, (ai, y) { (a\, pz), (a\,xpz), . . . , ( a \ , x n - 1 p z ) if and only if z = y. Let : B {0, 1} be given by
moreover, let
for every p X*, z {x, y}. By the definition of A, ty is well defined and it is a statehomomorphism of B' onto A0. D Lemma 3.24. For all A diagonal power of A.
k(m,
n),
can be represented homomorphically by an wth-
Proof. We may assume that m 2 since otherwise the statement is trivial. By Lemma 3.22 it suffices to prove that is a homomorphic image of a state-subautomaton of the nthdiagonal power of C(m, n). Consider the nth-diagonal power B = (An, X, ) = A1 A • • • An, of C(m, n) with A\ = • • • = An = C(m, n) and let B' — (Bf, X, 8") be a state-subautomaton of B generated by its state ((1, 1), (2,1),..., (n, 1)). Put ((i lf j{),..., (in,jn)) = («$((!, 1), p), 8((2, 1), ) , . . . , ((n,1),p)) and (( , ) , . . . , ( ;, ;)) = OHO, 1), pz), *((2, l ) , p z ) , . . . , <$((«, 1), pz)) for a given pair p e {;c, y}*, z { , }. Then, by the definition of C(m, n), [ii,..., in] = [i{, • • •, ] = {1,..., n}, and simultaneously,
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
93
Define :B {1,..., m} such that ^(((1,1),• • •, (n, 1))) = 1; moreover, for every p [x, y}, if(( ( ( l , 1), />), «((2,1), p),..., ((n, 1), p))) = p(x) + 1 (modm), where p(x) denotes the number of occurrences of the letter jc in the word p. Clearly, then ty is well defined and it is a state-homomorphism of the state-subautomaton B1 of the nth-diagonal product of C(m, n) onto . Lemma 3.25. Given a class 1C of automata, suppose that all counters and a strongly connected nonautonomous automaton can be represented homomorphically by a cascade product of factors from 1C. Then either AQ or can be represented homomorphically by a cascade product of factors from 1C for an integer m >2. Proof. Suppose that a strongly connected nonautonomous automaton A = ( A , X , 8 ) can be represented homomorphically by a cascade product of factors from 1C. For every x X, let Ax denote the set of all states a e A such that a = (a, xr) for some r 1. Since A is a strongly connected nonautonomous automaton, there are x\, x2 e X and a\ AXl with (a\,xi) (a1,X2). Let n 1 be any integer with the property that (a, x ) AXl for all a e A, and (a, x") = a whenever a AX}. Starting with a\, successively compute the states a\,...,at, at = (a,i-1, X2x ), i 2, until repetition occurs. Thus the states GI, ..., at are pairwise distinct and (at, X 2 x n - l ) = as for some s {1,...,t}. From the choice of n and a\ we have a\,..., at AXl and (ai;, x ) = a,,, i e {1,..., t}. If (ai, x1) = 8(at, X2) for some i {1,..., t}, then take a word v X+ with (ai, v) = a\ and define u = - We see that (a\,x\) (ai,X2) and 8(a\,x\u) = 8(a\,X2u) = a\.Letk = \u\. It is easy to prove that a cascade product of Ck+1 with A has a subautomaton belonging to k(l, k +1). (Hint: define Ck+1 x A({x, y},( , ) by
94
Chapter 3. Krohn-Rhodes Theory and Complete Classes
following hold: (1) There is a strongly connected automaton which can be represented homomorphically by a cascade product of factors from k. (2) There is an automaton A e 1C such that S(A) is isomorphic to the right-zero semigroup with two elements. Proof. The necessity of (1) is obvious, while the necessity of (2) can be derived from the Krohn-Rhodes decomposition theorem. By Lemma 3.25, either AQ or C can be represented homomorphically by a cascade product of factors from k. In the first case the proof is done. Supposing that Clm can be represented homomorphically by a cascade product of factors from 1C, choose A = (A,X, ) with property (2). By Proposition 2.34, there are states a\, ai € A and words v\, v2 € X+ with (ai, v\) = a\ and (ai, v2) = 02, i = 1, 2. We may as well suppose that |v1| = |u2| = mn for some n 2 (for v\ can be replaced by (v2V\)m and V2 by (v\V2)m). Observe that there exists an nth-cascade power of €„ which is isomorphic to the counter Cmn having mn states. Indeed, let C = ({1,..., m}, {x, y}, 5^) be given with
be given with
moreover let
(c1,..., cn} € ( 1 , . . . , m}n. An easy technical computation shows that this cascade power is isomorphic to Cmn. Now we consider a cascade product B = Cmn x A({x, y}, , ) such that (c, a, z) = x and
c e { 1 , . . . , mn}, a € A. Let B' be a state-subautomaton of the cascade product B generated by the state (1, a\). It is obvious that B' k(1, n). By Lemma 3.23 this completes the proof. D Let m 1 and n 2 be integers. We call the automaton A = (A, X, 8) an (m, ri)automaton if there are a € A, sets X i , . . . , Xm c X, and signs jti, X2 € Xi with the following conditions, where L denotes the language X\ • • • Xm:
for every
and there is a
with
Moreover, we say that A is an m-automaton if it is an (m, n)-automaton for some n 2. Obviously, A is an m-automaton if and only if | X | > 2 and it is an (m, n)-automaton forn = |X|.
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
95
Proposition 3.27. If A is an m-automaton and A is a homomorphic image of the automaton B, then B is also an m-automaton. Also, if none o f A 1 , . . . , An is an m-automaton, then no cascade product with these components is an m-automaton. Proof. For the first part of this statement, consider an m-automaton A = (A, X, 5) with a A, sets X\,.. .,Xm c X, and signs x\,x2 X1 having the above properties (1) through (3). Let B = (B, X', ') be an automaton having a homomorphism = ( ) l onto A Then for every a' € and u' € (u),u L+, L = X1. • • Xm we obtain '(a', x{) £ '(a', x'2) and that 8'(a', u'V') (a) holds for some i/ e ir2l(v), v e L*. By the finiteness of the state set B ofB, there exists a state a such that for every u' 2 l ( u ) , u is a having '(a', u'V') = a'. For the second part of our statement, consider a cascade product .4 = (A, X, 5) = .Ai x • • • x An(X, ( i,..., n) such that none of the automata At = (A t , Yt, ), t = 1,..., n, is an m-automaton for some m. Assume that contrary to our statement, A is an m-automaton with a = ( a 1 , . . . , a n ) A, a, € A,, t = 1 , . . . , n , sets X i , . . . , Xm c X, and signs x1, x2 X1 having the above properties (1) through (3). But then for every u € L+, L = Xi • • • Xn, there exists av & L* with (a, uV) = a. Suppose that (a1, ( (ai,..., an, z\)) 1 (a1, (a\,..., an, z2)) for some z1,Z2 X1 and put Xi' = { ( , . . . ') | (a't e A r , r = 1, . . . , , X,-},i = 1,..., m. But may not really depend on its state components and thus for every ... x'm X • • • X ,there exists a word x1 ...xm € L such that (a\, ...,an,xi ...xm) = x{...x'm. Then we have that for every u' e (Xi • • • X'm)+ there exists a v' € (Xi • • • X'n)* such that (a1, u'V') = a1. Thus we obtain that A\ is an m-automaton, which is a contradiction. Therefore, (a\, \(a\,..., an, z 1 )} = (ai, (a\t..., an, z2)) necessarily holds. We get in a similar way that i(a\,
<m.
Repeating this procedure for At, t = 3 , 4 , . . . , n, finally, we obtain that (a, x1) = 8(a, x2), a contradiction. Therefore, A is not an m-automaton. D The following result, which can be derived from the previous theorem, shows the complete structure of the complete classes of automata with respect to homomorphic representations under the cascade product.
96
Chapter 3. Krohn-Rhodes Theory and Complete Classes
Theorem 3.28. A class K, of automata is complete with respect to homomorphic representations under the cascade product if and only if (1) there is an m-automaton in k for some m 1, (2) for every prime power n > 1, there is a multiple m of n, automata Ai = (A{, X{, Si) € /C, i € {1,..., k}, k > 0, andintegers 1 = mo < m\ < • •• < m^ =m such that (2a) mj_i is a divisor o/m, (i e {!,...,£}), (2b) for every i e {1,..., k} there are distinct states a\,..., ami/mi_l € A, and a word u € Xf with \u\ = m/_i and 8j(ai, u) = a2,..., Si(ami/m._l-i, u) = ami/mi_
i(ami/mi_l,u')
= a\,
(3a) there is an automaton A € K such that a subsemigroup S ofS(A) is isomorphic to the monoid with two right-zero elements, and (3b) for every simple group G there is an automaton A € /C with G < S(A). D Proof. The necessity of condition (1) can be derived from Proposition 3.27. Indeed, if none of the automata At, t = 1,..., n, is an m-automaton for some m, then, by Proposition 3.27, all of their cascade products preserve this property. In addition, if B is a subautomaton of A and B is an m-automaton for some m, then A is also an m-automaton by definition. Thus, applying again Proposition 3.27, none of the cascade products of the above automata At, t = 1 , . . . , n, can represent homomorphically an m-automaton. This ends the proof of the necessity of condition (1). As regards the necessity of condition (2) of the above result, observe that all counters can be represented homomorphically by a cascade product of automata from /C if and only if /C has property (2). (See also Proposition 3.20.) By Theorem 3.17, this establishes the necessity of condition (2). The necessity of conditions (2a) and (2b) comes directly from the Krohn-Rhodes decomposition theorem. As to sufficiency, condition (2) is equivalent of condition (2) of Theorem 3.17. In addition, conditions (3a) and (3b) are the same as conditions (3a) and (3b) of Theorem 3.17. Thus, applying Theorem 3.17, it remains to show that, by our conditions, we can ensure condition (1) of Theorem 3.17. Let A = (A, X, 5) be again an m-automaton with a state a e A, sets X\,...,Xm c X, and signs x\,x2 € X\ with the following conditions, where L denotes the language Xi • • • Xm : (a) 1 < |Xi|,..., \Xm\ < n; (b) S(a, *i) + 8(a, *2); (c) for every u e L+ there is a v € L* with 8(a, uv) = a. Consider a cascade product B = ({1,..., m} x A, X, 5') = Cm x A(X, (p\, (p2) such thatCm = ({1,.. .,m}, {xcm}, c m ),f>c m (c,xc m ) = c + 1 (modm),
3.2. Some Results Related to the Krohn-Rhodes Decomposition Theorem
97
p e X* there exists a q e X* such that <5'((1, a)) = (1, a). In other words, the state (I, a) of B generates a strongly connected nonautonomous state-subautomaton of B. By Lemma 3.26, this completes the proof. Proposition 3.29. None of conditions (1), (2), (3a), or (3b) of Theorem 3.28 can be omitted. Proof. By Proposition 3.27 we cannot omit condition (1). The rest of the statement is a direct consequence of Theorem 3.18. A well-known open problem is whether the following natural question is undecidable in general. Problem 3.30. Given a finite class K. of automata and a finite automaton A, decide whether A can be represented by a cascade product of automata from JC. Lemma 3.31. Let A = (A, X, 5) be an automaton having states a, b A, a b, words p,q,r X+, \p\ = \q\, with 8(a, p) = a, S(b, p) = b, S(a, q) = b, 8(b, r) = a. Then there exists a single-factor product A(X, (p) such that Fcan be embedded isomorphically into S(A(X, ( )}, where F denotes the monoid with two right-zero elements. Proof. Consider the automaton A having the conditions of Lemma 3.31. Furthermore, let B = ({a1, a2), {X0, x1, x2}, ) be an automaton with S#(a,, XQ) = at, <$£(a,, */) = aj, i, j {1,2}. Clearly then S(B) is isomorphic to F. Thus, it is enough to find a singlefactor product A(X, cp) which isomorphically simulates B by nonempty words. By our conditions in Lemma 3.31, there are words p,v'(= qr), v"(= pr), w'(= q), w"(= p) X+, \v'\ = \v"\, \w'\ = \w"\ with 8(a, p) = a, (b, p) = b, (a, v') = 8(b, v") = a, 8(a, w') = 8(b, w") = b. It can be seen that in this case there exists an unambiguously defined
98
Chapters. Krohn-Rhodes Theory and Complete Classes
Then A isomorphically simulates B by nonempty words under r\ : {a, b} -> (a\ ,02], r2 : (XQ,XI, x2} -> {«, v, w] with Ti(a) = a\, T\(b) = a2, T2(x0) = u, r2(*i) = v, T2(x2) = w. This is the end of the proof. n Lemma 3.32. Let A = (A, X, 5) be an automaton such that G < S(A)for some noncommutative group G. There exists a single-factor product A(X,
(Note that the orders of Sx and 8y are each more than 1, since these group elements do not commute.) Observe that each of these words is of the same length, namely, of length o(8x)\x\ + o(8y)\y\. We compute that a • q = a0 • xyq = a0 • xyy x yx = a0 • x y x y x = a Q • xx yx = a 0 • x 0 yx = OQ • yx = b. It is trivial to check that a • p = a, b • p = b, and b • r = a. But then the states a, b and the words p,q,rofA satisfy the conditions of Lemma 3.31. This ends the proof. D Lemma 3.33. Let A = (A, X, 5) be an automaton such that G < S(A)for some noncommutative group G. Then A satisfies Letichevsky's criterion. Proof. Given an automaton A with n states, let G < S(A) for a noncommutative group G. By Proposition 2.47 we obtain AG < A n, where A n denotes the nth-diagonal power of A. It is clear that AG is strongly connected. In addition, G is noncommutative. Thus AG is a noncommutative strongly connected automaton. Therefore, by Proposition 2.76, AAn satisfies Letichevsky's criterion. Obviously, then A also has this property. This ends the proof. D Lemma 3.34. Let A = (A, X, 5) be an automaton having Letichevsky's criterion with a stateaQ € A, inputletters x, y X, and words p, q X* suchthat (a0, x) (a0, y) and (ao, xp) = (ao, yq). There exists a single-factor product B = A(X, (p) and a counter Ck such that the two-state reset automaton can be homomorphically represented by an aQ-productCk x B +2({x, y], ,..., |pq|+2). Proof. Let A = (A, X, 8) be an automaton having Letichevsky's criterion with a state a0 A, input letters x, y e X, and words p, q e X* such that 8(ao, x) ^ S(OQ, y) and
3.2.
Some Results Related to the Krohn-Rhodes Decomposition Theorem
99
(a0, xp) = (a0, yq). Suppose that (a0, xp') = (ao, yq') holds for some p'', q' € X having p = p'p", q = q'q"'. Then A will also have Letichevsky's criterion for the state ao> input letters x, y X, and words p'q", q'q". Therefore, we may assume p" — q" whenever (ao, xp') = (a0, yq') holds with p = p'p", q = q'q". We also assume the minimality of p and q such that 8(dQ, xp') = 8(dQ, xp'p") implies p" = A., and, similarly, 8(dQ, yq') = 8(d0, yq'q") implies q" = A for every p', p", p'", q', q", q'" with p = p'p"p'" and q = q'q"q'". Thus the following feedback function is unambiguously defined.
[for
Consider the single-factor product B = (A, {x, y}, SB) = A({x, y},
Put H
(Note that Let the product M receive the input signal z m its state (c, b\,..., bk) e H. The next state <$x ((c, b\,..., bk), z) is obtained in the following way. The first component c is set to c + 1 (mod A:), the c (mod A:) + 1-th component &c(modit) = «o is replaced by 8e(aQ, z), the c + 1 (modfc) + 1-th component &c+i(mod;t) = 8(aQ, z'), z' e {*, y} assumes the value 8(a<), z'z\), and each of the components bc+s(modk)+i = 8(aQ, z"z\... zs-i), z" e {x, y}, s = 2,..., k - 1 is changed for £,+,-+1 (m0dfc) = <$(flo, z"zi •.. z,). Thus, for every (c, b\,..., bk) the c — 1 (mod k) + 1-th component bc-i (mod/t) shows the value of the last incoming input letter for M. Define AQ = ({ai, aj\, {x\, X2], SQ~) with 5o(«,-, Xj) = «;, i, j e {1, 2}. Then AQ is the two-state reset automaton. For every (/, b\,..., bk) €. M we represent the state of AQ by &/_i (mod*) such that, say,
It is obvious that ^ : H —> {a\, d2\ is a homomorphism of a state-subautomaton of M. onto >^. This ends the proof.
100
Chapter 3. Krohn-Rhodes Theory and Complete Classes We have the following direct consequence of Theorem 3.17.
Theorem 3.35. A class JC of automata is complete with respect to homomorphic representations under the a. \-product if and only if (1) the two-state reset automaton can be represented homomorphically by an a\-product of automata from /C, (2) every counter (of prime power length) can be represented homomorphically by an a\-product of automata from k, (3a) there is a single-factor product B of an automaton A € K such that a subsemigroup S of S(B) is isomorphic to the monoid with two right-zero elements, and (3b) for every simple group G there is a single-factor product B of an automaton A e /C with G < S(B). Now we are ready to prove the following well-known result. Theorem 3.36. A class 1C is complete with respect to the homomorphic representations under the ct\-product if and only if (1) every counter (of prime power length) can be represented homomorphically by an a\-product of automata from /C, and (2) for every simple group G there is an automaton A € K, having a single-factor product BwithG < S(B}. Proof. The necessity of (1) and (2) are obvious. To show sufficiency it is enough to prove that by our conditions (1) and (2) we obtain the conditions of Theorem 3.35. Indeed, using conditions (1) and (2) of our statement, condition (1) of Theorem 3.35 comes from Lemmas 3.33 and 3.34. Furthermore, using again conditions (1) and (2) of our statement, condition (3a) of Theorem 3.35 is a direct consequence of Lemma 3.32. The proof is complete, in Proposition 3.37. Neither condition (1) nor (2) of Theorem 3.36 can be omitted. Proof. It is trivial that none of the counters satisfies Letichevsky's criterion. Thus the class of all counters is not complete with respect to the homomorphic representations under the general product and thus it is not complete for the homomorphic representations under the a\ -product. Then it is obvious that we cannot omit condition (2). Now we prove that we cannot omit condition (1). For every n > 2, let An = (An, Xn,8n) be the automaton where An = {0,1,..., n, 1',..., n'}, Xn = {x1,..., xn}, n(0, ,-) = i, Sn(i, jci) = 0, n(i, Xj) = i', n(i', xk) = i for every i, k {1 , . . . , n } , j ( 2 , . . . , n}. To see that /C = [An \ n > 2} satisfies (2) of Theorem 3.36, we show that the degree(n — 1) symmetric group can be embedded isomorphically into the semigroup of a single factor product of An. Obviously, this holds if and only if the degree (n — 1) symmetric group can be embedded isomorphically into the semigroup of the digraph Dn = (An,{(a,b) | a,b An, there exists x e Xn : n(a,x) = b}) which has the structure Dn = (A B , {(0, i), (i, 0), (i, i'), (i', i) | i = 1 , . . . , n}).
3.3.
Homomorphically Complete Classes Under the Quasi-Direct Product
101
To prove this fact, we consider a game similar to that in the first part of Section 2.1: let us place n — 1 coins c, onto the vertices 1',..., (n — 1)' so that c, is placed onto i'.lt is sufficient to prove that every pair of coins can be interchanged so that the others get back to their initial locations. We can restrict ourselves to the case that c\ and ci are the coins to be interchanged. Let us first move c\ to n' in four steps along the path 1'lOnn'; meanwhile all other coins are rotated around the cycles i'li', i = 2,..., n — 1, since there are no loop edges. After this transformation we see that c\ is on n', and for every i = 2 , . . . , n — 1, c,is back on vertex i'. Next, in a similar way, move ci to 1' along the path 2'2011' and rotate the coins c\,c3,..., cn-\ around the cycles n'nn', 3'33',..., (n — l)'(n — l)(n — 1)', respectively. Now the placement of the coins is this: c\ is on the vertex n', GI is on 1', and for / = 3,..., n — 1, c, is on /'. Finally, with a similar procedure, move c\ to 2' so that all the coins c, get back to i', i = 3 , . . . , n — 1, and ci gets back 1'. This completes the proof that JC satisfies (2). To see that k = [An \ n > 2} does not satisfy (1) we show that for every ai-product B of factors from JC, none of the counters of length greater than 2 can be represented homomorphically by B. Assume to the contrary that there is such a counter. By Propositions 2.59 and 3.20, there are a single-factor product A = (An, X, 8) = An (X, (p), distinct states a\, ...,
3.3
Homomorphically Complete Classes Under the Quasi-Direct Product
Recall that a quasi-direct product of automata is a special type of the general product such that the feedback functions of the component automata are really independent of the state components. Therefore, a quasi-direct product of automata At — (At, Xt, ,), t = 1,..., n, can be given as an automaton A = (A, X, 8) = At(X, ,...,
102
Chapter 3. Krohn-Rhodes Theory and Complete Classes
Theorem 3.40. There exists no minimal complete class of automata with respect to homomorphic representations under the quasi-direct product. Proof. Consider an arbitrary complete class k of automata with respect to homomorphic representations under the quasi-direct product. It is enough to show that for every automaton A = (A, X', 8A), the class K \ {K} also is a complete class of automata with respect to homomorphic representations under the quasi-direct product. Let A = {a\ , . . . , « „ } and take two distinct symbols X0, x\ X'. Consider an automaton B = (B, X, B) for which B = {1,..., n2 + 1}, X = X' U {x0, xi}; moreover, for all b e B and x X,
Consider a subautomaton B" = ({1,..., n}, X', 8'B) of B. It is clear that B" is isomorphic to A. Therefore, for our theorem it is enough to prove that B can be represented homomorphically by an appropriate quasi-direct product of automata from k \ {A}. It can be seen that B satisfies the following condition: (1) For every b, c e B there exists ape
X+ with 8&(a, p) = 8&(b, p).
Indeed, in case b = c this is obvious. Now let b ^ c. Using the definition of , we have that by b < c, p = (xiXQ -l y- b and, similarly, by b > c, p = +l c l b c x£ - (xix£- ) - satisfy condition (1). We show that for all distinct states a/, aj• e A of A and also for every word p'0 = x{... x't, x(,..., x't e X' satisfying <$B(a,, p') = SB (a/, p'), there exists a word p € [ x ( , . . . , x'tY such that 65(0,, p) = SB(OJ, p) and \p\ < n(n — 1). Indeed, assume that for an appropriate index r, 1 < r < t, there exists an s, 1 < s < t — r, such that (a,<, x{... x'r+s) = %(o,, x{... x'r+s) = SB(OJ, x{... xfr). Then, by the input word x'r+s+l... x't, SB(a,, x{... x'r+sx'r+s+l... x't) = 8B(ai,x'l... x'rxfr+s+l... x't) and 8s(aj, x{... x'r+sx'r+s+l... x't} = 8 B ( a j , x { . . . x'rx'r+s+l... x't}. Consequently, the word p can be constructed such that its length does not exceed the number of pairs (ar, as) A x A, ar ^ as. Thus, \p\ < n(n — 1) holds. Let Dt, = (Dt, Xt, f), t = 1,..., m, befiniteautomata having an index t {1,..., m} with Dt = A. Suppose that a quasi-direct product M. = , • • • m} can be given such that it homomorphically represents B. By Proposition 2.52, we may also assume thatjVfhasastate-subautomatonA/' = ( N , X , ) with a state-homomorphism : N B onto B. (And then Y = X.) Assume that A/" is minimal in the sense that B is not a statehomomorphic image of a proper state-subautomaton of M. By the definition of SB, B is strongly connected. Thus, using Proposition 2.25, N is also strongly connected. Because of Proposition 3.39, we can assume that either every Dt, t = I,..., m, is equal to A or there exists an index k € {1,..., m} such that A £ [ D 1 , . . . , D k } , but A = Dk+\ = •• • = Dm. Especially, thus Dm = A necessarily holds. Since |A| < |B|, by the assumption that M. state-homomorphically represents B, it follows that m > 1.
3.3. Homomorphically Complete Classes Under the Quasi-Direct Product
103
Consider the quasi-direct product Mi = Dt(X,
However, using that for every b, c e B there exists a p e X+ having 8B(b, p) = 8B(c, p), we obtain the existence of a word q X+ with 8B(\js((di, ...,dm, ai)), ) — SB( ((di,..., dm, aj)), x'0q). Since JV is strongly connected, an r e X+ can be found such that8tf((di, ...,dm, a,-),x* Q qr} = ((di, ...,d m ,ai), )Hence, ((d1,..., dm), x'0qr) = SMl((d\,..., dm), X'Q), where 5^, denotes the transition function of the quasi-direct product MI . On the other hand, using, in order,
and we get
For every u = 1,..., m we extend the function u : X -+ Xu to X+ such that for all x'lt...,x'k X, u ( x { . . . x ' k ) = u(x{)...(pu(xfk). Continuing the proof, that t / f ( ( d i , . . . , dm-i,di)) = ^ f ( ( d \ , . . . , dm-i,aj)) holds for all pairs (d\,..., dm-\,«,-), (d\,..., dm-i,Oj) e N, we show that (2) for every positive integers and r' e X+, 8A(aj, Vm^r')) ^ 8A(ajt
^(x^qrYr')).
Indeed, by virtue of <5 B (^((di,..., dm, a;)), x'0qr) = 8B(if((di, ...,dm, a,-)), x'Q) = n + 1 and 8*f((di, ...,dm,a,),x'Qqr) = 8j^((di, ...,dm,a(),x'0), we get 8B(^((di,..., d m , a j ) ) , X ' 0 ( q r ) z ) = SBW((di,... ,dm, ai)),xl(qr)*-1) = ••• = 8BW((di,... ,dm, ai)),xt0)=n + l. Consequently, because of 8&(\ls((d\, ...,dm, a,-)), XQ) = n + 1 ( (( i , . . . , dmtOj)), X'Q), 8B(ir((di,..., d m , d j ) ) , X'Q) ^ n + 1 = 8B(\(f(di, ...,dm, a,-), x'0(qr)z). Thus, according to the definition of 8B, for every word r' € X+ with \r'\
104
Chapter 3. Krohn-Rhodes Theory and Complete Classes
From this, by the substitution r" = r', we obtain 8u(du,
3.4
Homomorphically Complete Classes Under the Cascade Product
The following statement is a direct consequence of Theorem 3.1. Lemma 3.41. Let K,bea class of automata having fewer states than an appropriate prime number p and let C be a counter with p number of states. Then C cannot be represented homomorphically by a cascade product of factors from 1C.
3.4. Homomorphically Complete Classes Under the Cascade Product
105
The next statement is obvious. Lemma 3.42. Let Cbea nontrivial counter and take a cascade product M. = (Mi x • • • x Mn, X, 8) of automata Mt = (Mt, Xt, 8t), t — 1,..., n, with the following properties: (1) C can be represented homomorphically by M.. (2) There exists a positive integer k and a fixed-state m of an appropriate Ms, s {1,..., n}, such that 8((mi,..., m n ), xk+£) e MI x • • • x Ms_1 x {m} x Ms+\ x • • • x Mn, ( m 1 , . . . , mn) € MI x • • • x Mn, x € X, t = 0, 1, Then C can be represented homomorphically by a cascade product of factors Mi,...,Ms-i,Ms+i,...,Mn. Now we prove the following. Lemma 3.43. LetC = (C, {xc}, 8c) be a nontrivial counter and let k be a class of automata such that (1) C can be represented homomorphically by a cascade product of factors from /C, (2) N € k implies that C cannot be represented homomorphically by a cascade product of factors from K \ {N}. Then for every automaton A=(A, XA, A) there exists an automaton B=(B, XB, and a nontrivial counter D = (D, { X D } , ) as follows:
)
(3) B is a two-degree weakly nilpotent automaton. (4) A and D can be represented homomorphically by a cascade product of components from K, U {B}. (5) D cannot be represented homomorphically by a cascade product of factors from /C. (6) If any nontrivial counter £ can be represented homomorphically by a cascade product of factors from (K \ {N}} U {B} and A/" e /C, then £ can be represented homomorphically by a cascade product of factors from k \ { N } . Proof. Denote p a prime number for which every element of K has fewer states than p. Construct automata D = ({!,..., p], {*£>}, <$£>) and B = (B, XB, B) in the following way. Set
moreover, let B
Obviously,
and
with
and Thus, (3) holds.
106
Chapter 3. Krohn-Rhodes Theory and Complete Classes
To (4), take a cascade product of factors from K and let N = (N, {xc}, ) be a (state-)subautomaton of N having a (state-)homomorphism : N --> C onto C. Because of (1) there exists such an N, obviously. Denote (C 0 , X0) a fixed element of C x XA and construct the ao-product M. = with M n+i = B as follows: For any state ( m 1 , . . . ,mn,(c,a, d)) and input letter x of M. let
and
Take the subset M' of state set of M with M' = {(m 1 ,..., mn, (c, a, d)) \ ( m 1 , . . . , mn, (c, a, d)) € N, (c, a, d) B \ {(a0, a0, a0)}, ( m 1 , . . . , mn) = c}. By an easy computation we get that : M' -> A with ((m 1 , ...,mn,(c,a,d))) = a is a statehomomorphism of a suitable state-subautomaton of M. (with state set M') onto A Take an arbitrary fixed element xA of XA and let XA), t = 1,..., n + 1, holds for every state ( m i , . . . , mn, (c, a, d)) of M.'. It can be easily shown that : M' -> D with ((m 1 ,..., mn, (c, a, d))) = d is a state-homomorphism of an appropriate state-subautomaton of M! (with state set M') onto D. This ends the proof of (4). In consequence of Lemma 3.41 we receive (5). To (6) let us take a cascade product M = (M1 x • • • x Mn, X, )= , ,..., of factors Mt = (Mt, Xt, ), t = 1 , . . . , n, from (K \ {N}) U {B} and suppose that a nontrivial counter C' can be represented homomorphically by M. Obviously, by M1 = B thefirstcomponents of states ( ( m 1 , . . . , mn),x2+i), (m 1 ,... , m n ) e M1 x • • • x Mn, x e X, e = 0, 1 , . . . , are equal to (a0,, a0 , a0). Thus, by Lemma 3.42, we can suppose M1 B. Let s, 2 < s < n, be the first index (if it exists) with Ms = B. By (2) we obtain that C cannot be represented homomorphically by a cascade product of factors M 1 , . . . , M s - 1 • Consequently, for every pair c e C,m M1 X - - - x Mn and input letter x X there exist positive integers k1, k2 such that the first 5 — 1 factors of (m, xkl) and SM (m, xk2) coincide but . Then either the sth factor of (™, xkl+l) or the k2+l sth factor of (m, x ) coincides with (a0, a0, a0). Obviously, then the 5th factor of (m, Xmax(*i.*2)+^)) i — i 2 , . . . , coincides with (OQ, OQ, ao). Therefore, there exists a positive integer k, such that for every state m and input letter of M., the 5th factor of &M (m, xk) coincides with (a 0 , , a 0 , a0). Then, using Lemma 3.42, we can suppose Ms B. Repeating this procedure we have that C' can be represented homomorphically by a cascade product of factors from K \ N. This ends the proof of Lemma 3.43. n Lemma 3.44. Assume that for a given finite list C0, ..., Cj of nontrivial counters there canbe found a finite list B 1 , . . . , Bj, Bi+1, . . . , B i+j of automata having the following properties: (1) For arbitrary k {0,..., j], Ck can be represented homomorphically by a cascade product of factors from { B 1 , . . . , Bi+k}.
be a cascade pro
3.4.
Homomorphically Complete Classes Under the Cascade Product
107
(2) ByN (B\,..., Bi+k}, k = 0 , . . . , j, none ofCk,.. -, Cj can be represented homomorphically by a cascade product of factors from (B\,..., Bt+j }\N. Then for every automaton A there exists an automaton Bt+j+i and a nontrivial counter Cj+i as follows: (3) Bi+j+i is a two-degree weakly nilpotent automaton. (4) A and Cj+i can be represented homomorphically by a cascade product of factors from (5) IfJ\f € {Bi,..., Bi+k}, k = 0 , . . . , j+1, then none of Ck,..., Cj+1 can be represented homomorphically by a cascade product of factors from {B\,..., Bi+j+1] \{N}. Proof. Considering /C = (B\, . . . ,Bi+j;}and C = Cj, we obtain conditions (1) and (2) of Lemma 3.43. Then, using the notation #,•+_/+! = B and Cj+1 = D, it can be assumed that properties (3)-(6) of Lemma 3.43 are satisfied. Because of (3) and (4) of Lemma 3.43, we can see the validity of (3) and (4) directly. It remains to show (5). Suppose that to the contrary of our statement, for an appropriate k,0
108
Chapter 3. Krohn-Rhodes Theory and Complete Classes
the cascade product, then it should be a minimal homomorphically complete class under the cascade product too. Thus, it is enough to prove that every automaton A = (A, X, <5) can be represented homomorphically by a cascade product of factors from (JC U /Ci). Consider for an arbitrary automaton A the automaton Ai = (Ai, Xi, ;) in F having an isomorphism onto A. Using (1), we have that Ai can be represented homomorphically by a cascade product of factors from K U K1. Therefore A also has this property. This ends the proof. We obtained the following direct consequence of this result. Corollary 3.46. There exists a minimal homomorphically complete class under the cascade product. Finally, we note that, by Lemma 3.41, there exists no finite homomorphically complete class of finite automata under the cascade product.
3.5
Bibliographical Remarks
Section 3.1. Theorem 3.1 issued from K. B. Krohn and J. L. Rhodes [1962 and 1965]. A more detailed description of this result was developed by K. B. Krohn, J. L. Rhodes, and B. R. Tilson [1968]. It has a new proof in Esik [1999]. An extension of Theorem 3.1 was given by Z. Esik [1989a]. An attractive presentation of the Krohn-Rhodes theory was given by A. Ginzburg [1968]. The proof of Theorem 3.2 was described in Lallement [1971] and Eilenberg [1976]. Some aspects of the Krohn-Rhodes theory were studied by J. L. Rhodes and B. R. Tilson [1989], B. Austin et al. [1995], C. L. Nehaniv [1996], and Z. Esik [2000]. Results in this section (with the notable exception of the holonomy decomposition theorem) are mostly originally due to and derived from K. B. Krohn and J. L. Rhodes [1962 and 1965] and appear in the book edited by Arbib [1968]. They have been reformulated and treated by many authors, e.g., A. Ginzburg [1968] and S. Eilenberg [1976]. Lemmas 3.4, 3.5, 3.6, and 3.7 can be derived from the results of A. Ginzburg [1968]. Theorem 3.8 is due to H. P. Zeiger [1967]. Theorem 3.10 issued from K. B. Krohn and J. L. Rhodes [1962, 1965]. The original idea of the holonomy decomposition theorem (Theorem 3.9) is due to H. P. Zeiger [1967], with a correct proof for partial transformation semigroups given by S. Eilenberg [1976]. Our proof, which makes reference only to fully defined transformation semigroups, is inspired by Eilenberg's. Section 3.2. Proposition 3.11 and Corollary 3.12 were discovered by Z. Esik [1991b]. Theorem 3.13 can be derived from Z. Esik [1989a]. Proposition 3.14 was found by H. P. Zeiger [1967]. Lemma 3.15 appears in Domosi [1984]. Lemma 3.16 is an extended form of the Lemma 1.3 of F. Gecseg's book [1986, p. 25]. Lemma 3.16 was also proved by P. Domosi [1984]. Theorem 3.17 was elaborated by Z. Esik and P. Domosi [1986]. Theorem 3.18 was shown by P. Domosi and Z. Esik [1988a]. Proposition 3.19 was found by Z. Esik and J. Vkagh [1986]. Proposition 3.20 was developed by Z. Esik and P. Domosi [1986]. Lemmas 3.22, 3.23, 3.24, 3.25, and 3.26 were proved by P. Domosi and Z. Esik [1988a]. Lemma 3.27 is a new result. Theorem 3.28 is a strengthening of Theorem 3.17 and can be derived from Theorem 3.17 using results in Esik and Domosi [1986] with results from
3.5. Bibliographical Remarks
109
Domosi and Esik [1988a]. Theorem 3.29 is from Z. Esik and P. Domosi [1986]. Some related connections were described by P. Domosi and Z. Esik [1986] and P. Domosi and Z. Esik [1988b, 1988c]. Lemmas 3.31, 3.32, 3.33, and 3.34 are essentially new results. Theorem 3.35 is a direct consequence of Theorem 3.17. Theorems 3.36 and 3.37 were shown by Z. Esik [1986]. Section 3.3. Theorem 3.40 was shown by P. Domosi [1980]. Section 3.4. A minimal homomorphically complete system under the «o-product was presented by P. Domosi [1976]. A nice presentation of this result is in Gecseg [1986]. The results of this section are based on Domosi [1982].
This page intentionally left blank
Chapter 4
Without Letichevsky's Criterion
In Chapter 5 we will see the importance of Letichevsky's criterion in the composition of automata networks. In this chapter we consider networks of automata without Letichevsky 's criterion. In particular, we describe several types of networking with very restricted structure of the permitted links. Assuming that the component automata are rather simple of particular types, the resulting networks that can be constructed are already computationally as general (with respect to homomorphic representation) as what can be constructed with unrestricted networking. We also show that the hierarchy of vi -products (automata networks in which there are at most i links to an automata from components of the network) is strict for this type of representation. We prove even more: The ao-Vi-hierarchy is strict for both homomorphic representation and homomorphic simulation. In addition, the v/ -hierarchy also has this property. This means that the number of permitted links may have a strong influence on the computational capacity of the network if component automata have a certain structure (i.e., satisfy the so-called semi-Letichevsky criterion).
4.1 Semi-Letichevsky Criterion We start with the following statement. Proposition 4.1. Let A = (A, X, 8) be an automaton having the semi-Letichevsky criterion and let a € A, jc, y e X, p e X*, (a, x) (a, y), (a, xp) = a (such that for every q e X*, a (a, yq)). For every automaton A' there exists a single-factor product M. of A such that A can be represented homomorphically by a diagonal product of its connected state-subautomata andM.. Moreover, we also have this property for a single-factor loop-free product M. of A whenever (a, xk) = a holds for some positive integer k. Proof. Let A = (A', X', ') be an arbitrary automaton. Assume that (a, xk) = a holds for some positive integer k and then construct M. = A(X', (p) such that for every b 6 A, x' € X', (b, x') = x. In this case, M. is a single-factor loop-free product of A. Otherwise, put p = x1 ...xm withai = (a,x),a2 = (a 1 ,x 1 ), . . . , a m = (a m-1 ,x m-1 ),a = (am,xm), 111
112
Chapter 4. Without Letichevsky's Criterion
and for every b e A, x' e X', let
Then At is a single-factor product of A. In both cases we have S(8(a, x), (p(8(a, x), q)) ^ 8(8(a, y),
for all x e X. We have the following. Lemma 4.2. Every automaton in C. can be represented isomorphically by an otQ-V2-power of the elevator. Proof.LetA = ({0,..., n}, X, 8A) e C.lfn = 1, then A can be represented isomorphically by a quasi-direct power of the elevator having a single factor. Thus we may suppose that n > 1. Consider the ao-vz-power £%+1(X,
Clearly then we can assume that
is a state-isomorphism of A onto a subautomaton of
4.1 . Semi-Letichevsky Criterion
113
Lemma 4.3. Every monotone automaton can be represented homomorphically by a diagonal product of automata from L. Proof. Let £' be the class of all automata A = ({0, . . . , n}, X, 8A), n = 1,2,...,
S*(0, *) = 0, 8A(n, *) = n and 8A(j, jc) € {0, ;, j + 1}, 0 < j < n, for all x e X.
First we prove that all elements in £' can be represented homomorphically by a diagonal product of factors from £. Consider an arbitrary automaton A = ({0, . . . , n}, X, 84) e £' with n > 1. (We can take out of consideration the trivial case n = 1.) Define automata t), = 2,...,n, having
A(j,x)
ifj = t-l,
S
for all jc e X. Clearly then At e £ for all t = 2, . . . , n.
AUTOMATON An
Letfi c A 2 x - • -xA n withB = {(1,..., 1), (2,.... 2), (2, 3,.... 3),.... (2, . . . , £ , . . . , € ) , . . . , (2,..., n)} U {(l1..., ln) | 0 e {€1,..., €„}}. By an elementary computation we have that the mapping \js : AI x ... x An -> {0,...,n} with
is a state-homomorphism of an appropriate state-subautomaton of the diagonal product Ai A • • • A An onto A. Using the transitive property of the diagonal product, to establish our assertion we shall prove that every monotone automaton can be represented homomorphically by a diagonal product of factors from CJ. Consider a monotone automaton D = (D, X, 8-p) and denote a partial ordering on D for which d -D(d,x),d D,x X. Take a rearrangement d\,..., dn of the elements of D such that for every dt, dj D, di dj, and d, < dj implies i < j. Consider all bijective mappings of the form fs : {di, ...,dn} {1,..., n], s = !,...,«!. For every mappuig fs (1 s n!), define an automaton As = ({0, ...,n},X,8s) having
It is clear that As e £', 1 < 5 < «!. Take the diagonal product M — A\ A • • • A.An. We shall prove that M. homomorphically represents the automaton A. Define the set B C {0,..., n}nl as follows: (1) For every d^ € D there exists a (b\,..., bm) e B and an s e {!,...,«!} having f,(
114
Chapter 4. Without Letichevsky's Criterion
(2) For every (b1,..., bm) e B and s, t {1,..., n!}, 0 {bs,, bt,} implies f (bs) = ft-l(bt). (3) For every pair (£1,..., )) e B, t {1,..., n\], bt 0 implies that for arbitrary xi,... ,xr e X there exists an s {!,...,«!} with f (bs) = f (bt) and f (8s(bs, x1. ..x j )) = 8v(f (bt), Xl. ..*,-), 7 = 1, . . . . r. Let i/r : B {d\,..., dn] be a mapping for which ((b\,..., bn\)) = dk whenever (b\,..., bn\) e B has a component bt, t {1,...,n!} with f (bt) = dk. By conditions (1) and (2), \jf is a well-defined surjective mapping. Using (3) and the definitions of the mappings S, s = 1,..., n\, \ l f ( ( & i ( b \ , x ) , . . . , 8m(bn\, jc))) = 8x>(if((bi, ..., b n! )}, x), (b1, ..., bn\) €B,xeX. Therefore, the diagonal product A\ A • • • AAn has a state-subautomaton (with state set B) having a state-homomorphism onto A. By Lemmas 4.2 and 4.3 we can immediately derive the next statement. Theorem 4.4. Every monotone automaton can be represented homomorphically by an -V2-product of the elevator. Now we turn to the automata having the semi-Letichevsky criterion. Let A = (A, X, <5) be an automaton satisfying the semi-Letichevsky criterion. Given a state a € A, put A'a = A'a = 0 if there exists no x e X, p e X* having (a, xp) = a. Otherwise, let p e X* be the shortest word having this property for an appropriate x e X, and put
Given a positive integer r, a nonnegative integer s, we say that A is (r, sO-weighted if there exists an a e A with \A'a\ = r and |A£| = s. (Of course, it may be possible that A is (r, 5)-weighted and, simultaneously, (r', s')-weighted such that (r, s) /= (r;, 5') (with r, r' > 0).) Proposition 4.5. Let A be an (r, s)-weighted automaton (having the semi-Letichevsky criterion). There exists a single-factor product B of A such that B is an (r, r — l)-weighted automaton. Proof. Let A = (A, X, 8) be an (r, s)-weighted automaton (having the semi-Letichevsky criterion). There are a e A, x, y e X, p € X*,8(a,x) ^ 8(a,y),8(a,xp) = a with \A'a\ = \xp\ = r, IA^I = s (such that for every q € X*, a ^ 8(a,yq)). Put xp = xi • • • xr, xi,..., xr € X. Define (p : A x X -> X such that for every a' e A, x' € X,
It is clear that the single factor product A(X, (p) of A is an (r, r — l)-weighted automaton. Define the automaton £'k = ({1 ,...,/:,*}, {xi, x2}, 8'k) with 8'k(i,xi) = i + l (mod k), <%(*> *i) = *> ^fe(1' *2) = <%(*' JC2) = *,1
4.1. Semi-Letichevsky Criterion
115
SEMI-ELEVATOR £'k
Lemma 4.6. Let A = ( A , X , 8 ) be an (r, s)-weighted automaton (having the semiLetichevsky criterion). The semi-elevator of length r can be represented homomorphically by a diagonal power Bs+1, where Bis a single-factor product of'A. In particular, ifs = r — l, then we may assume that B is an input-subautomaton of A. Proof. By our conditions, there are a € A, x, y e X, p e X*, 8(a, *) ^ 8(a, y), 8(a, xp) = a with \A'a\ = \xp\ = r, \A'^\ = s (such that for every q X*, a 8(a, yq)). For technical reasons, we put a\ = a and xp = z\*--Zk such that z\,..., Zk € X, k > 1. Moreover, we put a,+1 = 8(a, z\ • • • z/), 1 < i < k, and A' = [a\,..., ak}. Let us consider the semielevator £'* of length k having £'k = ({1,..., k, *}, [xi, X2\, 8'k) with 8k(i, x\) = i + 1 (modfc), 8'k(*, *1 = *, 8k(i, *2) = 8k(*, x2) = *, 1 < i < k. We prove that £'k can be represented homomorphically by an appropriate diagonal power Bs+l such that (1) B is an input-subautomaton of A if s = \p\, and (2) # is a single factor product of A if s < |/?|. Let a,,,..., a,-, € A' be distinct states such that 8 (afj, yij) e A' for every yij. e X, j = l,...,s. Ifs = \p\, then let B be the input-subautomaton of A with input set {x, y}. Obviously, then 8(at,x) = ai+i(modk) A' and (aj, y) = a,+i(mod*) A' hold for every i € {!,..., k}, j {2,..., k}. In addition, (a1, y) i A'. I f s < \p\, then let B = A({x, y},
Clearly, then B has a state-subautomaton B' = (B', {x, y}, 8') generated by its state a\ such that for appropriate distinct states a\,..., a^ we have 5'(a,, x) = fl,+i(modik)> and simultaneously, for every j e {!,...,*},^ e X*, 8'(ai r yq) £ A'. Consider the state-subautomaton D = (D, Y, 8") of the diagonal power (B')s+l generated by the state (0i, ...,as+i). For every positive integer m, we obtain 8"((a\,..., as+i),xm) = (flm+KmodJt), • • • , «m+5+i(mod*))- Simultaneously, if r = xuy, then for every q € [x, y}*, there exists a t € {1,..., s + 1} with 8'(at, rq) £ (a\,..., ak}. Hence 8"((ai,..., a j+ i), rq)
(a|rq|+l(mod/fe)» • • • , a\rq\+s+l(modk))-
116
Chapter 4. Without Letichevsky's Criterion Define the mappings
:D
{1,..., k, *},
: {x,y}
{x1, x2} with
fa(x) = jci, (y) = x2- By an elementary checking, we get that is a state-homomorphism of a state-subautomaton of Bs+l onto £'*. The proof is complete. Proposition 4.7. Let A = (A, X, 8) be an (r, s)-weighted automaton (having the semiLetichevsky criterion). Every monotone automaton can be represented homomorphically by an cti-v2 +l)-product of B, -where B is a single-factor product of A. In particular, if s = r — 1, then we may assume that B is an input-subautomaton of A. Proof. Using Theorem 4.4, it is enough to prove that the two-state elevator can be represented homomorphically by a diagonal power Bs+1 such that (1) Bis input-isomorphic to an input-subautomaton of A if s = r — 1 , and (2) Bis a single factor product of A if s < r — 1 . But it is evident that every semielevator of length k > 1 can be mapped homomorphically onto the elevator. Thus, using Lemma 4.6, the proof is complete. D Next we prove the following lemma. Lemma 4.8. Let A = (A,X,8) be an (r, s)-weighted automaton (having the semiLetichevsky criterion). Then every product C x T>(Y,
First we recall that all counters have singleton input sets and thus they are autonomous automata. But then an arbitrary product of a counter and any other automaton coincides with the «o-product of the considered counter and the considered automaton. By Proposition 2.65, this single-factor product is also a monotone automaton. Thus we will assume without any restriction that C x T>(Y,
4.1. Semi-Letichevsky Criterion
117
C x T>(Y,
8e(ao, x) e A if jc e X, and 8s(a, x) e [8(a, x') \ x' e X} if a € A, jc e {;ci,..., xn}. Clearly then A is a subautomaton of B, where B is a connected automaton satisfying the semi-Letichevsky criterion. It remains to prove the existence of automata A0 ,..., As having the above properties. To this statement we shall show the existence of A\ such that the number of nontrivial cycles in AI is fewer than the number of nontrivial cycles in AQ. Applying this result inductively, we can reach that As does not contain any nontrivial cycle; i.e., it is a monotone automaton. Let a\,..., a,- and b\,..., b}; be two cycles of A with a\ —b\. Observe that in this case a* 7^ bk, 1 < k < min(z, y), would imply that, contrary to our assumptions, A satisfies Letichevsky's criterion with &(at-\, x) ^ 8(at-\, y) and 8(ai-i, xp) = 8(ai-\, yq) = a for some ai-\ € A,x,y e X,p,q € X*. We also have this consequence if a^ = bk, 1 < k < min(z, j) but i ^ j. Therefore, if two cycles have a common element, then these cycles should coincide. Let au+i,..., av be a nontrivial cycle in A. If there are a state a 6 A\{a\, ...,an] and words p, q e X* with S(a, p) € {fl«+i, ...,av] and a € {8(au+i, q),..., (av, q)}, then A satisfies Letichevsky's criterion, a contradiction.
118
Chapter 4. Without Letichevsky's Criterion
Therefore, for every a e A\{ai,..., an} and words p, q e X* with (a, p) 6 {au+\,..., av}, it holds that a £ (8(au+i,q),..., 8(av, q)}. Let a\,..., au e A denote all states for which there are words p\,..., pu € X* having 8(at, pi) 6 {««+i, • . . , av}, i = !,...,«. (We note that {a\,..., au} = 0 may be possible.) Finally, let A \ {a\,..., av} = {av+\,... ,an} for appropriate a v +1> • • • ,an £ A. (Note that {av+\,... ,an} = 0 may be possible but {«!,..., au, av+i,... ,an] ^0 because A satisfies the semi-Letichevsky criterion.) Hence, we can consider an arrangement a\,..., au, au+\,... ,av, av+\,..., an of the set of states in A = (A, X, 8) such that au+i, ...,av form a cycle of length v — u > 1; moreover, 5(a,, x) / a; for either l<j
with
Consider the counter
be an
Let
-product with
and
whenever be a mapping with otherwise. It is routine work to show that iff is a state-homomorphism of Mi onto A. Next we show the following corollary. Corollary 4.10. Given a finite set /C of automata satisfying the semi-Letichevsky criterion, let ck be the least common multiple of all positive integers which are lengths of cycles of automata in /C. Moreover, let mjc be the minimal number of cycles of automata in K. such that every prime power divisor ofcjc divides at least one of these lengths of cycles.18 Consider an (r, s)-weighted automaton A = (A, X, 8) € /C (with semi-Letichevsky criterion, s < r). If an automaton B can be represented homomorphically by a general product of automata from /C, then it can be represented homomorphically by an a i-vj-product of factors in K, with i < 1 and j < mjc + 2(5 + 1) + !. In particular, ifs = r — 1 and for every cycle of length k in B, the counter with k states, as well as the counter with r states, can be represented homomorphically by an oiQ-product of automata in 1C, then B can be also represented homomorphically by an UQ-VJ-product of factors from /C with j < m^, + 2(5 + !) + !. Proof. Suppose that B satisfies the semi-Letichevsky criterion and let r' denote the least common multiple of the lengths of all cycles in B. Then r' \ c/c- Therefore, by Lemma 4.9, B can be represented homomorphically by an oro-product of a counter with r' states and a monotone automaton M. On the other hand, by Proposition 4.7, for every (r, s)-weighted 18
Thus m/e = 0 if all cycles are trivial (having length of 1).
4.1. Semi-Letichevsky Criterion
119
automaton A e /C, M. can be represented homomorphically by an cto-V2(S+i) -power of a single-factor product A' of A, where A may be an input-subautomaton of A if s = r — 1. In addition, by our assumptions, mjc is the minimal number of cycles of automata in /C such that every prime power divisor of CK. divides at least one of these lengths of cycles. If w/c = 0, then c/c = 1, leading to r' = 1. Therefore, in this case we are ready. Consider the (r, s)-automaton A = (A, X, 5) e /C (having the semi-Letichevsky criterion) with a € A, x, y € X, p e X*, 8(a, xp) = a, 8(a, x) ^ 8(a, y), and \A'a\ = r, \A'a\ = s (such that for every q e X*, a ^ 8(a, yq)). Again, for technical reasons, we put fli = a and xp = z\ • • • zr such that zi,. •., zr e X (r > 1). Moreover, we put ai+i = 8(a, zi • • • Zi), I < i < r, and A' = {a\, ..., ar}. Let c denote the least common multiple of r and the lengths of cycles in B and define the ao-product B' = Cc x A(X, (p\, ^2) of the counter Cc = ({I, ...,c},{xc},8c) (with c states) and A such that for every x € X, V\(x} is the (only) input letter xc ofCc; moreover, for every i e (1,..., c}, x e X,
Since r |c, it is obvious that for every
if and only if t = 1 and 8(j, ^(tr + j, j, ;c)) j + l(mod r). By this observation, B' is a (c, s)-automaton with c\cjc. Suppose m/c > 0 and let AI, ..., Am, m < m/c € /C, denote automata for which c divides the least common multiple of c\,..., cm, where c, denotes the length of an appropriate cycle in A,•, i — 1,..., m. Obviously, the counter Cc with c states can be represented homomorphically by a direct product of counters with c\,...,cm states. On the other hand, for every i = 1,..., m, the counter CCi with c, number of states can be represented isomorphically by a single-factor product #, of A{. Therefore, using Proposition 2.53, an appropriate a0- vm -product of B\,..., Bm and a single-factor product A' of A (which may be an input-subautomaton of A if s = r — 1) homomorphically represents the (c, s)-automaton B' (having the semi-Letichevsky criterion). We prove that every single-factor product B" of B' can be represented homomorphically by an appropriate ciQ-vm -product ofBi,...,Bm and a single-factor product A' of A. Recall that B' is an ao-product of a counter and A. On the other hand, all counters have singleton input sets, and thus they are autonomous automata. But then an arbitrary product of a counter and any other automaton coincides with the ao-product of the considered counter and a single-factor product of the considered automaton. Therefore, B" can be represented homomorphically by an a0-product of Cc and a single-factor product A of A. Hence, we can see as before that, indeed, every single-factor product B" of B' can be represented homomorphically by an appropriate <xo-vm -product of BI , . . . , Bm and a single-factor product A of A. Applying Lemma 4.8, an «0-product T of a counter with r'\c states and a monotone automaton M. can be represented homomorphically by an «o-v>2(.y+i)+i -product B", where B" is a single-factor product of B'. As we proved before, B' can be represented homomorphically by an appropriate aQ-vm -product ofBi,...,Bm and a single-factor product A' of A. Thus, by Proposition 2.63, F can be represented homomorphically by an
120
Chapter 4. Without Letichevsky's Criterion
ofo-vm+20r+i)+i -product of automata Bi,...,Bm and A' (where B{ is a single-factor product of A, , i = 1 , . . . , m, and .A' is a single-factor product of .4). Hence, F can be represented homomorphically by an «i-v^+2(j+1)+1 -product of AI, . . . , Am and A. In addition, also by Lemma 4.8, if s — r — 1, then f can be represented homomorphically by an ao-V2(H-i)+i~ power of B' too. Therefore, applying again Proposition 2.63, if for every cycle of length k in B, the counter with k states, as well as the counter with r states, can be represented homomorphically by a single-factor ao-product of an automaton in K, (and s = r — 1), then T can be represented homomorphically by an ao-vm+2(S+i)+i -product of m factors in 1C, and A. But then we are ready because m < mjc and F homomorphically represents B. Suppose that B = (B, X&, SB) is without any Letichevsky criteria and that it can be represented homomorphically by a product of factors in /C. By Propositions 4. 1 and 2.54, we can restrict our investigations to the case when B is connected. If B is strongly connected, then it forms a cycle of length | B \ and then our statement obviously holds. Otherwise, it has a state bo e B which generates all states and, simultaneously, <$/?(£, p) ^ p holds for every p € Xg. Then B can be embedded isomorphically into the automaton B' = (B, XgUfe], 8'), where for every b e B,
Let m denote the least common multiple of all positive integers which are lengths of cycles in the automaton B. Then, by the construction ofB',m also is the least common multiple of all positive integers which are lengths of cycles in the automaton B'. By Lemma 4.9, B' can be represented homomorphically by an or0-product of a counter with m states and a monotone automaton. Because B can be represented homomorphically by a product of factors in 1C, it is easy to see that the counter of m states also has this property. On the other hand, by Lemma 4.7, every monotone automaton can be represented homomorphically by a product of factors in 1C. Thus we have that the automaton B' can be represented homomorphically by a product of factors in 1C. Observe that B' satisfies the semi-Letichevsky criterion (by Se(bo, z) = b0 and SB^Q, x'q) ^ b0, x' e XB, q e (X& U {z})*). Thus we can apply again Lemma 4.9, Lemma 4.8, and Proposition 2.63. The proof is complete. We have the following conjecture. Conjecture 4.11. Given a finite class 1C of automata, let CK denote the least common multiple of all positive integers which are lengths of cycles of automata in 1C. Moreover, let mjc be the minimal number of cycles of automata in 1C such that every prime power divisor ofcjc divides at least one of these lengths of cycles. For every nonnegative integer s, there exist an integer r > s, a finite set 1C of automata, an (r, s)-weighted automaton A e 1C (having the semi-Letichevsky criterion), and an automaton B such that B can be represented by a general product of factors from 1C but B cannot be represented homomorphically by an ai-Vj-product of factors in K ifi < 1 and j < mjc + 2(,s + 1). Problem 4.12. Prove or disprove Conjecture 4.11. The next observation gives a partial solution of Conjecture 4.11.
4.2. Without Any Letichevsky Criteria
121
Proposition 4.13. There exists an automaton A without Letichevsky criteria and a class 1C of automata having the semi-Letichevsky criterion such that A cannot be represented by an cto-product of factors from K.. Proof, Let /C be a singleton class having the automaton B = ({1, 2, *}, {*i, x2], <$) with 8(1, xi) = 2, 6(2, x2) = 1, 6(1, x2) = 8(2, jci) = 6(*, *i) = 6(*, *2) = *. Moreover, let A = ({0o, «i, a 2 }{y1, y2}, 6') be defined by 6/(o0, yi) = «i, S'(OQ, y2) = a2, 8'(ai, vi) = <$'(0i, y2} = a\, S'(a2, yi) = S'(a2, y2) = a2. Consider an arbitrary ao-power Bn(X,
4.2 Without Any Letichevsky Criteria Now we study automata satisfying neither Letichevsky's criterion nor the semi-Letichevsky criterion. The following statement is obvious. Proposition 4.16. A = (A, X, 6) is an automaton without any Letichevsky criteria if and only if for every state OQ e A, input letters x,y € X, and an input word p e X* having 5(«o, xp) = OQ, it holds that S(OQ, x) = 6(#o, )0Obviously, if A = (A, X, 5) has the above properties, then there exists a nonnegative integer n such that for every p e X* with |p| > n, each 8(a, p) (a e A) generates an autonomous state-subautomaton of A Denote by n^(< n) the minimal nonnegative integer having this property.
122
Chapter 4. Without Letichevsky's Criterion
Proposition 4.17. nA < max(|A| - 2, 0). Proof. Take out of consideration the trivial cases. Thus we may assume |A| > 2. Consider a € A, xi,..., xm+2 € X, having 8(a, xi • • • xmxm+i) ^ 8 ( a , x i - - - xmxm+2). If a, 8(a, *i), 8(a, Xix2),..., 8(a, x\ • • • xm), 8(a, xi • • • xmxm+i), 8(a, *i • • • xmxm+2) are not distinct states, then A satisfies either Letichevsky's criterion or the semi-Letichevsky criterion, a contradiction. Hence, m < \A\ — 3. Thus n^ < \A\ — 2. We also note the next direct consequence of Proposition 4.16. Proposition 4.18. If A is a strongly connected automaton without any Letichevsky criteria, then A is autonomous. By this observation, we immediately get the following. Proposition 4.19. Suppose that A= (A, X, 8) is a strongly connected automaton without any Letichevsky criteria. There exists a k > 0 such that for every a, b € A, a = b, if and only if there exists a pair p,q e X* with \p\ = |#|(modA:)19 and8(a, p) = 8(b, q). Lemma 4.20. Given an automaton A= (A, X, 8) without any Letichevsky criteria, a e A is a state of a strongly connected state-subautomaton of A if and only if there exists a nonempty word p e X* with 8(a, p) = a. Proof. Let a e A be a state of a strongly connected state-subautomaton of A. By definition, for every nonempty word q e X*, there exists a word r e X*wtih8(a,qr) = a. Conversely, suppose that 8(a, p) = a for some a e A and p € X*, p . Then for all prefixes p' of p and input letters x, y € X, 8(a, p'x) = 8(a, p'y). Therefore, for every q e X*, 8(a, q) = 5(a, r), where r is a prefix of p with \q\ = |r|(mod \p\). But then a generates a strongly connected state-subautomaton of A. We shall use the following consequence of the above statement. Proposition 4.21. Let A = (A, X, 8) be an automaton without any Letichevsky criteria. Moreover, suppose that a & A is not a state of any strongly connected statesubautomaton of'A. If'8 (b, p) = a for some b e A and nonempty p € X*, then8(a, q) ^ b, q e X*. Conversely, if 8(a,r) = c for some c e A and nonempty r e X*, then 8(c,q)^a,qeX*. d Next we prove the following proposition. Proposition 4.22. Given a class 1C of automata without any Letichevsky criteria, let A be an automaton which can be represented homomorphically by a general product of factors from JC. There exists an automaton A e /C, a q-power M of A with a single factor such that M. is an autonomous automaton; moreover, A can be represented homomorphically by a diagonal product of its connected state-subautomata and M.. 19
Recall that a = fc(modn) means n\a — b. Moreover, a
b(modn) means n/a — b.
4.2. Without Any Letichevsky Criteria
123
Proof. Consider the automaton A' — (A', X', <$')• We distinguish three cases. Case 1. There exists an A = (A, X, 5) e K, having a nontrivial cycle. In other words, there are distinct states a\,..., am e A, in > 1, and (not necessarily distinct) input letters xi,...,xm e X such that 5(a,-, jc,-) = a,+i(m0dm)- By Proposition 4.16, this implies that for every jc e X, 8(at, x) = a,+i(modm). Consider a fixed jc e X and let M = A(X,
This holds automatically if \q\ = \q'\ > \A\.
124
Chapter 4. Without Letichevsky's Criterion
Case2. Therearegi, r\, qi, TI with*? = q\r\ = qiri, \q\\ < \q2\, suchthat5(a, q\) = 8(a, q2),but5(a, q() ^ 8(a, q'2) holds for all distinct prefixes , of -Theseassumptions imply (\q\ =) \q'\ < \A\ — 1. On the other hand, \q\ = \q'\ > \A\ — 1 is supposed. Hence, we necessarily have \q\ = \q'\ = \A\ — 1. Thus we get 8(a, q() ^ 8(a, q2) for all distinct prefixes q{, q'2 o f q ' , where \q'\ = |A| — 1. This implies that for every d e A there exists a prefix q[ ofq' with 8(a, q() = d. Then for every d e A there exists an r( e X* having 8(d, r ) = 8(a, q'). On the other hand, we may assume 8(a, qrzr\) = 8(a, q) as in the previous case. Now we suppose 8(a,qr) = 8(a,q'rf) as before. Substituting d for 8(a,q) (= 8(a, qrzri)), there exists an r[ 6 X* holding 8(a, qr() = 8(a, q'). Put b = 8(a, qr)x (= 8(a,q'r'),c = 8(a,q),c' = 8(a,q'). Hence 8(b, zn) = c,8(b, zrir{) = c' and 8(c, r) — 8(c', r') = b (with c c'}. Therefore, by Proposition 2.70 we obtain again that A satisfies Letichevsky's criterion contrary to our assumptions. Case 3. Let 8(a, q\) / 8(a, q2) and 8(a, q{) ^ 8(a, q^) for all distinct prefixes q\, qi of q and q{,q'2 of q', respectively. Then|^| = \q'\ < \ A|-l. Recall that \q\ = \q'\ > \A\-l is also assumed. Thus \q\ = \q'\ = \A\ — 1, which implies that for every d € A there are ri,r{ € X* satisfying 8(d, n) = 8(a,q) and 8(d,r{) = 8 ( a , q f ) . Therefore, assuming 8(a, qr) = 8(a, q'r') for some r, r' 6 X*, and substituting d for 8(a, qr)(= 8(a, q'r')), we obtain 8(a, qrn) = 8(a, q}, 8(a, qrr{} = 5(a, q'} (with 5(a, qr) = 8(a, q'r')). Put c = 8(a, q), c' = 8(a, q'). Then 8(d, n) = c, 8(d, r() = c', 8(c, r) = 8(c', r') = d (with c £ c'). By Proposition 2.70, this implies that A satisfies Letichevsky's criterion, a contradiction again. Lemma 4.24. Let A = (A, X, 8) be an automaton without any Letichevsky criteria. For every state a € Awe have one of the following two possibilities: (1) There existq, q' € X*, \q\ = \q'\ > |A| - 1, suchthat8(a, qr) ^ 8(a, q'r') for every r,r' £X*, |r| = |r'|. (2) 8(a,q) = 8(a,q') for every q,qf € X*, \q\ = \q'\ > |A| - 1. Proof. Suppose that (1) does not hold. Then for every q, q' e X*, \q\ = \q'\ > |A| —1, there exist r, r' e X*, \r\ = \r'\, having 8(a, qr) = 8(a, q'r'). Using Lemma 4.23, 8(a, qr) = 8(a, q'r'), \r\ = |r'|, and \q\ = \q'\ > \A\ - 1 implies 8(a, q) = 8(a, q'). Thus (2) holds whenever (1) does not hold. The following statement is obvious. Lemma 4.25. Given a digraph V = (V, E), let v € V, pi, P2, p'2, Pi, P4 e V* such that PIP2P3VP4V and pip'2p3vp4v are walks and vp4V is a cycle. \p2\ = \p'2\(mod\p4V\)ifand only if there are positive integers k, I having \p\pip'3v(p4v)k\ = Ipip^Psv^tv)*]. Lemma 4.26. Let A = (A,X,8) be an automaton without any Letichevsky criteria. Consider a state a € A and suppose that there are q,q' € X*, \q\ = \q'\ |A| — 1, 8(a,q) 8(a,q'). Then there are q,q' (with \q\ = \q'\ \A\ - I) such that for an appropriate triplet u,v,v' € X*, q = uv and q' = uv', for which we have the following
4.2. Without Any Letichevsky Criteria
125
properties: (1) For every prefixes z ofv and z' ofv' with \z\ = \z'\ > 0, 8(a, uz) i=- 8(a, uz'). (2) For every prefixes wx ofz and w'x' ofz' with ww' A and x, x' € X, S(a, uw) = 8(a, uw') implies x = x'. (3) For every words r, r' e X* with \r\ = \r'\, 8(a, uvr) ^ 8(a, uv'r'). Proof. Consider a e A and suppose that our conditions hold; i.e., there are q, q' e X* having \q\ = \q'\ > \A\-l, 8(a,q) ^ 8 (a, q'). In this case, by Lemma 4.24,8 (a, qr) 8(a,q'r') holds for every r, r' e X* with |r| = |r'| > 0. Thus, it is enough to prove that we have properties (1) and (2). Then Proposition 4.17 implies that 8(a,q) and 8(a,q') generate autonomous state-subautomata of A. We will distinguish the following cases (omitting some of the analogous ones). Case 1. There are u, u', v, v', e X* such that q = uv, q' = u'v', 8(a, u) = 8(a, u') and for every nonempty prefixes r of v and r' of v', 8 (a, u)(= 8 (a, u')) (a , ') 8 (a, u') (= 8(a, u)) 96 8(a, ur), and 8(a, ur) ^ 8(a, u'r').21 Let, say, \u\ > \u'\ and let v" be a prefix of v' with \v"\ = \v\. Submit q' with uv" and then we will have our requirements. Case 2. There exists a prefix u of q having <5(a, u) = <5(a, q'). We shall use the fact that, in this case, v ^ X for v e X* with q = uv because of 8(a, q) ^ 8(a, q'). Let t2 e X* be a nonempty word with minimal length having 8(a, q't\t2) = 8(a, q't\) for some word t\ e X* and assume that ?2 is minimal in the sense that for every nonempty p € X*, 8(a, q't\p) = 8(a, q't\) implies \t2\ < \p\-22 Then, using that 8(a, qf) generates an autonomous state-subautomaton of A, we have q = uv, where u is a nonempty prefix of t\t\ for a suitable k > 0. To prove that in this case \u\ = j^r'Kmod |?2l) is impossible, assume the contrary. Recall again that 8(a,q') generates an autonomous state-subautomaton of A. But then, applying Lemma 4.25, there are words r, r' e X*, \r\ = \r'\, having 8(a, qr) = 8(a, q'r'). By Lemma 4.23, then |q| = |q'|<|A| — 1, contrary to our assumptions. Thus we have the following cases. Case 2.1. Suppose \u\ | |(mod |r2|) such that for all prefixes u\ of u and u ( of q' with uiu( i=. A, 8(a, u\) = 8(a, u() implies u\ — u and u\ = q'. Then we obtain our requirement again (having q = uv, where v is a nonempty prefix of t\t\ for a suitable k>0). Case 2.2. Assume \u\ ^ | |(mod lt 2 l) and, simultaneously, let, for some prefixes u\ of u and u\ of q', 8(a, MI) = 8(a, u\) such that u = u\v\, q' = u\v(\ furthermore, neither m = u\ = X nor v\ = v( = .23 If vi = X and v( X, then 8(a, u\} = 8(a, u'^) ^ 8(a, u'1v'lv)(= 8(a,uv)). Recall that u is a nonempty suffix of q. But then A has either Letichevsky's criterion or the semi-Letichevsky criterion, a contradiction. Similarly, it also leads to a contradiction if we assume v\ ^ A and v1 . Thus X ^ [vi, v(} can be assumed and we may also assume k$.{u\,u\] analogously. 21
H = u' = X is possible. The finiteness of the state set of A implies the existence of t\ and t223 If MI = u j = A. or v\ = i/j = A., then we may get either the previous case or this case considering appropriate M I , U ] , vi, Vj withuiu'j ^A-anduii/j 7^ A.. 22
126
Chapter 4. Without Letichevsky's Criterion
By \i<\ |0'|(mod|r2|), either | Ul | & K|(mod|f 2 |) or |vi| & K|(mod|f 2 |). Case 2.2.1. Suppose \u\\ ^ |ui|(mod |f2|) and let, say, |ui| < \v{\. Take a prefix vf of t\t2 for a suitable k > 0 with = \q\ and let us consider u\v\v' instead of q'. Case 2.2.2. Suppose |ui| = |u'p!(mod|f2|). Then |ui| |i/p!(mod|f2|). Let, say, l"i I < |M'I I- Take a prefix v' of fif| for a suitable k > 0 with (MI^I/! = \q\ and submit q' with «i i>i i/. In both Case 2.2.1 and Case 2.2.2, we have words24 it;, w\, W2, u/p w'2 e X*, A. ^ {w\,w'l}, \w\\ =£ lu/jKmodl l), w'2 is a prefix of wi (or, in the opposite case, W2 is a prefix of w'2), q = ww\W2,q' = ww^w^, such that S(a, ww\) = 8(a, ww'j), and 8(a, ww\) (= S(a, ww\}) generates an autonomous state-subautomaton of A. Then let iu, w\, W2, w , w'2 X* be arbitrary strings with these properties for which min(|w1 |, \w( |) is minimal. Suppose that for every nonempty proper prefixes z\ of w\ and z\ of w( we have 8(a, w) £ [8(a, wz\), 8(a, wz\)} and 8(a, wz\) •£ 8(a, wz[). Moreover, recall that 8(a, w) ^ 8(a, ww\)(= 8(a, ww{)) because 8(a, ww\)(= 8(a, ww()) generates an autonomous state-subautomaton of A. By these conditions, we are done, since we have our properties for q = ww\W2, q' = ww'^w^. Now we assume \w\ \ \w( |(mod j^l) such that for some prefixes z\ of w\ and z\ of w{, 8(a, z\) = 8(a, z( ) such that w\ = ziZ2, w{ = z\z'2\ furthermore, neither z\ = z\ = A. nor Z2 = z'2 — ..25 We can prove A {z\, z(, Z2, z'2] in a way similar to the proof of X i {u1, u'p vi,v{} in Case 2.2. Then either |zi| |zil(mod |r2|) or |z2| |z2|(mod |t2|). It remains to prove that these cases are impossible. If |z1| |zil(mod|f2l) and, say, \Z2\ > \Z2\, then considering the prefix w'2 of w'2 having \Z2W2\ = \z2w2\, we can submit w, w\, W2, w{, w'2 with w, z1, z2w2, z{, Z2W2, contrary to the the minimality of min(| w\ \, \ w{ \). If Izil = kil(mod |r2|) with |z2| |z2|(mod |t2|) and, say, |z1| > |z'|, then considering the prefix w'2 of w'2 having \z\w'2\ = | | , we can submit w, w\, w(, W2, w'2 with , Z2, w>2, u>2, contradicting the minimality of min(|w\|, \w( |). The proof is complete. We shall use the following definition. Let A = (A, X, 5) be an automaton. For every pair a, b € A, consider a fixed xa,b e X with 5(a, xa,b) = b if it exists and put pa(x) = xa,b if 8(a, x) = b. Moreover, put pa( ) = . and pa(x\ • • •xn) = pa(x\)pB(a,Xl)(x2} • - • Ps(a,xr-xn-i)(xn)- Clearly, then (a, w) = 8(a, pa(w)) holds for every w X*. Lemma 4.27. Let A= (A, X, 8) be an automaton without any Letichevsky criteria. Consider a, a, A, p e X* with S(a0, p) = a. If there are q,q' e X*, \pq\ = \pq'\ > |A| — 1, (a, q) 8(a, q'), then there are an input letter x e X, a word u € X*, and single-factor products B = (A, X, SB), C = (A, X, 8c) of A such that for every z, z' e X* with \z\ < |z'| < \pu\ + 1 we obtain ( (a0, z), 8c(ao, z)) ( (00, z'), 8c(aQ, z')); moreover, {(8B(ao,z),8c(ao, z))\z X*,\z\ < \pu\},{(8B(ao,z),8c(ao,z))\z = Zixz2,z\, Z2 € X*, |zi| = \pu\] and {(8B(ao, z), 8c(a0, z))\z = Zix'z2, x' eX,x' x, zi,z2e X*, \Z1\ = \pu\\ arepairwise disjoint sets. 24
In Case 2.2.1, of course, w = l,. If zi = zi = A. or Z2 = z — . then we may get either the previously discussed case or this case considering appropriate z\, z ,Z2,z'2 with z\z\ . and z2z2 •• 25
4.2. Without Any Letichevsky Criteria
127
Proof. Let A = (A, X, 5) be an automaton without any Letichevsky criteria. Consider a,OQ e A, p € X* with <5(a0, p) = a. If there are q,q' € X*, |p#| = \pq'\ > \A\ 1, S(a, q) ^ 8(a, q'), then we may assume q = uv and ' = uv' for some M, v, u' e X* such that (1 )-(3) of Lemma 4.26 hold. Put u = x\z, v' = x2z' with x\,X2 e X,z,z' e X*, |z| = |z'|. Thus for every prefix wx of z and u/*' of z' with ww' ^ A and x, x' e X, jc = x' whenever 8(a, ux\w) = 8 (a, ux2w'~). Therefore, without any contradiction, we can define the functions
By Proposition 4.16, for every prefix p' of /?M, 8 (ao, p') £ [8(ao, pux\r), 8(ao, pux2r) | r e X*}. (We note that S(a0, p') 8(ao, p") also holds for every pair of distinct prefixes p', p" of pu.) On the other hand, by our assumptions and Lemma 4.23, for every r, r' e X*, \r\ = \r'\, it holds that S(ao, pux\zr} S(a0, pux2z'r'). Therefore, S(a0, pux\zr') ^ 8(ao, pux2z'r'). But then (8(a0, pux\zr), 8(ao, pux\zr)) (8(ao, pux\zr'), 8(ao, pux2Zfr')) is valid for every r, r' e X*. In addition, by property (1) of Lemma 4.26, for every prefix w of z and it/ of z' with |u;| = |u/|, ( (ao> pux\w), S( , pux\wj) (S(OQ, puxiw), 8(ao, pux2U>')). Therefore the single-factor products B = A(X, (p) and C = A(X,
128
Chapter 4. Without Letichevsky's Criterion
Now let q = uv, q' = u'v' such that MM' ^ X and<5(a, M) = 8(a, u'). Suppose that \u\ and |M'| are minimal in the sense that for every prefixes u" of M and u'" of u' with u"u"' ^ X and 8(a, u") = 8(a, u'"), we have {u", u'"} - {M, u'}. Assume that, say, M = A.. This implies 8(a, u') = a with u' /: X. But then, by Proposition 4.16, a generates an autonomous state-subautomaton of A. Therefore, 8(a,q) = 8(a,q'), a contradiction. Now let X £ {u, u'}. Clearly, v = v' = X is impossible because 8(a, q) ^ 8(a, q'}. Let, say, v = X. Then, by the minimality of M and u', we have (1) and (2) again. Next we assume X ^ {M, M', u, t/}. If |M| = |M'|, then we can consider, say, uv' instead of u'v'. Therefore, \u\ ^ \u'\ can be supposed. Assume that, say, |M| > \u'\. Then submit v with v", where v" is a subword of v' with \v"\ = \v\. Because of the minimality of \u\ and \u'\ for every subword w of M and w' of M' with |iy|, \w'\ > 0, we obtain that 8(a, iu) = 8(a, w') implies w = u and w' = u'. Submitting q, q', u, u', v, v' with uv", q', u, u', v", v' we get (1) and (2). Now we prove (3), omitting some analogous cases. If there are no distinct prefixes p(, p'2 € X* of pq' with 8(dQ, p() = 8(aQ, p'2), then change pq for pq' and pq' for pq. Therefore, in this case, we are ready. Otherwise, we may suppose (ao, p = 8(ao, p'2) for some distinct prefixes p{, p'2 e X* of pq'. Let, say, p( = p'2r' for some nonempty r' e X. By Proposition 4.16 and 8(ao, p'2) = 8(ao, p'2r'), this implies that 8(ciQ, p'2) generates an autonomous state-subautomaton B of A. Moreover, 8(GO, P'\) = 8(ay, p'2r') = S(CIQ, p'2), r' 7^ X implies that this autonomous state-subautomaton is strongly connected. Recall that bythemaximalityof \q\(= \q'\), 8(ao, pqx) — S(«o, pq'x') holds for every x, x' € X.Thus, 8(ao, pqx) is also a state of the state-subautomaton B of A. Then <$(a0, pq) ^ 8(a0, pq') and 8(ao, pqx) = 8(ao, pq'x') imply that 8(ciQ, pq) is not a state of B. Indeed, if 8(ao, pq) and 8(ao, pqx) are states of B with 8(ao, pq) ^ 8(ao, pq') (and \pq\ = \pq'\), then B cannot be autonomous, i.e., by Proposition 4.18, it is not strongly connected, a contradiction. Therefore, for every prefix p\ of pq, S(CIQ, p\) is not a state of B. Suppose that, contrary to our assumptions, S(OQ, p\) — S( , p2) holds for distinct prefixes p\ and p2 of pq and put, say, p\ = pir\ (where r1 X is assumed). In other words, <5(flo, P2r\) = 8(ao, p2) holds such that 8 (a0, pi) is not a state of B. But 8 (a0, pqx) = S(0o, Pq'x'), x, x' € X, implies that there exists an r2 € X* such that 8(ao, p^ri) isastateof B. Clearly, then A satisfies either Letichevsky's criterion or the semi-Letichevsky criterion, a contradiction. Finally, (4) is a direct consequence of the maximality of |#|(= \q'\). This completes the proof. Lemma 4.29. Let A = (A, X, 8) be an automaton without any Letichevsky criteria. Consider a pair a,ao e A of states and a word p e X* with 8(ao, p) = a and suppose that 8(a, r) = 8(a,r') holds for every r, r' e X*,\pr\ = \pr'\ > \A\ - I. Assume that8(a,q) / 8(a,q') holds for some q, q' e X*,\pq\ = \pq'\ < \A\ - 1 and let q,q' be words of maximal length having this property. Then there exist an input letter x, words u, v, v', w € X*, q = uv,q' = uv', v = xw such that for every nonnegative integer i < \pu\, there are <XQ — v\-powers B = (B, X, SB), C = (C, X, 8c) of A having states bo e B,CQ € C such that for every z, z' € X* with 0 < |z| < k'l < \P4\ ~i we have (8B(bo,z),8c(co,z)) ^ (8B(bo,z'),8c(co,z')), and, moreover
4.2. Without Any Letichevsky Criteria
129
{(&B(bo, z), &C(CQ, z))|z € X*, |z| < i}, {(SB(fco, z), <$c(c0, z))|z = Zi*z2, |zi| = i, |z2| < l M | - l } f l l W / { ( B(b0,z),«c(Co,z))|z € X * , Z = Z l J C ; Z 2 , | Z l | = I, *' € X,x' ^X,\Z2\
\pq\ —i} arepairwise disjoint sets.
<
Proof. Assume that our conditions hold. Then there are q,qf, u, v, v' e X*with# = uv, q' = uv' (having \q\ = \q'\ < \A\ — 1) such that we have properties (l)-(4) of Lemma 4.28. Consider yi,..., y\pq\, y( pu | +1 ,..., y'\pq\ e X such that, in order, p = yl-> y\p\, u = y\P\+i • - • y\Pu\, v = V|pu|+i • - • y[pq\, v' = y'lpu\+l • • • y[pqV Moreover, consider words pk, vt, v't e X*, where, in order, pk is a prefix of pu of length k, 0 < k < \pu\, vt is a prefix of v of length £, and vft is a prefix of v' of length t, 0 < t < \v\(= \v'\). Finally, let y' e X be an arbitrary fixed-input letter. By our assumptions, without any contradiction, we can define the functions