Permutation Automata by G. THIERRIN D6partement d'Informatique Universit6 de Montr6al

1. Introduction An a u t o m a t o n ([2], [4]) is a q u i n t u p l e . 4 = (S, I, 8, so, F), where (i) S is a finite n o n e m p t y set o f states; (ii) I is a finite n o n e m p t y set o f inputs; (iii) 8: S × I ~ S is called the transition function; (iv) so is an e l e m e n t o f S (the initial state o f A); (v) F is a subset o f S (the set o f final states o f A). Let I* be the set o f all finite sequences o f elements o f I, including the null sequence A. Any e l e m e n t o f I* is called a tape. With the operation o f concatenation, the set I* becomes a semigroup, which is called the free s e m i g r o u p (with identity A ) g e n e r a t e d by I. T h e transition function 8 can be e x t e n d e d by recursion to S × I*. T h e set T(A) = {x] x e I* a n d 8(s0, x) e F} is called the set o f tapes acc e p t e d by the a u t o m a t o n .4. A subset o f U o f I* is said to be a regular set if and only if t h e r e exists some a u t o m a t o n A such that U - T(A). An a u t o m a t o n .4 is said to be a p e r m u t a t i o n automaton, or simply a p - a u t o m a t o n , if and only if each input p e r m u t e s the set o f states. A subset U o f I* is said to be a p - r e g u l a r set if and only if there exists a p - a u t o m a t o n A such that U = T(.4). It is the p u r p o s e o f this p a p e r to give some characterizations o f p - r e g u l a r sets and to d e t e r m i n e some operations u n d e r which the family o f p - r e g u l a r sets is closed.

2. p-Automata and p-Regular Sets Definition 2.1. An a u t o m a t o n A = (S, I, 8, So, F) is said to be a p e r m u t a tion a u t o m a t o n , or m o r e simply a p - a u t o m a t o n , if and only if ~(si, a) = ~(sj, a), where si, sj e S, a e I, implies that si -- sj. It is obvious that the following t h r e e conditions are equivalent: (i) .4 is a p - a u t o m a t o n ; (ii) 8(si, x) = 8(sj, x), where x e I*, implies that si = sj; (iii) For every x ~ I*, we have 8(S, x) ----S. 83 MATHEMATICAL SYSTEMS THEORY, VoL 9 No. l Published by S p r i n g e r - V e r l a g N e w York Inc.

84

G. THIERRIN

D e f i n i t i o n 2.2 A n e q u i v a l e n c e relation R o n I* is said to be right cancellative [left cancellative] if a n d o n l y if ac =- bc (R) [ca ==-cb (R)] i m p l i e s that a =- b (R). I f R is right a n d left cancellative, t h e n R is said to be a cancellative e q u i v a l e n c e relation. D e f i n i t i o n 2.3. Let U be a subset o f / * . W e define: (i) F o r e v e r y a ~ I* U " a={x[xeI*andax~ U ". a = {x[ x e I *

U},

a n d xa e U};

(ii) a - b ( R v ) i f a n d o n l y i f U " a = U " b, a - b (vR) if a n d only if U " a = U " b. It is easy to see that R v is a right c o n g r u e n c e a n d t h a t vR is a left cong r u e n c e . T h e s e c o n g r u e n c e s have b e e n u s e d to c h a r a c t e r i z e the r e g u l a r sets ([2], [4]). T h e y w e r e first discussed in the g e n e r a l t h e o r y o f semig r o u p s by D u b r e i l ([ 1 ]). L E M M A 2.1. Let R be a right congruence of finite index on I* and let C be a right congruence on I* such that R C_ C. I f R is right canceUative, then C is also right cancellative. Proof Let T be a right c o n g r u e n c e o n I*. F o r e v e r y c e I*, let T(c) = {y] y • I* a n d t h e r e exists x e I* such t h a t y -- xc (T)}. I f T is right cancellative a n d if a g ¢ b (T), t h e n ac ~- bc (T) f o r e v e r y c • I*. T h e r e f o r e , a right c o n g r u e n c e T o f finite i n d e x is right cancellative if a n d o n l y if T(c) = I* f o r e v e r y c • I*. Since R is right cancellative, we have R(c) = I* f o r e v e r y c • I*. F r o m R C_ C, it follows that R(c) C_ C(c) a n d C(c) = I*. T h e r e f o r e C is right cancellative. T H E O R E M 2.1. Let U be a subset of I*. Then the foUowing three conditions are equivalent." (i) U is a p-regular set; (ii) U is the union of some classes of a right congruence on I* of finite index, which is right cancellative. (iii) The right congruence R e on I* is right canceUative and of finite index. Proof. (i) implies (ii). T h e r e exists a p - a u t o m a t o n A = (S, I, 8, So, F ) such that U = T ( A ) . Let R be the e q u i v a l e n c e relation d e f i n e d o n / * by: a --- b (R) if a n d o n l y if 8(s0, a) = 8(s0, b). It is k n o w n ( [ 2 ] , [4]) that U is the u n i o n o f s o m e classes o f R. Let us show that R is right cancellative. I f ac =- bc (R), t h e n 8(So, ac) = 8(So, bc) a n d 8(8(s0, a), c) = ~(8(s0, b), c). Since A is a p - a u t o m aton, we have 8(s0, a) = ~(s0, b) a n d a -- b (R). (ii) implies (iii). Let a ~- b (R). I f x ~ U ." a, t h e n a x e U. B u t a x -= bx (R). H e n c e b x e U a n d U • a C_ U " b. Similarly, U." b _C U." a. T h e r e f o r e U ." a---U • b, a = b (Ru) a n d R C R v . Since R is right cancellative a n d o f finite index, it follows ( L e m m a 2.1) t h a t Rv is r i g h t cancellative a n d o f finite index. (iii) implies (i). Let S = { [x] ] x e I* } be the set o f classes o f Rv. By h y p o t h esis, S is finite. Lets0 = [A] a n d F = {[x]l x e U}. D e f i n e 8(Ix], a ) = [xa].

Permutation Automata

85

It is k n o w n ( [ 2 ] , [ 4 ] ) t h a t A = (S, I, 6, So, F ) is a n a u t o m a t o n s u c h t h a t U = T(A). L e t us p r o v e t h a t A is a p - a u t o m a t o n . I f 8([x], a) = 8 ( [ y ] , a), t h e n

[xa]

=

[ya]

xa =--ya (Ru) x - - y (Ru). H e n c e Ix] = [y]. C O R O L L A R Y . A regular set U is p-regular if and only i f U " ac = U ." bc implies that U ." a = U " b. T h e n e x t r e s u l t is a g e n e r a l i s a t i o n o f p a r t (ii) o,f t h e p r e c e d i n g t h e o r e m . T H E O R E M 2.2. A subset U of I* is p-regular if and only if U is the union of some classes of an equivalence relation R of finite index on I*, which is right cancellative. Proof. F r o m the p r e v i o u s t h e o r e m , we see t h a t t h e c o n d i t i o n is necessary. I n o r d e r to s h o w t h a t it is sufficient, we h a v e only to p r o v e t h a t R is a r i g h t c o n g r u e n c e . S u p p o s e t h a t R is n o t a r i g h t c o n g r u e n c e . T h e n t h e r e exist a, b, c ~ I * such t h a t a =- b (R) a n d ac • bc (R). L e t C = {Cl, c2," • ", cn} be a s u b s e t o f I * s u c h t h a t (i) b = Cl; (ii) ,cim cs (R) f o r i ~ j ; (iii) F o r e v e r y x ~ I*, t h e r e exists c, ~ C such t h a t x -= ci (R). S i n c e R is o f finite i n d e x , t h e set C is finite, a n d t h e n u m b e r n o f elem e n t s o f C is e q u a l to the i n d e x o f R. Since R is r i g h t canceUative, we h a v e

qc ~ c f (R) f o r i ~ j, a n d e a c h class o f R c o n t a i n s an e l e m e n t o f t h e f o r m qc. T h e r e f o r e t h e r e exists ci a C s u c h t h a t qc ~ ac (R). H e n c e ci -=- a (R). Since a = b (R), we h a v e b ~ ci (R) a n d ci = cl = b. T h e r e f o r e bc = ac (R), a n d w e h a v e a c o n t r a d i c t i o n . Definition

2.4. L e t R b e a n e q u i v a l e n c e r e l a t i o n o n I * a n d let t ~ I*.

We define a = b (R • t) if a n d only i f t a =- tb (R). It is o b v i o u s t h a t R ." t is a n e q u i v a l e n c e relation. 1 7 I ' I E O R E M 2.3. Let R tle a right congruence on I*. Then I'i) R • t is a right congruence. (iii) I f R is of finite index n, then R • t is also of finite index m and m <~ n. Furt~hermore,

C=AR.'t tel*

is a congruence on I* of finite index and C C R. (iii) I f R is right cancellative, then R ." t is also right cancellative. P r o o f (i). L e t a --- b (R ." t). T h e n ta =- tb (R), a n d , since R is a r i g h t c o n -

86

G. THmRmN

g r u e n c e , tax =-- tbx (R) f o r all x • I*. H e n c e ax - bx ~R .~ D. (ii) Since R is o f finite i n d e x n, t h e r e exists a finite s¢~d = { a l , ~t2, • • • , a n } o f / * suc h t h a t (1) ai • aj ( R ) f o r i ~ j ; (2) f o r e v e r y c F I*, t h e r e exists a i • A such t h a t at = c (R). L e t [tt*] = {x[ x • I * a n d t h e r e exists r • I * such t h a t tr ~ x (R)}. T h e s u b s e t B = A . : N [tt*] is n o n e m p t y . L e t B = {bl, b2, " " ' , bk}. Since B _C A, we h a v e k ~< n. ' F o r e a c h bi • B, we c a n c h o o s e a n e l e m e n t ri • I * such th/tt tri =- bi (R). L e t T = {rl, r2, • • • , rk}. F o r e v e r y y • I*, t h e r e exists aj • A such t h a t ty = aj (R). Since B = A A [tI*], t h e r e exist b~• B a n d r~ • T s u c h t h a t aj = b~ a n d tri ~ b~ (R). T h e r e f o r e ty =- tri (JR) a n d y = r~ (R • t). T h i s p~-oves t h a t m <~ k ~< n, w h e r e m is the i n d e x o f R ' t. It is ~)bvious t h a t C is a r i g h t c o n g r u e n c e . L e t us p r o v e t h a t C is a c o n g r u e n c e " a n d t h a t C C R. L e t a = b (C). T h e n f o r e v e r y t e I*, we h a v e a b (R . " t ) a n d ta = tb (R). I f we t a k e t = A (the i d e n t i t y e l e m e n t o f / * ) , t h e n a - b ( ~ ) ~ ' H e n c e C C R. L e t x e ' I * . T h e n , f o r e v e r y t • I*, txa

txb (R ),

xa =--xb (R ." t).

H e n c e xa - xb (C) a n d C is a c o n g r u e n c e . It'~remains to p r 0 v e t h a t C is o f finite index. L e t D = f"l R ." a~. Since A '

ate A

is finite a n d since R ." a, is o f finite index, D is o f finite i n d e x a n d C C_ D. L e t a'---:b (D)! I f t e I*, t h e n t h e r e exists ai • A such t h a t t ~ a, (R). S i n c e R is a r i g h t c o n g r u e n c e , we h a v e ta =- afa (R) a n d tb - a~b (R). B u t a =- b ( R ." a,) and: aia =- aib (R). T h e r e f o r e ta =- tb (R) a n d a - b (R ." t). Since this is t r u e for' e v e r y t, we h a v e a - b (C) a n d D C_ C. H e n c e C = D a n d C is of" finite index. (iii) L e t ac =- bc (R ." t). T h e n tac =- tbc (R), ta =-- tb (R), a -='b (R " t).

H e n c e R ." t is r i g h t cancellative. T H E O R E M 2.4. Let U be a subset o f I*. T h e n the f o l l o w i n g three condi.tions are equivalent. (i) U is a p-regular set. (ii) U is the union o f some classes of a canceUative congruence o f finite i'ndex on I*. (iii) U is the union o f some classes of a congruence C on I* such that the quotient semigroup I * / C is a finite group. P r o o f (i) i m p l i e s (ii). T h e subset U is the u n i o n o f s o m e classes o f a r i g h t c o n g r u e n c e R o f finite i n d e x , w h i c h i s : r i g h t cancellative ( T h e o r e m 2.1). L e t C = tg* R ." t. F r o m T h e o r e m 2.~3, it follows t h a t C is a c o n g r u e n c e o f

Permutation Automata

87

finite index such that C C_ R. H e n c e U is the u n i o n o f some classes o f C. Since R is right cancellative, T h e o r e m 2.3 shows that R " t is right cancellative for every t e I*. T h e r e f o r e C is right cancellative. Let T = I*/C be the quotient semigrot~p m o d u l o C. T h e s e m i g r o u p T is a finite and right cancellative semigrou p with an identity element. It is well k n o w n that such a s e m i g r o u p is a g r o u p . Since a g r o u p is right and left cancellative, it follows that C is a cancellative c o n g r u e n c e o f finite index. (ii) implies (iii). This follows immediately f r o m the previous results. (iii) implies (i). Obvious. C O R O L L A R Y 1. I f U is a p-regular set, then U " a and U " a are nonempty sets f o r every a ~ I*.

C O R O L L A R Y 2. A nonempty finite subset of I* cannot be a p-regular set. Definition 2.5. An equivalence relation R on I* is said to be right limitative ([5])~if and only i f a c =- bc =- a (R) implies that a ~- b (R). Every right cancellative equivalence relation is obviously right limitative. T H E O R E M 2.5. A subset U o f I* is p-regular i f and only if U is the union of some ciasses o f a right congruence R of finite index on I*, which is right limitative. Proof T h e condition is necessary by T h e o r e m 2.1. Let us show that it is also sufficient. Let C = A R ." t. We know ( T h e o r e m 2.3) that C is a contel*

g r u e n c e o f finite index and that C C_ R. H e n c e U is the u n i o n o f some classes'of C. I f ac -~ bc =- a (R ." t), t h e n tac =- tbc =- ta (R) ta =- tb (R)

a=

b ( R . " t).

H e n c e R ." t is right limitative for every t~ I*. It is immediate that the intersection o f right limitative equivalence relations is also right limitative. T h e r e f o r e C is right limitative. T h e quotient s e m i g r o u p T = I*/C is a finite s e m i g r o u p with an identity e l e m e n t 1 such that ac = bc = a, where a, b, ce T, implies that a = b. Let us show that T is a group. Let e be an i d e m p o t e n t e l e m e n t o f T. We have (1 - e ) - e =

1 • e=(1

-e)

H e n c e 1 • e = 1 and e = 1. Since T is finite, then, for every a e T, there exists a positive integer n such that a" = e, where e is an i d e m p o t e n t eiement. But e = 1. T h e r e f o r e , for every a~ T, there exists x~ T such t h a t ' a x = 1 and T is a g r o u p . F r o m T h e o r e m 2.4, it follows that U is p-regular.

88

G. THIERRIN

3. Equivalence of p-Automata We recall the following result. T H E O R E M 3.1. (Hartmanis-Stearns [3]). Every p-automaton A is equivalent to a strongly connected p-automaton B. Proof Let U = T(A). T h e n U is a p-regular set and U is the u n i o n o f some classes o f a c o n g r u e n c e C such that I*/C is a finite gToup ( T h e o r e m 2.4). Let S = { [al], • • • , [a~] } be the set o f classes o f C, where [al] is the class containing A, and let F be the set o f classes o f C containing the elements o f U. For every a ~ I, define 6([ai], a) = [a~a]. T h e n B =(S, I, 6, [all, F ) becomes an a u t o m a t o n such that U = T(B). H e n c e A is equivalent to B. Since I*/C is a g r o u p , B is a p - a u t o m a t o n and, for every pair [ai], [aj], there exists [a~.] such that [ai] [ak] = [aj]. T h e r e f o r e 6([ai], ak) = [aj] and B is strongly connected. T H E O R E M 3.2. Every automaton A :- (S, I, 6, so, F) such that 8(si, a) = 8(sj, a) = sl, where a e I*, implies that si = sj is equivalent to a strongly connected p-automaton. Proof. We have only to prove that U = T(A) is a p-regular set. Define a =- b (R) if and only if 8(s0, a) = ~(s0, b). T h e n R is a right c o n g r u e n c e o f finite index and U is the union o f some classes o f R. Let ac =- bc =- a (R). T h e n 8(So, ac) = 8(So, bc) = 8(So, a)

~(8(s0, a), c) : 6(8(s0, b), c) :- 8(s0, a). H e n c e 6(s0, a) = 6(So, b) and a -= b (R). T h e r e f o r e R is right limitative and U is p-regular ( T h e o r e m 2.5).

4. Operations on p-Regular Sets T H E O R E M 4.1. The family of p-regular sets of I* is a Boolean algebra of sets. Proof I f U is p-regular, then the right c o n g r u e n c e Ru is right cancellatire ( T h e o r e m 2.1). I f U is the c o m p l e m e n t o f U, we have Ru = R~. T h e r e fore, U is also p-regular ( T h e o r e m 2.1). Let U1 and U2 be two p-regular sets. T h e n U1 and Us are respectively the union o f some classes o f right congruences Rt and R2 o f finite index which are right cancellative ( T h e o r e m 2.1). T h e intersection R = R1 A R~ is a right c o n g r u e n c e o f finite index and R is also right cancellative. It is obvious that U1 V~ U2 is the union o f some classes o f R. T h e r e f o r e U~ A U2 is a p-regular set.

T H E O R E M 4.2. I f U is a p-regular set of I*, then the transpose U r o f U is also a p-regular set. Proof Recall that i f a = a~a2 • • • ak is an e l e m e n t o f / * , where al, as, • • • , an e I, then the transpose a r o f a is the e l e m e n t a r = an " " " a2a~.

Permutation Automata

89

T h e set U is the u n i o n o f s o m e classes o f a cancellative c o n g r u e n c e C o f finite i n d e x o n I * ( T h e o r e m 2.4). Define a -= b (C T) if a n d only if a r - br (C). W e see easily t h a t C r is a cancellative c o n g r u e n c e o f finite i n d e x on I* a n d t h a t U T = {xrl x e U} is the u n i o n o f s o m e classes o f C r. T h e r e f o r e U T is p-regular. THEOREM the two sets

4.3. I f U is a p-regular set of I* and if X is a subset of I*, then

U1= U/X = {v] v ~ l * a n d v X U2 = U ~ X =

(7 U 4= ~}

{wl w ~ I* and Xw 0 U # ~}

are p-regular. Proof First we shall p r o v e t h a t Rv C Rt;,. L e t a =- b (Rv) a n d let y E U1 ." a. T h e n ay ~ U~ a n d t h e r e exists x e X such t h a t avx e U. H e n c e yx U ." a = U ." b a n d byxe U. T h e r e f o r e bye U~,y¢ U1 ." b a n d U1 ." a C U1 ." b. Similarly, U1 ." b C U~ ." a. T h e r e f o r e U 1 ." a =

U 1 ."

b,

a =- b (Ru,). Since U is p - r e g u l a r , Rt., is a r i g h t c o n g r u e n c e o f finite i n d e x a n d Rv is r i g h t cancellative ( T h e o r e m 2.1). F r o m Ru C_ Rv, a n d L e m m a 2.1, it follows t h a t Rv, is o f finite i n d e x a n d r i g h t cancellative. T h e r e f o r e U1 is p - r e g u l a r . W e see easily t h a t U~'= Ur/X T. Since U is p - r e g u l a r , U r is p - r e g u l a r . T h e r e f o r e U~ is p - r e g u l a r , a n d since U,, = (uT) r, U2 is also p - r e g u l a r . W e shall show n o w that the family o f p - r e g u l a r sets o f I * is n o t closed u n d e r the o p e r a t i o n s o f p r o d u c t a n d star. L e t I = {a}; t h e n I* = {a" I n / > 0}. Let U = {a 2''+1] n /> 0}. It is easy to see t h a t Ru is a cancellative cong r u e n c e o f i n d e x 2 o n I*. H e n c e U is a p - r e g u l a r set o f / * . T h e c o n g r u e n c e Ru2 is n o t cancellative since

a° . a '

=a 2.a'(Rv2)

and

a ° ~ as (Ru~). T h e r e f o r e , t h e p r o d u c t U • U = U "2 = {a""] n > 0} is n o t a p - r e g u l a r set. Let U = {a a'+21 n / > 0}. T h e n

u * = tJ

k=0

°} U {a s) U {a"l n

4}.

W e see easily t h a t R v is a cancellative c o n g r u e n c e o f i n d e x 3 o n I*. H e n c e

90

G. TmERaIN

U is p-regul~ir. T h e congruence

Rv* is not cancellative, since

a°'a 4-a'

. a 4(RU,)

and a ° ~¢ a' (/%,). T h e r e f 6 r e U * is not a p-regular set.

REFERENCES [ 1] P. DUBREIL, Contribution ~ la th~orie des demi-groupes. Mgm. Acad. Sci. Inst. France (2) 63 (1941), no. 3, 1-52. [2] S. GINSBURG,An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass., 1962. [3] G. HARTMANISand R. E. STEARNS,Algebraic Structure Theory of Sequential Machines. Prentice-Hall, Englewood Cliffs, N. J., 1966. [4] M. O. RABIN and D. SCOTT. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125. [5] G. TmERRIN, Sur la caract6risation des groupes par leurs 6quivalences r6guli~res. C.R. Acad. Sci. Paris 238 (1954), 1954-1956. (Received 14 September 1967)