Hardware Reference
In-Depth Information
representations can be used, both in making computations more efficient and in
allowing larger problems to be solved. The monolithic transition and output relations
will never be constructed. With a partitioned representation, the functionalities of
the automata are represented as sets of functions,
fT
k
.i; cs/g
and
fO
k
.i; cs/g
.All
Boolean operations are performed using these functions. It will be shown that
image computation plays the key role in the manipulations involving partitioned
representations, and hence a decade of research resulting in techniques to speed up
image computations [30, 120, 137] can be used.
4
7.2
Computation Algorithms
This section describes how to perform operations on the automata, required for
language equation solving, when the partitioned representations are available. The
main algorithm for the computation, using either monolithic or partitioned represen-
tations, was described in Chap. 3, Sect. 3.3. In this section, we show that, given the
partitioned representations, all the steps are essentially embedded into a modified
determinization procedure, so that there is no need to perform the completion and
variable hiding operations as separate steps. However for generality, we show first
how these operations can be performed independently of determinization.
7.2.1
Elementary Operations Using Partitioned Representations
In the application to the problem where the topology is as shown in Fig.
7.1
,we
have partitions for
F
(which has both
u
and
o
as outputs):
fT
j
T
F
.i;
v
;cs
F
;ns
j
T
F
/g; fU
j
U
.i;
v
;
u
j
U
;cs
F
/g; fO
j
O
F
.i;
v
;o
j
O
F
;cs
F
/g
and partitions for
S
:
fT
j
T
S
.i; cs
S
;ns
j
T
S
/g; fO
j
O
S
.i; o
j
O
S
;cs
S
/g:
7.2.1.1
Completion
An automaton derived from an FSM is completed by interpreting the complement
of its output relation as the condition for a transition from the current state to
4
It is beyond the scope of this topic to describe all these advancements; we experimented
extensively with implementing most of proposed techniques and chose the methods that we
observed to be most efficient.
Search WWH ::
Custom Search