Equations Over !-Automata - The Unknown Component Problem: Theory and Applications - page 77

Fig. 4.5 Topology for
Problem 4.4 and Problem 4.5

I U

C X

S

C ! D 4.4. Given the topology shown in Fig. 4.5 , consider the ! -regular languages

.i 1 u 1 C i 1 u 2 C i 2 u 1 C i 2 u 2 / ? .i 1 u 1 / ! C .i 2 u 2 / ! and S ! D .i 1 C i 2 / ? i 1

.

C ! ! X ! S ! is the limit

Check whether the largest solution of the equation

.C ! / X .S ! /

of the largest solution of the equation Pref Pref . Notice that the

former is a parallel equation over -regular languages and the latter is a parallel

equation over regular languages (obtained as finite prefixes of

!

! -languages).

C ! D 4.5. Given the topology shown in Fig. 4.5 , consider the ! -regular languages

S ! D .i 1 C i 2 / ! .
Check whether the largest solution of the equation

u 1 C u 2 // ! and ..i 1 C i 2 /.

C ! ˘ ! X ! S ! is the limit

.C ! / ˘ X .S ! /

of the largest solution of the equation Pref Pref . Notice that the

former is a parallel equation over -regular languages and the latter is a parallel

equation over regular languages (obtained as finite prefixes of

!

! -languages).