Hardware Reference
In-Depth Information
.A " O \f ˛ g " I
\ C " U / # U O
D;, by Prop :2:3.d/
since f ˛ g " I
D .. f ˛ g " I / # U O / " I
. f ˛ g " I / # U O
\ .A " O \ C " U / # U O
D;, by Prop :2:1.a/. f ˛ g " I / # U O
Df ˛ g
f ˛ g\ .A " O \ C " U / # U O
D;,
˛ 62 .A " O \ C " U / # U O
,
˛ 2 .A " O \ C " U / # U O
,
˛ 2 A C
Therefore the largest solution of the language equation A X
C is given by the
language
S
D A C:
(2.3)
t
Coro llary 2 .13. A language B over alphabet U O is a solution of A X
C iff
B
A C .
Equations over languages can be extended to topologies with more than two
components, as the one in Fig. 2.3 , whose largest solution is given by:
S
D ..A " Z O
\ C " I U V / \ S " V Z / # U V Z
(see [150]).
Let S be the largest solution of the equation A X C . It is of interest
to investigate subsets of S that satisfy some further properties, e.g., being prefix-
closed, progressive, etc.
If S is prefix-closed then S is the largest prefix-closed solution of the equation.
However, not every non-empty subset of S inherits the feature of being prefix-
closed. If S is not prefix-closed, then denote by S Pref
the set obtained from S by
deleting each string that has a prefix not in S .
Proposition 2.14. If S Pref
¤; ,then S Pref
is the largest prefix-closed solution of
the equation A X
C .
If S Pref
D; , then the equation A X C has no prefix-closed solution.
If the language S does not include the empty string, then A X
C has no
prefix-closed solution.
If S is U -progressive (S is a language over alphabet U O), then S is the largest
U -progressive solution of the equation. However, not each non-empty subset of S
Search WWH ::




Custom Search