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