RELATIONAL TREE AUTOMATA AND CONTEXT-FREE SETS Dedicated to Professor Tatsuji Kudo on his sixtieth birthday

Bull. Kyushu Inst. Tech.

(M, & N. S.) No. 27, 1980, pp. 17-25

RELATIONAL TREE AUTOMATA AND CONTEXT-FREE SETS

Dedicated to Professor Tatsuji Kudo on his sixtieth birthday

By

Yasuo KAWAHARA

(Received Oct. 31, 1979)

Various algebraic approaches to theoretical computer science have been tried by many authors for years. For instance ADJ [9, 10] introduces ordered algebraic theories and studies them for wider applications to the ranges of computer science. The purpose of this paper is to prove a theorem due to Mezei and Wright [7] in the framework of Arbib and Manes [1, 2]. In [4] Eilenberg and Wright generalized the result by means of theory of T-algebras introduced by Lawvere, to prove that the recognizable sets and algebraic sets coincide for free theories with finite bases.

We assume that the readers are familiar with calculus of relations and the category Rel of sets and relations. In the category Rel we denote by ct: A--7B a relatjon,f: A.B a map, ct•6: A--rC the composite of two relations ct: A--7B and 6: B-7C, and ct': B--.A the inverse relation of ct: A--7B. The category Rel admits a natural structure Rel= ÅqRel,

M, e,...År of monoidal categories as indicated by Ehrig et al. [3, p. 30]. Note that the unit object e of Rel is a single element set. Given a label set (9, v: 9.N), where N js the set of non-negative integers, we have already obtained an endofunctor Xn: Rel.Rel, called the 9-tree process in Kawahara and Yamaguchi [5]. Since the multiplication (cartesian product) of the monoidal structure of Rel commutes with coproducts (disjoint unions), the 9tree process Xg is an input process by Theorem 1.1 of [5]. In what follows we assume that a finitet) label set (2, v: 9-ÅrN) is fixed. The notations and terms in [5] are freely used here.

g1. Relational 2-tree automata and 2-grammars

A (relational) 9-tree automaton M is an Xg-dynamics (9, S) equipped with an (output) relation 6: 9.e, where e is a single element set. Thus an 9-tree automaton M is represented as a diagram

eX.

M: Ol e-ir'e

t) A label set (9, p: 9.N) is finite if 9 is a finite set.

18 Yasuo KAwAHARA

in the category Rel. The reachability relation C: ipX9"9 of an 2-tree automaton M=

(9, 6, 6) is a unique Xn-dynamorphism 4: (ipX9, ippt)"(9, 6), where di is the empty set.

The response (behavior)f: ipX9-Te of an 9-tree automaton M is the composite 4 •6 of the reachability relation 4: ipX9--re and the output relation 6: 9--.e. For a subset U of a set Vwe define a relation O: e-7V by O=eÅ~UceÅ~ V. Note that a relation ct:e-7

Vcorresponds to a subset of V. A subset L of ipX9 is called recognizable if Åí#: ipX9 -Te is the response of some 9-tree automaton M.

We remark that the endofunctors Xg, X9: Rel--"Rel defined in [5] satisfy the follow- ing additional properties :

i) ct"Xg=(ctXg)" and ct#X9=(ctX9)" for each relation ct: 9-T9'.

ii) ctXncct'Xg and ctX9cct'X9 for two relations ct, ct': 9--79' with ctcct'.

iii) (V ctn)Xn== V ctnXg and (V ctn)X9 =V ctnX9

nlO nlO nlO nlO

for an ascending chain ococcttc•••cct.c•••: e"9' of relations.

A relation G: V"VX9 is called an 9-grammar on Vif Vis a finite set and if G is a finite relation, that is, G is a finite subset of Vx VIX9. Given an 2-grammar G: V-7 VIX9 and an Xg-dynamics (9, 6), we define a map G.:Rel(V, 9).Rel(V, 9) by, for each relation T: V"9, G.(T)=G•r, where r is a unique Xg-dynamorphism r:(VX9, Vpt)-T (9, 6) rendering the triangle

vZ-, VX.@

X l'

e

commute (Cf. [5; Theorem 1.1]).

We immediately have

PRoposiTioN 1. If G, G': V---7VLX9 are 9-grammars and M: V"V is a relation, then

(i) (G U G').(T) - G.(T) U G'.(T) (ii) (M • G).(T) -M • G.(T)

for each Xn-dynamics (9, 6) and eachTERel(V, e). O

THEoREM 2. Let G:V-7VX9 be an 9-grammar and (9, 6) an Xg-dynamics. If TocTic•••cT.c•••: V--79 is an ascending chain of relations, then G.(V T.)= v G.(T.).

n)O nZO

PRooF. It follows at once from the fact that (V T.)X9==VT.X9 and G.(T):

n)O n20 G•TX9•6@, where 6@: (2X9, 9pt).(9, 6) is a unique Xg-dynamor-p' hism rendering the

triangle

Relational Tree Automata and Context-Free Sets 19

e -2ll'-År ex9 "XiX,.io@

e commute. U

Note that the last theorem implies that the map G. preserves the ordering of relations.

Given an 9-grammar G: V"VX9 and an Xg-dynamjcs (9, 6), we define inductively a sequence {T.eRel(V, Q)lnEN} of relations by To=ip (the empty relation) and T.+i=

G.(T.) fornEN. PutT=VT.. Then, by Theorem 2, we have TocTic•••cT.c••• and n)O so G.(T)= V G.(T.)=:V Ti+i=T. Next assume that G.(T')cT' for some T'eRel(V, 9).

n20 n)O Then we hive T.cT' f-or neN, since TocT', and hence T==v T.cT'. This proves that n).O

T= V T. is the minimal fixed point of the map G.: Rel(V, 9).Rel(V, 9) and it is the min"

al solution ofthe inequality G.(T)cT. We say that T= V T. is the minimal solution nlO of the equation G.(T) ==T for an Xg-dynamics (9, 6), and we denote it by T(G).

LEMMA 3. LetG: V7VX9, 6': V'-7V'X9 be two S2-grammars. ifthe square vt -SZ'-. V'pag

ctl Ictxg V-. VX9

commutes, then T(G') =ct • T(G) for each Xg-dynamics (e, 6).

.

PRooF. Let {T.ERel(V, 9)1nEN} and {TAERel(V', 9)lneN} be two sequences defined by To=ip, T6=ip and T.+i= G.(T.), TA+i=G'.(TA) for nEN. Assume that TA=

ct•T. for some nEN and r.: (VX9, Vpt)-7(e, 6) is a unique Xn-dynamorphism with Vn•

rn =T.• Then we have

TA+1 = G'•(ct ' Tn) = G' ' ctX9 ' rn = ct ' G' rn= ct ' G•(Tn) = ct ' Tn+1 '

Since T6=ct•To, this shows that T9=ct•T. for all nEN and so T(G') =ct•T(G). O As applications of the above lemma we describe two propositions below.

PRoposmoN 4. Let Gk: Vk"VkX9 (k :1,..., n) be 9-grammars and let ih: Vh•

H Vk be the h-th injection of coproducts (h=1,..., n). Define an 2-grammar G:

ISkSn

'll- Vk"( ll Vk)X9 by G= V iZ•Gk•ikX9, then i,•T(G)=T(G,)(h=1,...,n) for

IEk5n IEkEn IEk5n

each Xn-dynamics (9, 6).

20 Yasuo KAwAHARA

PRooF. To prove the proposition, by virtue of Lemma 3, it suffices to show that the square

V, -gb.. V,X.@

i,I ii,x9

ll Vk -G (ll Vk)Xg@

ISk5n ISk5n

commutes (h---1,..., n). But we have

i, •G== i, •( v i,# • G, • i,X9)=G, • i,X9 15k-Sn

since ik•iX==ip (k7Eh) and ik•i,E=lv.. This completes the proof. O

PRoposmoN 5. Let G: V-.VX9 be an S2-grammarand let ii: V.Vlle and i2: e

.Vlle be the injections of coproducts, where e is the single element set. If ct= i#i U i2# • O:

VI-Ie--T V and G = ct • G • ii X9 : VHe"(Vll e) X9 for some su bset U of V, th en i2 • T(G) = V n•T(G) for each Xg-dynamics (e, 6).

uEU

PRooF. We first remark that

ii • ct=ii •(i"i U i2# • 0)=il •i"i U ii • i2' • 0= lv

since ii • i"i = lv and ii • i2" = ip. Therefo re G• ctX9 = ct •G• i, X9 • ctX9 = ct • G• (i, • ct)X9

= ct • G and so T(G) = ct • T(G) by Lemma 3. Hence we have i2 • T( G) = i2 • (i 'i U i2" • 0) • T( G)

=va•T(G). o

ueV

g2. Context-freesets

Given an Xs2-dynamics (e, 6), a subset L of 9 is called context-free in (e, 6) if there exists an S]t-grammar G: V--7VX9 and an element ve Vsuch that Åí==D•T(G), that is, L is a component of the minimal solution T(G).

PRoposiTioN 6. Afinite union of context-free subsets is also context-free in each Xg-dynamics (9, 6).

PRooF. This is an immediate consequence ofProposition4 and 5: a

PRoposlTloN 7. The empty set is context-free.

PRooF. Let (2, 6) be an Xg-dynamics and V a non-empty finite set. Define an

S2-grammar G by G :Vq: V. VX9. If {T.eRel(V, e)lneN} is a sequence of relations

Relational Tree Automata and Context-Free Sets 21

defined by To == ip and T. . , = G.(T.) (n G N), and if r. : ( VLX f3, VIL) --T (e, 6) is a unique Xn- dynamorphism with Vny • r.=T., then

Tn+1 =G'(Tn) : Vn ' rn == Tn

and so T.=ip for each nEN. This shows that T(G)=:ip and hence ip==fi•T(G) for each element ve V. O

PRoposiTioN 8. Every si,ngle etement subset of ipXf? is context-free in (ipX9, ippt).

PRooF. Let 4 be an element of ipX9 and Va non-empty finite set. There is a unique Xg-dynamorphism p:(ipX9, ip#).(VX9, VLt). Define an 9-grammar G: V-T VX9 by a single element subset G== {(v, p(4))}cVx VX9 for an arbitrary element vEV and define a sequence {T.eRel(V, gbX9)lnEN} by To=ip and T.+i=G•(T.) (neN)•

From the fact that p•r =1ipxf. and so (p(4), 4)Er for each Xg-dynamorphism r: (VX9, Vpt)--7(diX9, ippt), we have T.+i={(v, C)} for each nEN. Hence it follows that T(G)=

{(v, 4)} and 8=D•T(G). O

We denote by Ve: VXg.VX9 the composite VnXg• Vpt: VXg-VX9 of VnXg: VXg .VX9Xg and Vpt: VX9Xg.VX9. Since maps VnXn and Vpt are injective, so is the map Ve: VXn.VX9. We say that an 9-grammar G:V--rVX9 is of degree1 if G•Ve"•Ve

=G. Given an 9-grammar G: V--7VX9, we define an Xg-dynamics 6G: VXg-7V on a finite set V by 6G== Vc•G#. Converseiy, given an Xg-dynamics S: VXg-7V on a finite set V, we define an 9-grammar G6:V-7VX9 by G=S#•Ve. The relation Go is in fact a finite relatjon since 2 and V are finite and so is VXg. The 2-grammar Gj is always of degree 1 because

Gj• Ve#• Ve == 6#•Ve• Ve#• Ve == Gb by Ve == Ve• Ve#• Ve.

For an 9-grammar G: V-7VX9 of degree 1 and an Xg-dynamics 6: VXg"V, we have

Go. =(Ve • G')# • Vc == G• Ve# • Ve == G

and 6G, =Ve•(6#•Ve)#=Ve•Ve#•6=6

since Ve is injective and so Ve•Ve#=lvx.. This clearly gives a bijection between 9- grammars of degree 1 on a finite set Vand Xg-dynamics on V.

Next we prove a basic property of the minimal solutions.

THEoREM 9. Let G: IZ"VX9 be an 9-grammar of degree1 and (9, 6) an Xg-

dynamics. if the dynamics 5: 9Xg"e is an injective map, then T(G)#: e---7Vgives an

X.-dynamorphism T(G)": (9, 6)"(V, 6G)•

22 Yasuo KAwAHARA

PRooF. Let {T.ERel(V, 9)lneN} be a sequence of relations defined by To=(15 and T.+i==G.(T.) (nGN) and let r.: (VX9, Vpt)--7(e, 6) be a unique Xn-dynamorphism with Vn•r.=T. (neN). Then we have

Tn+i == G'rn == G• Ve#•J/e•r. (G is of degree 1) =6E-VnyXn•VLt•r. :6g•VnXn•r.Xg•6

= (5e • T.Xg • (5

and T.+i•5# =6g•T.Xg•6•6#= 6g•T.Xg

since 6 is an injective map and so 6•6#=IQx.. Hence T(G)#==(VT.)# gives an Xg-

dynamorphism (9, 6)---.(v, 6.). D nlO

The following corollary is a version of Theorem 2 of Eilenberg and Wright [4].

CoRoLLARy 10. Let G: V-7 VXf3 be an S2-grammar ofdegree1and T(G): V--TipX9 the minimal solution of G,(T) :T for the initial free Xn-dynamics (ipXf:?, ippt). Then

T(G)": (ipXEft?, ippa)-T(V, SG) is the unique Xn-dynamorphism.

PRooF. Since in: IX9Xg.IX9 is injective by the definition, it follows at once from

Theorem9. M

g3. Mainresults

We can now prove the following theorem corresponding to Proposition 1 in Eilenberg and Wright [4].

THEoREM 11. Given an S2-grammar G: V-7 VX9, there exists an S2-grammar G-: V -T VLX9 such that

i) 6• Vn"= ip

and ii) T(G)==T(G) for each Xg-dynamics (9, 6).

PRooF• Define G'==G•[,..Y{e}Vj(#t)•VJ'(,)], where Vj(t): V(t)--År,!I.l V(t)= l71X9 is the

t-th injection of coproducts (Cf. [5]). Since VVj(#,)•Vi(t)=lvx9 and Vn--VJ'(e), we

tE :T have G == G• Vn#• Vn U G+ and so trivially G• Vn#• Vn c G, G' c G. It is clear that (G • Vny" • Vn).(T) = G • Vq' • Vn .(T) == G• Vq" •T for each Te Rel (V, 9). We now form the relation (G • Vn ")" == V (G • Vq ")": V--7 V, where (G • Vq ")O =1. and (G • Vq #)n'i ==

nlO (G•Vq")"•(G•Vq") for neN, Put G---(G•Vny")"•G'. Then G: V--TVX9 is in fact an 2-grammar since Vis a finite set and G is a finite relation. By the definition it follows

that G--•Vny"=ip and G•Vny#•GwwcC;. Finally we shall prove that T(G)=TÅqG). Assume

that G.(T)==T. Then we have

Relational Tree Automata and Context-Free Sets 23

G• Vn"•T=(G• Vn"• Vn).(T)cG.(T)=T andso (G•Vn")"•TcT.

Hence G- .(T) == [(G• Vq")"•G'].(T) =(G• Vn')"G".(T)

c (G• Vny")"G.(T)=(G• Vq")"•Tc T.

Conversely, assume that G.(T)=T. Then we have

G.(T)=(G • Vn" • Vn U G').(T) =(G • Vn" • Vn).(T) U G".(T) cG• Vny"•Tu G-.(T) = G- Vn"• (;.(T) UT

== (G • Vn" • G).(T) U Tc G.(T) U T=T.

This proves that T(G) = T(G). n

The degree of an S2-tree is defined as follows:

O) For t =e, deg (e)=O.

n

1) For t=(ti,..., t.)co with v(tu) =nll;O and ti,..., t.G,/07`, deg (t)=1+2 deg (tk).

k=1

The following theorem corresponds to Proposition 2 in Eilenberg and Wright [4].

THEoREM 12. Given an 9-grammar G: V--rVX9 with G•Vn#==di and an S2-tree

tE,/`7- with deg(t)År1, there exists a.finite set Vwi,th an injection i: V"V and an Si}- grammar G: 7-7 VX9 such that

i) G• Vn" = ip and G• Vj (",) = ip,

ii) if G• Vj "( ,) = di for an S2-tree s G ,9' with s 7E t and deg (s) l; deg (t), then G- • i7j (",)

=: ip)

and iii) i•T(G) =T(G) for each Xg-dynamics (9, 6).

PRooF. The 9-tree t with deg(t)År1 has the form t=(ti,..., t.)co for a)e9 with v(co)==nÅrO and ti,..., t.E,/`7'. We can choose an S2-tree tp with deg(tp)ÅrO among ti,..., t.. Put 7=VllV(t.) and let i: V-Åre h: V(,.).Vbe the injections of coproducts. In this proof we write Vj(,): V(,)--ÅrVX9 (sev"'") forj(,). We now define an 9-grammarG: V-T i7 X9 by G=: G(O) u G(i) u G(2), where

G(O) = i# • [G ---j(#,) •j(,)] • i.X9 : V7----, IJT/x9

N.{:i

H= j(t,) • iX9M•''Mh• VnM•••Mj(t.) • iX9: V(t,)D•••O V(t.) . (7X9)"

G(i) =: i# • G•j(#,) •H• Vpt(.): V- 7X9 and G(2) =h# •j(,.)• iX9 : 7" VX9.

First we shall show that i•T(G)=T(G). Assume that G.(T)=T for TeRel(V, 9) and

24 Yasuo KAwAHARA

put T"=i'•TUh#•j(,.).(T): V-T9. For the unique Xg-dynamorphisms r:(VX9, Vpt)--"t (9, (5) with Vn•r=T and F:(VX9, i7Lt)-.(e, (5) with 7n•7=T-, it clearly holds that r=

iX9•f, i•i---Tand h•T----J'(,.)r. Then we have

G(O).(T-) == i# • [G -j(#,) •J'(,)] • r, H• Vpt(.) •F =H• r-n • 6.

:[J'(ti)O'''Uj(t.)] • r" • 6.

== [j(tt)O'''Oj(t.)] ' V#(co) ' r = J(t) . r,

G(i).(i) = i# • G • 1' (",) • J'(t) • r,

G(2).(T-) = h# •j(,.) • r,

and hence

G.(i)=:G(O).(i) u G(i).(i) u G(2).(i) : i# •G•ru h# •j(,.) •r

=: i" 'TU h" 'j(t.)'(T) (G•(T) =: T)

"f'

Similarly, if G- .(T-) =f forieRel(7, 9), then we can show that G.(i•T-)=i•i. This proves that i•T(G)=T(G). The properties i) and ii) will be obtained from the fact that

G(O) • Vj (#,) = ip for each s e .9` with either s 7E t or G •j(#,) =: di,

p

-v

G(i)• Vj(#,)=ip for sl(ti,,.., e,..., t.)co,

and G(2)• Vj(#,) == ip for s7E t..

This completes the proof of the theorem. O

Since .V.gVi.# •Vi. =lvx., Vi.• Ve =VJ'((e,...,e).) and an 9-tree t of degree 1 has the

form t=(e,..., e)tu for some tuG9, an 9-grammar G: V-T VX9 is of degree 1 if and only if G•Vl' (#,)=ip for each tG./07' with deg(t)7El. Thus the following theorem has been established by an iterative application of Theorem 11 and 12.

THEoREM 13. For each context:free subset L in an Xg-dynamics (e, S), there exists an S2-grammar G: V" JZX9 Qf degree 1 and an element veVsuch that Åí =D•T(G). U

Finally we describe the result due to Mezei and Wright [7] and it was generalized

by Eilenberg and Wright [4] for the case of tree automata and polynomials defined by

Yasuo KAwAHARA 25

algebraic theories.

THEoREM 14. In the initialfree Xg-dynamics (ipXCgD, q5pt), the recognizable sets and the context-free sets coincide.

PRooF. Let L be a recognizable subset of diX9. Then there exists a finite S2-tree automaton M=(V, 6, 6) such that Åí=(4•6)", where C: (ipX9, ippt)"(V, 6) is a unique Xn-dynamorphism. Since T(Gj)"=4 by Corollary 10 and 6" =O for a subset U of V, it follows that Åí=O•T(Gj)= Va•T(Gj) and hence L is context-free from Proposition 6.

uEU

Conversely, assume that L is a context-free subset in (ipX9, ippa). By Theorem 13, there exists an S2-grammar G: V--.VX9 of degree 1 and vGVsuch that Åí=D•T(G). Again, by Corollary 10, T(G)" gives the unique Xg-dynamorphism (ipX9, ippt)--7(V, 6G) and Åí"==

T(G)' • D' is the response of an S2-tree automaton (V, 6G, D#), which proves that L is recog-

nizable. Hencetheproofiscompleted. O

References

[1] M.A.ARBiBandE.G.MANEs, Machines in a category: An expository introduction, SIAM Review 16 (1974), 163-192.

[2] M.A.ARBiBandE.G. MANEs, Arrows, struetures, andfunctors, Academic Press, New York, 1975.

[3] H. EHRiG et al., Universal theory ofautomata, B. G. Teubner, Stuttgart, 1974.

[4] S.EiLENBERG and J.B.WRiGHT, Automata in general atgebras, Inform. Control 11(1967), 452--470.

[5] Y. KAwAHARA and M. YAMAGucHi, Minimal realization theory for tree process machines in mo- noidal categories, Mem. Fac. Sci. Kyushu Univ. Ser. A 34 (1980), 71-78.

[61 S. MAcLANE, Categoriesfor the working mathematician, Springer-Verlag, New York, 1971.

[7] J. MEzEi and J. B. WRiGHT, Algebraic automata and context-free sets, Inform. Control 11 (1967), 3-29.

[8] J. W. THATcHER and J. B. WRiGHT, Generalizedfinite automata theory with an application to a de- eision problem ofsecond-order logic, Math. Systems Theory 2 (1968), 57-81.

[9] E, G. WAGNER, J. B. WRiGHT, J. A. GoGuEN and J. W. THATcHER (ADJ), Initialalgebra semantics and continuous algebras, J. Assoc. Comput. Math. 24 (1977), 68-98.

[10] E, G. WAGNER, J. B. WRiGHT, J. A. GoGuEN and J. W. THAcTHER (ADJ), Some jundamentals of order-algebraic semantics, Lecture Notes in Computer Science 45, Springer-Verlag (1976), 153-168.

Department of Applied Mathematics

Kyushu Institute of Technology

Tobata, Kitakyushu 804

Japan