(50,1ご
織 お
1謝::リ
AN APPLICAT10N OF COHEN'S RESULT
ON STAR HEttGⅡ T TO THE THEORY OF
CONTROL SttRUCTURES
TATSUYA MOTOKI
Department of =nformation Sc■ ence
工baraki
UniVersity
Hitachi 316,
-1-
」apan
Abstract.
We app■ y a resu■ t/concept on star height to two prob■ ems in
the theory of contro■ structures.
First, we genera■ ize
Kosarajuts systems REn
structures and show, by using
°f C° ntro■
Cohents resu■ t on star he■ ght, that the genera■ ized systems
constitute a path― wise hierarchy with respect to their
expressive powerse
second, by using a concept on star height,
we sharpen Peterson et a■ .'s resu■ t that RE∞ is path― wise■ y
comp■ ete.
-3-
1。
INTRODUCT工 ON
A■ though
prob■ em
regu■ ar events have been extens■
ve■ y
studied, the
of determining the star height of a regu■ ar event
is on■ y partia■ ■y so■ ved.
A■ ong resu■ ts on star height our
concern is Cohenis resu■ t [2]that for a certain fami■ y of
regu■ ar events the star heェ ght equa■ s
comp■ ex■ ty of an automaton recogn■
z■
a certain measure of
ng the event.
The theory of contro■ structures arose from Dijkstra [3]
who advocated avo■ ding the use of unnecessar■ ■y comp■ ex contro■
structures
■n
programs.
Contro■ structures have been w■
de■ y
studied before 1975 and many theoretica■ resu■ ts have been
presented on their expressive powers.
For instance, K9saraju
[6] introduced RE[n]― structures (。 r REn ChartS in terms 91
Kosaraju)and showed the semantic hierarchy:
RE[1]―
where
Sem RE[2] Sem RE[う
ёach ■ine
] Sem RE[4] Sem
means that the right system Of contro■
structures has more express■ ve power than the
semantic v■ ewpo■ nt.
■eft
from the
Other notab■ e resu■ ts are rev■ ewed in
Leagard et a■ e[7].
Now we can easi■ y see the
■anguagё ―theoretic
between regu■ ar express■ ons and program schemes.
simi■ arity
ェn
thiS paper
we app■ y Cohenis resu■ t on star height to a prob■ em in the
theory of contro■ structures.
Exp■ ic■ t■ y speaking, we
genera■ ize Kosaraju:s RE[n]― structures and show the path― wise
(or ■anguage― theoretic)hierarchy:
-4-
l pW RE[2]―重型LRE[2+1/2]pw ....。
where each
■ore
■ine
means the right system of contro■
exprOsS■ Ve power than the
viewpoint.
■eft
from the
sructures has
■anguage―
theoretic
In fact, the hierarchy
RE[1]pw RE[2]― 理型二RE[う ]― 理型LRE[4]pw
fo■ ■ows
immediate■ y frOm Kosara]u:s semantic hierarchy.
In additiOn, we sharpen Peterson et a■ .'s resu■ t [8]that
the RE[∞ ]― structure is
■anguage― theoretica■ ■y
comp■ ete.
2c PRELttMttNARIES
2。 1。
FLOWCHARTS AND PROGRAMS
A (deterministic)finite incomp■ ete automaton M is a
quintup■ e (S,A,δ
an a■ phabet, s。
fina■
to S.
,s。
states and
The
'F), where s is a finite set of states, A is
iS the initia■ state, F⊂ S is the set of
∈s
δ
■anguage
in the usua■ way.
is the transition partia■ function from S
×A
recognized by M, denoted by L(M), is defined
Let <M,s〉 denote the finite incomp■ ete
automaton obtained from M by changing its initia■ state into s.
We say that M is reduced if and On■ y if (1)it has neither any
dead state nor any inaccessib■ e state from the initia■ state,
and (2)s1 / s2 imp■ ies L(く M,sl〉 )/ L(〈 M,s2〉 )f° r any pair of
States sl, s2・
In the seque■ , we use three pairwise■ y dis30int infinite
-5-
.
sets of symbo■ s lF, lP and iF l p ∈lP}; and ■
et
= F UP U l百 l p ∈ lP}. The set lF means a set Of prinitive
actions (e.ge assignment statements), and the set lP means a set
Σ
of pr■ m■ tive predicateo
by
The symbo■ Of identity actiOn, denoted
is a■ so in lF.
λ,
A f■ owchart
is a finite incomp■ ete automaton (s,A,δ ,s。
'F)
satisfying the fo■ ■owing three conditions:
(1)A is a finite subset of
Σ.
(2)For every s∈ s, either
I(s,a)iS defined}= lp,コ }for some p∈ lP,
I(s,a)iS definedl = lf}for some f∈ lF, or
(2。 2)la∈ A
(2。
1)la∈ A
I(s,a)iS definedl = φ
(3)F = Is∈ S I(s,a)iS undefined for every a∈ A}.
(2.う
)la∈ A
.
A f■ owchart (S,A,δ ,6。 ,F)is
often dё noted by its state graph
(S,E,s。 ), where E = 1(s,五 ,t) l δ(s,a)=
tl is the set of edges.
The c■ ass of programs and the he■ ght of a progralll Q,
denoted by h(Q), are defined as fo■
(1)ヽ
■ows:
Any e■ ement of lF, exit(i)for any positive integer i, and
halt are programs of height O。
(2)For any p∈ lP UiF l p
Q;R
and
∈
lPl and prOgrams Q and R,
if p then Q e■ se R fi
are programS of height max(h(Q),h(R)), and
whi■ e
p do Q end
and
reneat Q end
are programs of height h(Q)+1.
The execution of exit(i)is intended to cause termination of i
enc■ osing whi■ e/repeat_■
6ops.
different from Kosaraju's.
Thus the meaning of exit(i)is
A■ ■other commands/contro■
structures have the■ r usua■ mean■ ngs.
-6-
For any nonnegative
n, an n― pFOgram
■nteger
■s
occurrence of exit(i), i
a program conta■ n■ ng neither any
〉 n,
nor ha■ t, and an (n+1/2)― program is
a prOgFam COntaining no occurrence of exit(i), i
of c― program
〉
n.
The c■ ass
is denoted by RE[c].
We may cons■ der a program to be a f■ owchart.
This
■s
accomp■ ished by regarding occurrences of ;, then, e■ se and ュo ■n
the program as statese
We denote by G[Q]the f■ owchart
associated with a program Q.
For examp■ e, the fo■ ■owing program
Q haS the associated f■ owchart G[Q]in Fig。
■f
3
λe■ se2 ha■ 立 ￡i 。
,
p thenl
whi■ e
1。
q 4p4 g ;5
lepeat if r then6 eXIt(1)e■ se7 f fi end
end
Let Q' be the subprogram
repeat
ex■ t
The
r then exit(1)e■ se f fi end
state s5
°f
G[Q]is the entry state of Ql,
state of Qt, and s6 and s7 are
s Of
is the
スノ ー
Ｓ Ｑ
in Q.
■f
`
The
forma■ defin■ tion of these notions w■ ■■ be c■ ear.
Now we define the trace set of a program Q, denOted by
L(Q), to be II(G[Q])。
Here the symbo■ of identity action is
considered to be the empty word; that is
w∈
Σ■.
λw
= wλ = w for every
Thus a f■ owchart is actua■ ■y a finite incomp■ ete
automaton w■ th c― moves, but these C― moves are obv■ ous■ y
■nessentia■
onese
We say that a f■ owchart G is convertib■ e to a
progralll Q if and on■
f■ owchart
y if L(G)=
G is c― convertib■ e
■f
II(Q)。
We a■ so say that a
and on■ y if G is convertib■ e to
some c― program.
Suppose that a f■ owchart G is convertib■ e to a program Q.
-7-
FoF a Subprogram R of Q, We Say that a state s of G corresponds
to the entry state of R if and on■ y if L(く G,s〉 )= L(〈 G[Q], the
lf the entry state of R is access■
b■ e
the initia■ state of G[Q], there exists such a state s.
We
entry state of R>).
from
define s■ m■ ■ar■ y for the exit state and interior states of R.
2.2. COHEN:S RESULT ON STAR EEIGET
The star height of a regu■ ar expression over an
■s
a nonnegative
■nteger
a■
phabet A
defined as fo■ ■ows:
(1)φ and e■ ements of A have star height O.
(2) (α +β )and (α β)have
height of
star height max(star height of
α,
star
β).
(3)α tt has star height (star height of
α)+1。
The star height of a regu■ ar event L, denoted by sh(■ ), is the
star height of regu■ ar expressions dettoting L.
■east
Cons■ der
the operation over state graphs of de■ eting one
state and re■ ated edges from each max■
of stateso
the
■east
■oops
ma■
strong■ y connected set
The rank of a state graph G, denoted by rank(G), iS
number of app■ ications of the operation to break a■
in G.
■
For examp■ e, the rank of state graph in Fig. 2 is
l, sinCe the exhaustive search of ways of app■ ications, shown in
Fェ g。
5, revea■ s that the 9ptimum way ■s to de■ ete so and s4 at
once.
Likewise, the rank of state graph in Fig。 4 iS 2.
We say that a regu■ ar event L has the fin■ te
property if and on■ y if xヽ L /y｀ L imp■ ies l(x｀ II)∩
for every pa■ r of words x, y.
-8-
■ntersection
(y｀ L)￨
< ∞
THEOREM 2.1。 (Cohen [2])
inё omp■ ete
SuppOSe that a reduced finite
automaton M recognizes a regu■ ar event L.
If L has
the finite intersection property, sh(■ )= rank(M).
We now have the fo■ ■ow■ ng coro■ ■ary.
COROLLARY 2。 2.
工f
a reduced f■ owchart G is convertib■ e to a
program Q and L(Q)has the finite intersectiOn property, then
h(Q)〉 rank(G)。
Proof.
We first obtain
rank(G[Q])〉 sh(IJ(G[Q]))
from Egganis resu■ t [4]that the star height of a regu■ ar event
does not exceed the rank of any state graph recogn■ z■ ng that
event.
The coro■ ■ary fo■ ■ows immediate■ y from Theorell1 2.1, the
above inequa■ ity and the fact h(Q)
Coro■ ■ary 2。 2,
app■ ied
うe
〉
rank(G[Q]).
Q.E.D.
under the condition h(Q)= 1, is often
to inconvertibi■ ity proofs.
A HIERARCHY OF CONTROII STRUCTURES
This section
■s the ma■ n
part of the paper and is devoted
to the path― wise hierarchy ■n Theorem ぅ.8.
LEMMA 3el.
There exists a f■ owchart which is l― convertib■ e
but not 1/2-convertib■ e.
-9-
Proof.
Ilet G=(S,E,s。 )denOte the f■ owchart in Fig. 4。
Then
the f■ owchart (S, E-1(sぅ ,gl,SO)￨' S4)i' C° nvertib■ e to the
fo■ ■owing
l― program Ql.
f2 ;
e■
e■ se
se
ｏ ２
．， ｐ ｉ 一
ｆ
ｆ
一 λ
ｉ
2 then
鼈 ｏ ●■
，
” ｆ
ｆつ ｉ一
repeat if p3 then
then f2
e■
se Qri上 (1
g2 ;
・
f p2 then f2
e■
se
exit(1)塾
墓
end
Therefore G is convertib■ e to the fo■ ■owing l― program。
whi■ e
pl艶 ギ
ql如
e■ se
・
Q1
3 81
f p2 then
e■ se
Ql
; gl
gl墓
墓
end
Now assume that G is convertib■ e to a 1/2二 program P.
We
e state frOm the
=ay assume that G[P]contains no lnaccessib■
initia■ state. ■
et Q be a 1/2-program obtained froEI P by
changing each subprogram of the form while pl lp
・ 0・
end into
p ha■ t end or equ■ va■ ent■ y the program
理
■f pl then λ else ha■ t fi. Then L(P)= L(Q)since c has exact■ y
the program while =巧
One eage Of the form (。 。.,pl,.。 。)and this edge entё rs to the
fina■ state s∞ .
Hence G iS a■ so convertib■ e to Q.
Let Q: be
a subprogram of Q Of he■ ght l anc of the fOrm whi■ e r do 。。. end
Or 蝉
。
・・
end.
By the construction of Q, the subprogram
Q' dOeS not have the fOrm whi■ e pl 12 。c0 9理ユ・
Suppose that Ql is of the form whi■ e p2 1Q R 9ュ ユ. Then
-10-
the
tate s3 0f G corresponds to the entry state of R and the
State S2
°°rresponds
to the exit state of R, since G has exact■ y
one edge of the form(..。 ,巧 ,。 …)・ Thus,since R is a■ oop― free
subprogram, in an automaton (S, E-1(s2'p2'S3)l, s。 )there must
exist on■ y a finite number of paths from s3 t° S2'
a contradictione
whi■ e
r艶
Likew■ se, Qt Cannot have the form
.…
9nd fOr any other r∈ I pl,p2'pァ 弓,ql,■ ,q2'弓
Suppose that Q' is Of the form repeat e.. end. Let s
l・
denote the state of e correspOnding to the entry state of Q'。
We may a■ so assume s ≠ s∞ , becauSe if s = s∞ we may change Q'
■nto
the program ha■ t by the same reason as the case that we
obta■ n
Q from Po
term■ nation
Then, s■ nce ha■ t is the on■ y command to cause
of Q',
L(Q')= II(G[Ql])= II(<G,s〉
).
Thus from Coro■ ■ary 2。 2 and the fact that
x｀
L(く G,s〉
)≠
yヽ L(く G,s〉
for every pa■ r
)imp■ ies (x｀
L(〈 G,s〉
))∩
(y｀ L(く 0,s〉
))=
φ
of words x, y,
r,nk(く G,s〉 )≦
1・
But there does not ex■ st such s
■n
G, a contradiction。
As readers see in the proof of llemma
う。1,
Q.E.D.
COro■ ■ary 2.2
ows us to do without considering any detai■ ed structure of
a■ ■
programs.
LEMMA 3.2。
There exists a f■ owchart which is 1/2-convertib■ e
but not l― convertib■ e.
Proof.
The f■ owchart in Fig. 5, denOted by G=(S,E,s。 ), is
- 11 -
convertib■ e to the fo■ ■owing 1/2-program.
whi■ e
pl 19 fl ,
p2 12 f2 '
崚
wh■ ■e pぅ
" fぅ
・
,
f p4 then ha■ t
Qユ se
gぅ
fュ
end ;
︵
∠ ・
，
３
製
g5
end
Now assume that G is convertib■ e to a l― program Qo We lnay
assume that G[Q]contains no inaccessib■ e state from the initia■
state.
Let Q: be a subprogram of Q of height l and of the form
Whi■ e O・・
dO `.. end or repeat
。。. end。
■et
s be the state of G
corresponding to the entry state of Q:, s' be the state of G:
corresponding to the ex■ t state of Q:, and W be the set of
states of G corresponding to interior states of Q:.
We may a■ so
assume that s / s∞ and that Q' represents at ■east one ■oop; by
the same reason as in the proof of Lemma ぅ。1。 We ttow consider
the case s。 ∈W, the case s8∈ W and the remaining Oase, and
deduce a contradiction
The case s。 ∈W.
■n
each case.
since s。
∈W
and exit(1)is the on■ y
command in Q' tO Cause termination of Q, si must be the fina■
state and hence contro■
to the term■ na■ state.
L(Q')= L(〈 G,s〉
■eav■ ng
from Q' means cOntro■ reaching
Thus we obta■ n
),
and hence from corO■ ■ary2.2
- 12 -
rank(く G,s〉 )≦
1。
But there does not ex■ st such a state s
■n
G, a contradiction・
se, the condition S8∈ W eads to , COntradiction.
・
The case s。
The subprogram Q' represents
S
・
8三 生上
`w and
exact■ y one ■oop s2 S4 S5 S6 →S2' and hence two states sぅ
and
Likew■
S7
°f
G are
■n
(S, E― I(s,a,t)
fin■ te
W.
Thus, s■ nce
h(Q・
l a ∈ Σ, t ∈ S},
number of paths from sぅ
s。
)=1, in the f■ owchart
)there must ex■ st on■ y
°r s7 t° S・
a
But we cannot find
Q.E.D.
out such a state s in G, a contradiction.
There exiSts a f■ owchart which is
IJEMMA う。3。
(1+1/2)― convertib■ e but neither 1/2-convertib■ e nor
l― convertib■
e.
Fig。 6:
The f■ owchart in Fige 6 is seen to be
Proof.
(1+1/2)― convertib■ e in the same way as in the l― convertibi■ ity
proof of Lemtta 3.10
From llerllma 3。
l and 302, the f■ owchart is
seen tO be neither 1/2-convertib■e no■ 1-convertib■ e.
LEMMA
う。4.
Q.E.D.
There exists a f■ owchart which is both
1/2-convertib■ e and l― convertib■ e but not O― convertib■ e.
Proof.
The f■ owchart in Fig。 7 iS COnvertib■ e to the
1/2-prograzrl
wni■ e
p dO・ f q then ha■ t
e■ se
f fi end,
and convertib■ e to the .1-program
wh■ ■e
p do
■f
q then exit(1)9■ se f fi end.
The inconvertibi■ ity fo■ ■ows immediate■ y from Kasai [5],
-1う ニ
since the f■ owchart has a ■00p s。 → sl 'S2'SO and thiS
tw9 exits to the fina■ state,(s。 ,F,S4)and (sl,q,S4)・
LEMMA
■oop
has
Q・ E.D.
Given an (n+1/2)― program Q, Where n is a positive
う。5・
integer, we can find out an (n+1)― program of trace set L(Q).
Proofo
We give a required transformation procedure, which
inserts some dummy repeat― end structures into Q.
exp■ ain
First, we
the idea by using an examp■ e: Given a (2+1/2)― lprogram
whi■ e
pi
鯉
p2 ユQ
repeat ■f
Whi・ e
pぅ
th食 ユ 1』
e■
p4 then exit(2)e■ sQ fl 』ュ
se ■f p5 then ha■ t else exit(1)fi fi
end
end ;
ユ
・ f p6 then exit(1)e■ se f2 ￡
蝉
:
;
g,
the fo■ ■owing ■s a required ぅ―program。
repeat
whiユ e
pl lp
蝉
repeat if p2 then λe■ se exit(2)fi ;
repeat if pぅ
』 p4 th￡ ユ Q基 ユ立(3)
tL2ユ 主
e■
e■ Se
-14-
fユ
■f p5 th￡ ユ 9基 ユ立(2)
e■
end
SQ fl
.
SQ eXit(1)fi fi
,
end ;
ex■ t(3)
end ;
・ f p6 then exit(1)e■ se f2 fユ
end ;
g3
exit(1)
end
Forma■ ■y,
■et
iT姜 ,Tl,T2'・・
°
'T五
}be the transforIItation
system on programs, defined inductive■ y as fo■ ■ows:
(1)Tキ (Q)= Fepeat Tl(Q) ; exit(1)end.
(2)For every integer i, 1
く
i < n,
(2.1)if Q is in lF, then Ti(Q)= Q ;
(2.2)if Q = exit(j), j く i, then Ti(Q)= 9基 ■立(j) 3
Q = Qxit(j), j ≧ i, then Ti(Q)= exit(j+1) ;
(2。 4)if Q = ha■ t, then Ti(Q)= 9基 ュ
主(1) 3
(2。
う)if
(2.5)if Q = Rl;R2' then Ti(Q)= Ti(Rl);Ti(R2) ;
(2.6)if Q=夏 p then Rl喪Q R2彙 'lhen
Ti(Q)=
ゴ p then Ti(Rl)e■ Sp Ti(R2)ニ ユ ;
(2.7)if Q = repeat R end and i < n, then
Ti(Q)= repeat Ti+1(R)9ュ■ ;
(2。
8)if Q = repeat R end and i = n, then
Ti(Q)=
; exit(n+1)end ;
(2.9)if Q = whi■ e p do R end and i く n, then
■229ユ 主 二呈ユ￡ュ上 Tl(R)2■ュ
Ti(Q)= whi■ e p do Ti+1(R)2ュ ュ ; and
(2。
10)if Q = while p do R end and i = n, then
Ti(Q)=里
塾
聖 螢
三
p then λe■ se exit(2)墓
Tl(R)
-15-
;
end ;
eXit(n+1)
end.
The program T姜 (Q)is seen to be a required (n+1)― prOgram. Q.E.De
For every n∈ 12,3,4,5,.・ .}, there exists a
LEMMA う.6。
f■ owchart
which is (n十 ■プ2う ―convertib■ e‐ ut not n― convertib■ e.
We first define f■ owcharts Gn=(Sn,En''(1)),
Proof.
五∈ 12,3,4,5,0・ ・ }, as fo■
(1)Sn = Is(i)
■ows:
l i iS an integer satisfying l ≦ i < 2n+2}
U Is(∞ ) }∪ {t(i,j) l i and j are integers satisfying
2n+1 くi く2n+2 and O < j 〈n}.
(2)En=1(S(i),p(1),s(2i))11≦
i〈 2n+ll
∪
1(s(i),p(i5,s(2i+1))11≦ i〈 2n+1}
∪
1(s(1),f(i),t(i,0))12n11≦ iく
U 1(t(i,0),q(i,0),s(∞ )) 1 2n+1
≦
i
2n■ :￨‐
〈 2■ +21
∪
1(t(i,j),q(i,j),s(Li/2n―
計2」 ))12n刊 ≦i
1(t(i,0),q(i,0),t(1,1)) 1 24+1 く i く 2n+21
＜
∪
０
U l(t(i,j),q(i,j),t(i,j+1))
￨
) )
1 2n+1 ≦ i 〈2n+2}
∪ 1(t(1,n),q(i,n),s(l_i/2」
))
1 2n+1 ≦ i
く
2n+21.
We wi■ ■ show that Gn iS
(n+1/2)― convertib■ e but not n― convertib■ e.
We show the (n+1/2)― conVertibi■ ity by inductive■ y
constructing programs Ri, 1
(1)For each integer i, 2n+1
≦
く
i
≦
i
2n+2, as fo■ ■ols:
く
- 16 -
く j〈 n}
2n+1 く i < 2n+2, 。くjく nl
UI(t(i,n),q(i,n),s(Li/4」
As an examp■ e, G2 iS Sh° wn in Fig. 8。
2n+2,
2n+2,..et
f(i);
R.■ =
■f
q(I,0)then ha■ t e■ Se
■f
q(1,1)then exit(n)e■ se
■f
q(i,2)then exit(n-1)e■ se
λ
fi 3
if q(1,n) then ex■ t(1)e■ se
i, 1 < i
(2)For each integer
Ri=聖
く
ゴ p(i)then
蝉
λ fi
λ
;
λ fi
;
fi.
2n+1, .et
R2i
e■ Se
R2i+1
』ユ 饗 ・
The f■ owchart en iS eas■ ■y seen to be convertib■ e to the
(n+1/2)― program Rl.
Now assume that Gn iS C° nVertib■ e to an n― progran Q.
We
may assume that G[Q]contains no inaccessib■ e state fron the
Let Ql be a subprogram of Q of he■ ght l and of
initia■ state.
the form whi■ ё ... do ... end or reneat
integer i
≧
■et
2,
・・・
end; and for each
Qi be the sma■ ■est subprogram containing Qi■
1
proper■ y and of the form whi■ e ..e dO ... ёnd or repeat .。 。 end.
Ilet m be the greatest number
■ such
that Qi eX■ Sts, and
■et
S be
the set of state, Of en C° rresponding to exit states of Ql, Q2'
BeCause of the symmetry in Gn' Ql may be assumed
...,Qmin(m,n)・
to represent a
■oop
partition Sn as fo・
・
passing through s(2n+1)。
Fina■ ■y, we
°WS:
(1)U_1 = Is(∞ )l.
(2)For each integer k, 0
〈
k
く n-2,
Uk = Is(2k)}
∪ ∪
(2k+1+1)2j<iく (2k+1+2)21,0≦ j≦
Is(i)￨
it(i,j)
(3)Un_1 = Sn
(2k+1+1)2n―
―∪
kE二 予
Uk・
The partition of Sぅ
is i■
・
k
n_k}
くi 〈(2k+1+2)2n「 卜, 。≦j ≦n}.
ustrated in Fig. 9。
Lig。
-17-
9・
We sha■ ■ prove that S∩ Uj ≠φfor eVery j, -1 ≦ j ≦ n_1.
Let
k = min{i l Ql represents a ■oop passing through s(2・
),
s(2i+1), s(2i+2),..。 , and s(2n+1)}.
Then not on■ y for every j∈ lk, k+1,..., n-1}but a■ so for every
j∈ 1-1, 0, 1,。
。。,k-1}the State s(23)corre,pOnds to an entry or
interior state of Ql, sinCe Ql represents a
s(2k)→
,s(2ktl)→
..。
,t(2n+1,1),...
.。
. →s(2n+1)→
■oop of the form
t(2n+1,。 )
→t(2n+1,k+1),s(2k),
ま
nd since(t(2n+1,。 ),q(2ntl,。 ),s(∞ )),(1(2n+1,1),q(2n+1,1),s(1))
, (t(2n+1,2),q(2n+1,2),s(2)),..。 , (t(2n+1,k),q(2n+1,k),s(2k 1))
are edges of Gn
Thus
S∩ U_1 ≠ φ
since Q is an n― program and hence either eXit(1), ex■ t(2),。 ..,
ex・ t(n_1)Or
exit(n)must be used in Ql to represent an edge to
the fina■ state, (t(2n+1,。 ),q(2n+1,。 ),s(∞ )).
S∩ Uj ≠ φ
for eVery j∈
And
10,1,2,。 。。, n 1}
since Ql cannOt represent a who■ e part of Uj from Coro■ ■ary 2。 2,
h(Ql)三 l and rank((Uj, En∩
Fron the above
=LE」
酬
ILEMMA 3。
■nequa■ ity
×
Uj),
s(23)))2 2.
we der■ ve a contradiction,
L堕 ￨IS∩ り
=ド ￨≦
min(町 → ≦ L∝
For every po,itiVe integer n, there exists a
7。
f■ owchart
1≦
(Uj ttΣ
which is (n+1)― convertib■ e but not
(n+1/2)― convertib■ e.
Proofe
n∈ 11,2,う
We first define f■ owcharts Hn=(sn,En'S(° )),
,。
。0・ }, as fo■ ■ows:
-18-
L}
(1)Sn
ls(1) l i iS an integer satisfying O≦ i く 2n+う
∪Is(∞ )}∪ It(1,j) l i and j are integers satisfying
2n+2≦ i<2n+う and。 ≦ j≦
〒
￨
(2)En =
1(s(0),p(0),s(1)),(s(0),p(0),も
(∞
))}
+2}
U
{(s(i),p(1),s(2i))11≦ iく
∪
1(s(i),p(i),s(2i+1))11≦ iく 2n+2}
∪
1(s(1),f(1),t(i,0)) 1 2n+2
2■
く i く 2n+う
く
一 ヽリ
U 1(t(i,j),q(i,j),s( Li/2n―
j+2」
l
〈2n+う
U l(t(i,0),q(1,0),s(0)) 1 2n+2 < i
U 1(t(i,0),q(i,0),t(1,1)12n+2
n}・
}
i く 2n+う
￨
) 1 2n+2 〈 i く 2n+う
,
0く jく nl
く
＜
く2■ +う ,
0く
i く2n+3}
＜
一
i<2nIラ ￨.
We Wi■ ■ show that
6。
う。
is (n+1)― convertib■ e but not (n+1/2)― convё rtib■ e.
We show th6 (n+1)― convertibi■ ity by inductive■ y
constructing programs Ri, 1 ≦ i く2n+3, as f。 ..ows:
(1)For each integer i, 2n+2 ≦ i く 2n+3, .et
f(i)3
Ri =
Se
■f
q(i,0)then exit(n+1)e■
■f
q(1,1)then ex■ t(n)e■ se
if q(i,n) then exit(1 )曇
each integer i, 2
(2)For
R. ―
■
lepeat
■f
く
i
p(i) then
く
λ墓
λ墓
;
;
λ 彙・
2n+2, .et
R2i
(3)Let
-19-
e■
j<nI
The f■ owchart Hn is
As an examp■ e, Hl is shown in Fig。 10。
to Gn+l in the proof 9f Lemma
一 ∪ 1(t(i,n),q(1,n),s( Li/4」 )) 1 2n+2
∪ {(t(i,n),q(i,n),s( Li/2」 )) 1 2n+2
sini■ ar
2n+2
■
。
U l(t(i,j),q(1,j),t(i,j+1))
se
R2i+1
fi end.
Rl = whi■ e p(0)19 1』 p(1)thett
The f■ owchart Hn
姜
・
ニュ Ωュユ
Rぅ
seen to be convertib■ e to the
■y
eas■
R2
(n+1)― prOgram Rl。
Now assume that Hn iS C° nvertib■ e to an (n+1/2)― program Q.
We may assume that G[Q]cOntains no inaccessib■ e state fron
initia■ state.
proof of Lemma
Ilet Qi, m and S be the same as defined in the
う
・ 6.
Because of the symmetry in Hn, Ql may be
assumed tO represent a
partition Sn
(1)U。
the
s fo■
■oop
passing through s(2n+2)e
And we
°WS:
・
=Is(0),S(1)}u{S(1)￨ラ ×2j≦ iく 4× 2j,0≦ j≦
u it(i,j)13× 2n+1≦ i<4× 2n+1,。 ≦ j≦ nl.
(2)For eaCh integer k, 1
≦
k
n+11
く n,
Uk=Is(2k)}
∪ Is(1) ￨(2k+1+1)2j ≦ i く (2k+1+2)2j, 0≦ j ≦ n_k+11
k+1,
k+1 く i く
(2k+1+2)2n―
∪ it(i,j) ￨(2k+1+1)2n―
0≦ j≦
(3)
Un=Sn-lS(∞ )}…
uk曇
n}・
l Uk・
る
The partition of S2 is i■ ■ustrated in Fig。
11。
Then we obta■ n
S∩ Uj / φ
■n
fOr every j∈
the same manner aS
Σ
j=8 1
く 一
n+l =
■n
.,n}
10,1,2,。 。
the proof of
■emma う。6。
Ujl≦ 應￨≦
Σ
j=8り ∩
min(m,n)≦
n,
Q.E.D。
contradiction.
From above seven
Thus
■emmas
we obtain the fo■ ■owing resu■ t。
- 20 -
THEOREM
う。8.
型LRコ
2]―⊇
where each
IL(Rコ
i◆
■ine
[2]pw RE[2+1/2]pw
from RE[c]to RE[d]means
[c])ン L(RE[d])
e.{L(Q) I Q
(2)L(RE[11)―
∈
RE[c]}ァ
lL(Q) I Q CRE[d]￨.
■(RE[1/21)≠ φ, L(RE[1/2])― ■(RE[1])/
IL(RE[1+1/2])― (L(RE[1/2]) UL(RE[1]))/
(■
(RE[1/2])∩
■(RE[1]))―
II(RE[0])/
Φ,
φ,
φ.
Incidenta■ ■y, Peterson et a■ .[8]shows that
L(RE[∞ ])= {L(G) I G is a f■ owchart}.
This can be sharpeneo by COns■
der■ ng
ranks of f■ owcharts.
The
proof is simi■ ar to the proof of Eggan's resu■ t [4]that giヤ e五
an incomp■ ete automaton M, we can find out a regu■ ar expression
of star height rank(M)and of
THEOREM
う。9。
■anguage
L(M).
19t G=(S,E,s。 )be a f■ owchart.
If rank(G)= 0,
then we can construct a O― program of trace set L(G)by using
on■ y
semico■ on and if― then― e■ se=fi structures; if rank(G)= 1,
then L(G)∈ L(RE[1/2])
∩
L(RE[1]); and if rank(G)〉 1, then
L(G)∈ L(RE[(rank(G)-1)+1/2]).
Proof.
An i― section is defined to be a maxュ
ma■
StrOng■ y
connected sё t T of states such that iank((S,(T× ΣXT)∩ E,s。 ))= i.
■et
n(i,G)be the number of i― sections in G, and
k(G)=
Σ
主
=Tank(G)n(i,G)IS
li.
-21-
■et
一 ・
The proof proceeds
Basis, k(G)=
■oop,
by induction on k(G).
0.
Since rank(G)=O and hence G contains
we can eas■ ■y construct a requ■ red O― program.
Induction step, k(G)〉
0。
Let K be the c■ ass of
■et
rank(G)― sections, and for any T∈ K
s(T)be a state in T such
that
rank((S, ((T-ls(T)1)XΣ X(T-ls(■ )l))∩ E, s。 ))= rank(G)-1。
We gradua■ ■y construct a requ■ red program.
In the first step we construct a required program Q[T]for
each f■ owchart くG,s(T)>, Tこ K.
EXIT[T]={s∈
S― ■
■et
￨(T× Σ×Isl)∩ E≠
φ},
■et
and
G[T]= (S,(E
―
XS)
Is(T)})× Σ
(EXIT[T]U
U{(t,f(t),s(T))
l t ∈EXttT[T]}, s。
)
where f(t)'s are new symbo■ s in lF. The f■ owchart G[T]is
ustrated in Fig。 12.
i■ ■
(1)The case that rank(G)_>_1_and_(s(■ ),g,Sl )∈
From the inductive hypothesis and
and g∈ lF.
E｀
fbr some
,1三 査
「
■ettma 305, We
can construct (rank(G)-1)― prOgr,五 s Q[sl]Of trace s9t
L(〈 G[T],sl〉
)・
From the inductive hypothesis and the fact that
f6r any t∈ EXttT[T]the f■
f■ owchart
a■ so
o■ chart くG,t>
can be reduced intO a
O' satisfying k(G')〈 k(G), for each t∈ EXttT[T]we can
construct a ((rank(G)-1)+1/2)― program R[t]of trace set
L(〈 G,t〉
).
里
鍵
Then
g;Q[Sl]1(R[t];肇
螢
)/1(t)}t∈ EXIT[T]型
is a required ((rank(G)-1)+1/2)― program Of trace set L(く G,s(T)〉 )
where Q[sl]{(R[t] ; ha■ t)/f(t)lt∈ EXttT[T]iS a program obtained
frOm Q[Sl]by rep■ acing each occurrence of f(t), t∈ EXIT[T], by
- 22 -
平
亜互
the program R[t];ha■ t.
(2)The case
that rank(G)〉 l and (S(■ ),p,S 1
for some sl, s2∈ S and p∈ P.
)∈
E
We can construct a requ■ red
program in the same manner as in the caSe (1). In fact,
repeat if p then Q[sl]1(RIt];ha■ t)/f(t)}t∈ EXttT[T]
else Q[S2]1(R[t];ha■ t)/f(t)}t∈ EXIT[T]墓
end
is a required program′ where Q[S2] iS a (rank(G)-1)― prOgram of
trace set L(〈 G[T],s2〉 )°
(3)
The caseithat rank(G)= l and (S(■ ),g,Sl )∈ E for some s
and g∈ F.
O― program
From the
■nductive
hypothes■ s we can construct
∈S
a
Q[Sl]Of trace set II(く G[T],sl〉 )by using on■ y
semico■ on and if― then― e■ se― fi structures.
From the inductive
hypothesis and the same fact as in the case (1), for each
t∈
l―
EXIT[T]we can a■ so construct a 1/2-program P[t]and a
program R[t]oF trace set L(く
G,t〉
).
Then
■S
1
■epeat g ; Q[sl]1(P[t];ha■ t)/f(t)}t∈ EXttT[T]9三 コ
a required 1/2-program of trace set IL(〈 G,s(■ )〉 ); and
■S
epeat g;Q[、 ]1は [t];彙 (1))/f(t)}t∈ EttTETi頭
■
a required l― program of trace set L(く G,s(T)>)since Q[Sl]haS
no
e/rep￡ at― ■oop.
wh■ ■
(4)
The case that rank(G)= l and (S(■ ),p,Sl), (s(T),D,s2)∈ E
for some sl, s2∈ S and p∈
IP_・
We can construct requ■ red
programs in the same manner as in the case (う
)。
In the second step we construct a required program for G。
Let
H=(Su itl,(E-ls(T)IT∈
∪
K}× Σ×S)
1(s(T),g(T),t)I T∈
- 2う ―
KI, s。 )
where t is a new state and g(T)'s are nё w symbo■ s
f■ owchart
H is i■ ■ustrated in Fig。 1ぅ O
in l「
.
The
From inductive
hypothesis and the fact that H can be reduced into a f■ owchart
Hi satisfying k(Hl)
く
k(H), we can cOnstruct a
((rank(G)-2)+1/2)― program R of trace set IL(H)。
Then
RIQ[T]/g(■ )IT∈ K
is a required ((rank(G).1)+1/2)― program Of trace set L(G)where
Q[T]ts are ((rank(G)-1)+1/2)― programs obtained in the first
Q・ EoD.
step.
ACKNOWLEDGMENTS
I w■ sh
■ntroduc■ ng
to thank Professor Teruyasu Nishizawa lor
me to the area, and the referee and Professor
Kojiro Kobayashi for reading carefu■ ■y the manuscript.
They a■ so gave me many va■ uab■ e suggestions/advices.
REFERENCES
Ro Se Cohen and
1。
」。 A.
Brzozowski, Genera■ properties of star
height of regu■ ar events,
」。 Computo
System Sci。 4 (1970),
260-280。
Ro Se Cohen, Star height of certain fami■ ies of regu■ ar
2。
events,
う.
」。 Comput.
System Sci。 4 (1970), 281-297.
Eo W. Dijkstra, GoTo statё ment considered harmfu■ , comm. ACM
ll (1968), 147-148.
…
24 -
4・
R. C. Eggan, Transition graphs ana the star he■ ght of regu■ ar
events, Michigan Math.
5・
T・
」。10 (196う
), 385-397.
Kasa■ , Trans■ atabi■ ity of f■ owcharts_■ nto whi■ e prograns,
」. Comput. System Sci。
9 (1974), 177-195。
6. S. R. Kosaraju, Ana■ ysis of structured programs,
」. Comput.
System Sci。 9 (1974), 232-255・
7。
H. F. Iledgard and M. Marcotty, A gene■ ogy of contro■
structures, Comme ACM 18 (1975), 629-6う 9.
8. W. Wo Peterson, T. Kasami and N. Tokura, On the capabi■ ities
of Whi■ e, Repeat, and Exit statements, Comm. ACM 16 (197う
50う -512.
-25-
),
Descriptive
■egends
for figures.
Fig.■ .
An examp■ e of G[Q].
Fig.2.
A State graph of rank
Fig。
.
An exp■ anation of the Fact that the rank ttf the state
3.
graph in Fig。 2 is
Fig。
■
■.
A f■ ow9hart of rank 2 in Lemma3.■
4.
.
Fig.5。
A f■ owchart in Lemma3.2.
Fig.6.
A f■ owchart in Lemma3.3.
Fig。
7.
A f■ owchart in Lemma3.4.
Fig。
8.
A f■ owchart G2 in the proof of Lemma3.6`
Fig。
9.
Fig。 ■0.
Fig.■ ■.
The partition oF S3 in the proof of Lemma3.6.
A f■ owchart H. in the proof of Lemma3.7.
The partition of S2 in the proof of Lemma3.7.
Fig.■ 2. A f■ oWChart
Fig。 ■3.
G[T]in the proof of Theorem3.9.
A f■ owchart H in the proof of Theorem3.9.
- 216 -
Fig。 ■
.
- 271 -
Fig.2.
- 28 _
Fig.3.
- 29′
―
Fig.4.
- 130-
Fig.5.
- 31 -
Fig。
6。
-32-
Fig。 7.
-33-
く2)
Fig.8.
34-
銅 ← ０
≧
…
個 動 ０
く1)
０ 金 ０
し
)
■
弊
〇 喝
Fig.9.
-35-
qC8J)
一 一
0
゛ 蜂
qG′
Fig.10.
- 36-
U0
Fig:1■
-3_7-
.
f(tt)
tt
n
EXIT[T]
t2
n
EXIT[T]
Fig。 ■2.
-38-
Fig。
13
- 39-
© Copyright 2025 ExpyDoc
