Hardware Reference
In-Depth Information
composition topology with two components, we will assume that I; O are external
alphabets, and U is an internal alphabet; however, U or a part of it can be made
observable externally, if needed.
Comment. The definition of parallel composition justifies a-posteriori why the
expansions operator e is not defined to be a substitution, i.e., e./ ¤f g . Consider a
language A D ..i o/ ? . uv / ? / ? and a language B whatsoever. The parallel composition
of A and B should be equal to the language .i o/ ? , because B should not affect the
I
[ O behavior of A. Now suppose B
Df g . If we would define e./ Df g ,then
D ..i o/ ? . uv / ? / ?
D ..i o/ ? . uv / ? / ?
it would be A \ B * I [ O
\f g * I [ O
\f gDf g ;
[ O/ ? then it is A \ B * I [ O
D ..i o/ ? . uv / ? / ?
if we define instead f g * I [ O
D .I
\
D .i o/ ? , that is the expected result.
Va r i a n t s o f synchronous composition are introduced in [25] as product ,
(with the comment sometimes called completely synchronous composition ), and
in [82] as synchronous parallel composition , ˝ .Variantsof parallel composition
are introduced in [25] as parallel composition , k (with the comment often called
synchronous composition ),andin[82]as interleaving parallel composition , k ;the
same operator was called asynchronous composition in [107]. These definitions
were usually introduced for regular languages; actually they were more commonly
given for finite automata.
It has also been noticed by Kurshan [82] and Arnold [2] that asynchronous
systems can also be modeled with the synchronous interpretation, using null
transitions to keep a transition system in the same state for an arbitrary period of
time. Kurshan [82] observes that: “While synchronous product often is thought to be
a simple -even uninteresting!- type of coordination, it can be shown that, through use
of nondeterminism, this conceptually simple coordination serves to model the most
general 'asynchronous' coordination, i.e., where processes progress at arbitrary
rates relative to one another. In fact the 'interleaving' model, the most common
model for asynchrony in the software community, can be viewed as a special case
of this synchronous product.” A technical discussion can be found in [83], but the
transformation is not straightforward in practice, and the matter requires further
investigation.
In the sequel it will be useful to extend some properties of languages to
the composition of two languages. As examples, we illustrate the extension for
I -progressive and I ? O-progressive languages.
D ..i o/ ? . uv / ? / ?
\ .i [ o/ ?
f g * I [ O
Definition 2.1.16. Given a language A over alphabet I
U , a language B over
alphabet U
O is A -compositionally I -progressive if the language L
D
A " O
\
B " I
over alphabet X
D
I
U
O is I -progressive, i.e., 8 i
2
I
9 . u ;o/ 2
U
OŒ˛ 2 L ) ˛.i; u ;o/ 2 L.
Definition 2.1.17. Given a language A over alphabet I
[
U , a language B
[ O is A -compositionally IU ? O -progressive if the language
over alphabet U
.I U ? O/ ?
L D A " O
\
B " I
over alphabet X
D
I
[
U
[
O (I , U and O
pairwise disjoint) is IU ? O-progressive, i.e.,
9 ˇ 2 U ?
8 i 2 I
9 o 2 OŒ˛ 2 L
)
˛iˇo 2
L.
Search WWH ::




Custom Search