Hardware Reference
In-Depth Information
a
b
1
/
1
−/
0
−/
1
1
/
1
3
1
2
A
B
1
/
0
−/
0
0
/
1
0
/
0
0
/
1
1
/
0
0
/
0
4
C
D
0
/
0
Fig. 5.8
Example for Problem
5.2
;(
a
) Driving machine M
A
;(
b
) Driven machine M
B
(b) Solve the equation M
X
M
B
D
M
A
M
B
and extract the
best
implementation
of M out of the largest solution, where
best
is defined as in (a).
(c) Compare the results of (a) and (b).
5.3. Computation of Observability Don't care Sequences in a Series Topology
Consider the series composition of the FSMs M
A
(driving machine) and M
B
(driven
machine), shown in Fig.
5.8
(from [121]).
(a) Find the output sequential don't cares of M
B
to optimize M
A
, using the method
of Theorem
5.3
; optimize M
A
accordingly.
(b) Find the output sequential don't cares of M
B
to optimize M
A
, using the method
of Theorem
5.4
; optimize M
A
accordingly.
(c) Find the largest flexibility for M
A
solving the equation M
X
M
B
M
A
M
B
;
optimize M
A
accordingly.
(d) Compare the results of the different techniques.
!
5.4. Games on
-automata
In this exercise we follow the exposition in [74]). The game is played on a
deterministic !-automaton
G
D
.Q;˙
0
˙
1
;;q
0
;/, called the game automaton.
The game starts at state q
0
; player-0 plays a
0
2
˙
0
and then player-1 plays
a
1
2
˙
1
, and the game advances to state q
1
D
ı.q
0
;.
0
;
1
//, player-0 then
plays a
0
2
˙
0
, followed by player-1 playing a
1
2
˙
1
andsoonforever.The
infinite sequence
D
.
0
;
1
/.
0
;
1
/::: is a play of the game. The acceptance
condition of the game automaton is the winning condition for player-0 and
:
is
the winning condition for player-1. The language of the game automaton, L.
G
/ is
the game language. A play
2
.˙
0
˙
1
/
!
is a win for player-0 if
2
L.
G
/, i.e., the
set of states visited infinitely often by satisfies the winning condition. Otherwise,
the play is a win for player-1, whose winning condition is
:
.InaBuchi game,
player-1's winning condition is a co-Buchi winning condition.
Consider the Buchi game shown in Fig.
5.9
a (from [74]).
(a) Show a win play for player 1 and a win play for player-0.
Solution.
The play .b;1/.b;1/.a;0/
!
is a win for player-1, whereas the play .b;1/
!
is a
win for player-0.
Search WWH ::
Custom Search