Electronic Journal of Graph Theory and Applications 3 .
, 162Ae181 On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boodea,c .
Hajo Broersmab .
Jan F.
Broeninka Robotics and Mechatronics.
Faculty EEMCS.
University of Twente The Netherlands b Formal Methods and Tools.
Faculty EEMCS.
University of Twente The Netherlands c Department of Computer Engineering.
InHolland University of Applied Science The Netherlands boode@utwente.
nl, h.
broersma@utwente.
nl, j.
broenink@utwente.
Abstract In this paper we introduce and study a directed tree problem motivated by a new graph product that we have recently introduced and analysed in two conference contributions in the context of periodic real-time processes.
While the two conference papers were focussing more on the applications, here we mainly deal with the graph theoretical and computational complexity issues.
We show that the directed tree problem is NP-complete and present and compare several heuristics for this Keywords: finite deterministic directed acyclic labelled multi-graphs, vertex removing synchronised graph product, target trees, periodic real-time systems Mathematics Subject Classification : 68R10 DOI: 10.
5614/ejgta.
Received: 24 April 2015.
Revised: 12 July 2015.
Accepted: 22 July 2015.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Introduction In this paper we give a detailed discussion of a new graph product that we have recently introduced and analysed in two conference contributions .
, .
While the two conference papers were focussing more on the applications, here we mainly deal with the graph theoretical and computational complexity issues.
Here we also introduce a new decision problem on directed trees.
It is motivated by the applications from the context of periodic real-time processes, and it is based on the new graph product.
However, this tree problem can be based on any graph product .
r, in fact on any binary operatio.
Therefore we introduce it now, before going into the technical details of the particular application that motivated it.
A directed tree problem Let T be a tree, so a connected acyclic .
We orient the tree by replacing each of the edges of T by an arc, in precisely one of the two directions, so we obtain an acyclic weakly connected directed graph, which we call a ditree.
A source in a ditree is a vertex with in-degree 0.
This is usually referred to as a leaf.
A sink in a ditree is a vertex with out-degree 0.
We call such a vertex a target of the ditree.
We say that a ditree D is a target tree if D has the following properties.
Each vertex except for the leaves has in-degree 2.
each vertex except for one has out-degree 1.
unique vertex of D .
f D has more than one verte.
with in-degree 2 and out-degree 0 is called the target of D.
In our later application, the target v of a target tree D will be interpreted as a special product of two graphs .
o be defined in the seque.
that are represented by the two in-neighbours u and w of v in D.
If u is a target vertex of D v, then analogously u can be interpreted as the product of two graphs, etc.
On the other hand, each of the ways to compute the product of the graphs G1 , .
Gn can be represented as a target tree on n leaves and n 1 internal vertices .
on-leave.
As an example, in Figure 1 we depicted a target tree corresponding to a solution of one of the heuristics called MNSA in the sequel.
The leaves at the top represent graphs corresponding to processes, and the internal vertices represent products, e.
, the internal vertex numbered 1 represents the product of G16 and G2 , the vertex numbered 8 represents the product of this new graph with G1 , etc.
, and the vertex numbered 15 represents the product of the graphs represented by the vertices numbered 14 and 13, respectively.
For the MNSA heuristic the order in which the products of the graphs are calculated are given by the numbers of the internal vertices.
So the vertex numbered 1 represents the first product, the vertex numbered 2 represents the second product, and so on.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Figure 1.
Target tree representing a solution of the MNSA heuristic.
In the sequel we will introduce two graph parameters ` and M that represent the processing time and memory occupancy of the graph corresponding to .
he execution o.
a process, and we will define how to compute the value of these parameters for the product of two graphs.
As we will see, for the product of two graphs G1 and G2 , the `-value is usually lower than the sum of the two `-values of G1 and G2 .
f the corresponding processes synchronise on certain action.
, whereas the M -value of the product is usually larger than the sum of the two M -values.
If for the execution of a number of processes on one processor we have a limited memory capacity and a deadline to make, this leads to a decision problem: can we combine the processes in such a way that we can execute them on the processor, meeting the deadline and memory restrictions? Turning back to the target tree representation, every leaf and every internal vertex of the target tree has an associated `-value and M -value, and corresponds to one process .
he leave.
or a subset .
of more than one process .
he internal vertice.
Each combination of all the processes into several subsets .
in which each process occurs in precisely one subset, is represented by a number of leaves .
ossibly zer.
and a number of internal vertices .
ossibly zer.
, so that all the chosen vertices of the target tree cover all the leaves.
Here a chosen vertex v of the target tree is said to cover all the vertices in all the directed paths from the leaves terminating in v .
, v covers all vertices in the .
ditree with target vertex v that results after deleting the arc which is directed away from .
We call a set of vertices that covers all the leaves of a target tree D precisely once a leaf cover of D.
As an example, the target vertex is a leaf cover of cardinality 1 and the set of leaves is a leaf cover of cardinality n.
Every leaf cover also has an associated `-value and M -value .
iven by the combination of processes it represents, in a way we will explain late.
We say that a target tree D on n leaves is feasible if it admits a leaf cover for which the associated `-value and M -value are within the deadline and memory restrictions, so the corresponding combination of processes .
orresponding to the sets of products of the graphs G1 , .
Gn associated with the n leave.
can be executed correctly on the processor.
The above question translates into the following decision problem: given n graphs G1 , .
Gn .
epresenting n processe.
, can we construct a feasible target tree D on n leaves .
epresenting the graph.
? We call this the Synchronised Product Decision Problem.
We will show that this decision problem is NP-complete.
In fact, for obvious reasons, we will also be interested in a solution, so a target tree together with a leaf cover that provides a YES answer.
If the leaf cover contains more than one vertex .
o if it is not the target vertex of the target tre.
, the solution in fact corresponds to a forest of target trees for mutually disjoint subsets On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
of the n leaves.
General introduction We continue with a general introduction that also contains the motivation for introducing the new graph product.
The software of applications of embedded control systems is often designed using a General Purpose Computing System (GPCS).
Such a GPCS often has more processing power and memory available than the embedded control system.
The embedded control system is the target system on which the software will run.
The hardware of the target system can be very limited with respect to available memory and processing power.
If such a target system has to be periodic hard real-time, it has deadlines D for its processes to fulfil the timing requirements, together with memory M to store the data of these processes.
Periodic real-time robotic applications can be designed using formal methods like process algebras .
, .
While designing, the designer distributes the required behaviour over up to several hundreds of processes.
These processes very often synchronise over actions, e.
to assert that a set of processes will be ready to start executing at the same time.
Due to this synchronisation the application suffers from a considerable overhead related to extra context switches.
In .
we have defined periodic real-time processes as finite deterministic directed acyclic labelled multi-graphs, where these graphs are closely related to state transition systems.
The .
arcs in such a graph represent actions in a periodic real-time process.
The label represents the name of the action and its duration.
As, per action, there is a context switch, the longest path in such a graph is the most time consuming with respect to the context switch and therefore the worst We introduced in .
a Vertex-Removing Synchronised Product (VRSP) to reduce the number of context switches.
VRSP is based on the synchronised product of WoOhrle and Thomas .
, which is used in model-checking synchronised products of infinite transition systems.
The VRSP reduces the number of context switches and realises a performance gain for periodic real-time applications.
This is achieved by .
combining two graphs representing two processes that synchronise over some action.
This combined graph represents a process that will have only one context switch per synchronising action, where the two processes each have a context switch per synchronising action .
Using the VRSP, the set of graphs is transformed into a new set of graphs.
For this new set of graphs, either the processes that they represent meet their deadline and fit into the available memory, or there is no set of processes with strong-bisimular behaviour with respect to the original set of processes that will do so.
To be able to compose the set of graphs in a meaningful manner, the VRSP has to be idempotent, commutative and associative.
We have defined the notion of consistency for which VRSP is Consistency implies that the processes represented by the graphs are deadlock free in the sense that each process must reach the state where for the process no more actions are specified.
In process algebraic terms this is also a deadlock, which we exclude from our definition.
Furthermore we investigate the number of leaf covers in the set of target trees that G can generate under VRSP.
This number is given by the Bell number.
We introduce a Synchronised Product Decision Problem (SPDP), which describes a solution On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
out of the exponential number of leaf covers in the set of target trees and show that it is NPcomplete.
We have given in .
heuristics that will calculate in polynomial time a leaf cover under VRSP.
Each of the heuristics that we have investigated generates one target tree.
These heuristics give no guarantee that the requirements will be fulfilled.
In this paper we give another heuristic based on the memory occupancy of the set of graphs.
We compare this heuristic with the heuristics given in .
The terminology is given in Section 2.
From the definition of consistency we derive in Section 2 corollaries that show that the VRSP of two consistent graphs is deadlock free.
In Section 3 we show that the VRSP has an identity graph I, that it is commutative, idem-potent and .
or consistent component.
In Section 4 we give a tree representation of all the combinations of graphs representing a process specification with respect to the summation over the VRSPs.
Section 5 we define the Synchronised Product Decision Problem (SPDP) for the tree representation of Section 4 and show that it is NP-complete.
A heuristic based on the memory occupancy is given in Section 6.
We finish with the conclusions in Section 7.
The pseudo-code of the heuristics is given in the Appendix.
Terminology We use Bondy and Murty .
Hammack et al.
Hell and NesUetrUil .
and Milner .
for terminology and notation on graphs and processes not defined here and consider finite labelled weighted deterministic directed acyclic multi-graphs only.
In order to make this paper self contained as far as the new terminology is concerned, we repeat the notions as they were introduced in .
for convenience.
So, if we use G to denote a graph, we mean a labelled weighted deterministic directed acyclic multi-graph.
Thus G consists of a set of vertices V , a multi-set of arcs A, and a surjective mapping : A yc L, where L is a set of label pairs.
G is also denoted as G pV.
Lq.
An arc a P A which is directed from a vertex v P V .
he tai.
to a vertex w P V .
he hea.
will usually be denoted as a vw.
For each arc a P A, paq P L consists of a pair plpaq, tpaqq, where lpaq is a string representing an action and tpaq is a positive real number representing the worst-case execution time of the action represented by lpaq.
If an arc has multiplicity k A 1, then all copies have different label pairs, otherwise we could replace two copies of an arc with identical label pairs by one arc, because they represent exactly the same action at the same stage of the process.
If two arcs a, b P A have label pairs paq plpaq, tpaqq and pbq plpbq, tpbqq such that lpaq lpbq, then this implies that tpaq tpbq.
this follows since lpaq lpbq means that the arcs a and b represent the same action at different stages of a process.
The identity graph consists of one vertex and no arcs .
nd therefore no label pair.
and is denoted as I, so I ptiu.
Hq.
The empty graph consists of no vertices and no arcs and is denoted as GH , so GH pH.
Hq.
A graph G is called deterministic if its arcs have the following property.
If vi wi , vj wj P A with wi wj have identical label pairs pvi wi q pvj wj q, then vi vj .
This is equivalent to determinism in the set of processes that represents the graph G.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
A directed path in G is a sequence of distinct vertices v1 v2 .
vk of G such that vj vj 1 P A for j 1, .
, k 1.
The length of a directed path v1 v2 .
vk is defined as A tpvi vi 1 q.
A directed cycle is a directed path v1 v2 .
vk together with an additional arc vk v1 , and is denoted by v1 v2 .
vk v1 .
G is called acyclic if G does not contain any directed cycles.
We consider finite directed acyclic graphs.
G, only.
In general, such a graph consists of several components, where each component.
Gi , is weakly connected .
all vertices are connected by sequences of arcs, ignoring arc direction.
and corresponds to one sequential process.
For such components, `pGi q is defined as the maximum length taken over all directed paths in Gi .
For the whole graph, which corresponds to a parallel set of sequential processes that must each run to completion, the maximum path length, `pGq, is the sum of all the individual `pGi q, so `pGq An `pGi q.
For a component Gi we denote its set of vertices V pGi q as Vi , its multi-set of arcs ApGi q as Ai and its set of label pairs LpGi q as Li .
If G represents one process, then mpGq represents the amount of memory needed to store the related data-structures.
We consider finite graphs only, therefore mpGq is finite.
Usually G consists of several components, where each component Gi of G corresponds to one process.
Then mpGi q represents the amount of memory needed to store the related data-structures for Gi .
An arc ai with label pair pai q in component Gi is a synchronising arc with respect to component Gj , if and only if there exists an arc aj P Aj with label pair paj q such that pai q paj q.
The source of a component Gi is the set of vertices tvi .
i P Vi u with d Gi pvi q 0.
The sink of a component Gi is the set of vertices tvi .
i P Vi u with dGi pvi q 0.
A full path in a graph G is a path from the source to the sink of the component Gi .
For each Gi we define S0i to denote the set of vertices with in-degree 0 in Gi .
S1i the set of vertices with in-degree 0 in the graph obtained from Gi by deleting the vertices of S0i and all arcs with tails in S0i , and so on, until the final set Stii contains the remaining vertices with in-degree 0 and there are no arcs in the remaining component.
As in the acyclic ordering, this ordering implies that arcs of Gi can only exist from a vertex in Sji1 to a vertex in Sji2 if j1 j2 .
If a vertex v P Vi is in the set Sji in the above ordering, we also say that v is at level j in Gi .
Whenever G consists of components G1 , .
Gn this is denoted as G An Gi .
The union of two vertex-disjoint graphs Gi and Gj is the graph consisting of the union of the vertex sets of Gi and Gj together with all the multi-arcs and label pairs defined by Gi and Gj .
Graph Products The Cartesian product Gi Gj of Gi and Gj is defined as the multi-graph on vertex set Vi,j Vi Vj .
he Cartesian product of the vertex sets of Gi and Gj ) with two types of arcs.
Arcs of type 1 .
are between pairs pvi , vj q P Vi,j and pwi , wj q P Vi,j with vi wi P Ai and vj wj .
ith vi wi and vj wj P Aj ), so arcs of type 1 and 2 correspond to arcs of Gi and Gj , respectively.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
This definition of the Cartesian product is an extension of the Cartesian product in .
V pGi Gj q tpvi , vj .
vi P Vi and vj P Vj u ApGi Gj q tpvi , vj qpvi1 , vj1 .
vi vi1 ^ vj vj1 P Aj , or vi vi1 P Ai ^ vj vj1 u LpGi Gj q = tppvi, vj qpvi1 , vj1 q.
vivi1 P Ai ^ vj vj1 ^ ppvi, vj qpvi1 , vj1 qq pvi, vi1 qu tppvi, vj qpvi1 , vj1 q.
vj vj1 P Aj ^ vi vi1 ^ ppvi, vj qpvi1 , vj1 qq pvj , vj1 qu For k Au 3, the Cartesian product G1 G2 .
Gk is defined recursively as ppG1 G2 q .
q Gk .
In the sequel the Cartesian product Gi Gj is denoted as Gi lGj .
a notation we adopted from .
The synchronised product of Gi and Gj is constructed in two stages.
Firstly, the intermediate stage, denoted as Gi b Gj of Gi and Gj , is defined as the graph on vertex set Vi,j Vi Vj with two types of arcs:
- Arcs of type 1 are between pairs pvi , vj q P Vi,j and pwi , wj q P Vi,j with vi wi P Ai , vj wj and pvi wi q R Lj .
ith vi wi and vj wj P Aj , and pvj wj q R Li ).
These arcs of Gi b Gj are called asynchronous arcs, and the set of these arcs is denoted as Aai,j .
Thus.
Aai,j tpvi , vj qpvi1 , vj1 .
vi , vi1 P Vi , vj , vj1 P Vj with vi vi1 P Ai , vj vj1 and pvi vi1 q R Lj , or vj vj1 P Aj , vi vi1 and pvj vj1 q R Li u - Arcs of type 2 are between pairs pvi , vj q P Vi,j and pwi , wj q P Vi,j with vi wi P Ai , vj wj P Aj and pvi wi q pvj wj q.
These arcs of Gi b Gj are called synchronous arcs, and the set of these arcs is denoted as Asi,j .
Thus.
Asi,j tpvi , vj qpvi1 .
Ai vj1 .
vi , vi1 P Vi , vj , vj1 P Vj with vi vi1 P Ai , vj vj1 P Aj and pvi vi1 q pvj vj1 qu and Ai,j Aai,j Asi,j .
The intermediate stage of the synchronised product is similar to the synchronised product defined by WoOhrle and Thomas .
Secondly, all vertices at level 0 in the intermediate stage that are at level A 0 in Gi lGj are removed, together with all the arcs that have one of these vertices as a tail.
This is then repeated in the newly obtained graph, and so on, until there are no more vertices at level 0 in the current graph that are at level A 0 in Gi lGj .
The resulting graph is called the Vertex Removing Synchronised Product (VRSP) of Gi and Gj , denoted as Gi n Gj .
VRSP is also called the synchronised product if no confusion can arise.
For k Au 3, the VRSP G1 n G2 n .
n Gk is defined recursively as ppG1 n G2q n .
q n Gk .
The summation over products of components is denoted as Gn Ii1 Ii2 H, i1 i2 .
Ii t1, , nu.
Ak n Gj .
Ii AE t1, , nu.
P i 1 j Ii Remark 2.
The asynchronous arcs are created in a similar fashion as the arcs in the Cartesian Remark 2.
A pair of synchronous arcs from G1 and G2 are replaced by one arc in G1 b G2 .
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Graph-morphisms A homomorphism f of Gi to Gj , f : Gi yc Gj , is a mapping f : Vi yc Vj such that f pv qf pwq P Aj whenever vw P Ai and pf pv qf pwqq pvwq.
A weak-homomorphism f : Gi yc Gj , is a map f : Vi yc Vj for which vw P Ai implies f pv qf pwq P Aj and pf pv qf pwqq pvwq, or f pv q f pwq.
f Induces a mapping from Ai to Aj , which is denoted by f .
Remark 2.
Label pairs have been added to the definition of a weak-homomorphism as defined by Hammack et al.
Components Gi .
Gj are isomorphic, denoted Gi Gj if there exists a bijection I from Vi to Vj , such that vi wi P Ai with pvi wi q pk, lq y Ipvi qIpwi q P Aj with pIpvi qIpwi qq pk, lq and pvi wi q pIpvi qIpwi qq.
Components Gi and Gj are consistent if and only if the following two requirements apply:
There exist weak-homomorphisms Ai and Aj such that Ai : Gi n Gj yc G1i and Aj : Gi n Gj yc G1j implies Gi G1i and Gj G1j .
Gi nGj pV q Vi Vj and Gi nGj pV q Vi Vj .
Where Vi tvi .
i P Vi ^d Gi pvi q 0u.
Vi tvi .
i P Vi ^ dGi pvi q 0u.
Corollary 2.
Let components G1 and G2 be consistent.
For every full path of G1 n G2 there exists a full path of G1 .
ossibly after skipping arcs of the path in G1 n G2 that then belong to G2 ) and there exists a full path of G2 .
ossibly after skipping arcs of the path in G1 n G2 that then belong to G1 .
the skipped arcs are asynchronous arcs.
Proof.
Because G1 and G2 are consistent there exist weak-homomorphisms A1 and A2 such that A1 : G1 n G2 yc G11 and A2 : G1 n G2 yc G12 implies G1 G11 and G2 G12 .
These weak-homomorphisms A1 and A2 have the property that for all full paths w1 w2 .
in G1 n G2 and for every arc wi wi 1 there is an arc uj uj 1 in A1 with pwi wi 1 q puj uj 1 q or there is an arc vk vk 1 in A2 with pwi wi 1 q pvk vk 1 q.
Such an arc may exist for both weak-homomorphisms A1 and A2 , so for A1 pwi wi 1 q uj uj 1 and A2 pwi wi 1 q vk vk 1 with pwi wi 1 q pvk vk 1 q puj u Aij 1q.
Let wi , wi 1 R G1 nG2 pV q G1 nG2 pV q.
If for an arc wi wi 1 with pwi wi 1 q a.
A1 maps wi and wi 1 to uj then uj uj 1 with puj uj 1 q a is not in A1 .
By repetition, skipping arcs that map by A2 to A2 , there must be a wj wj 1 with A1 pwj q uj .
A1 pwj 1 q uj 1 and uj uj 1 P A1 and pwj wj 1 q puj uj 1 q, because otherwise uj P V and there is a vertex vx P G2 pV q for which puj , vxq P G1 n G2pV q.
Analogously, by repetition, skipping arcs that map by A2 to A2, there must be a wj 1 wj with A1 pwj 1 q uj 1 .
A1 pwj q uj and uj 1 uj P A1 and pwj 1 wj q puj 1 uj q, because otherwise uj P V and there is a vertex vx P G2 pV q for which puj , vx q P G1 n G2 pV q.
Vice versa for A2 and arcs that are not in G2 .
From this it follows that all paths w2 w3 .
wn1 by A1 (A2 ) are mapped to some path u2 u3 .
2 v3 .
vl ).
But A1 (A2 ) maps w1 to u1 .
1 ) and wn to uk 1 .
l 1 ) and therefore u1 u2 .
1 v2 .
vl 1 ) is a full path of G1 (G2 ).
Corollary 2.
Let components G1 and G2 be consistent.
For every full path in G1 pG2 q there exists a full path in G1 n G2 .
osibly after skipping arcs of the path in G1 n G2 that then belong to G2 pG1 .
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Proof.
Because A1 (A2 ) maps G1 n G2 to G11 G1 (G12 G2 ) together with Corollary 2.
1, for every full path in G1 (G2 ) there exists a full path in G1 n G2 .
Corollary 2.
If components G1 and G2 are consistent, then G1 n G2 is deadlock free.
Proof.
Follows directly from Corollary 2.
1 and Corollary 2.
Both requirements of consistency are necessary to exclude a deadlock in the processes represented by the components.
The first requirement of consistency ensures that all paths in the components are .
pto isomorphis.
also in the VRSP of these components.
An example that violates this requirement is given in Figure 2.
Figure 2.
Inconsistent components Gi and Gj violating requirement 1.
The second requirement of consistency ensures that for two components Gi .
Gj , for all paths in component Gi there is a path in the Gi n Gj .
ossibly after skipping arcs that belong to Gj ) and vice versa.
A path in one component containing arcs with label pairs in opposite order as a path in the other component is avoided.
An example that violates this requirement is given in Figure 3.
Note that both examples satisfy only one of the two requirements of consistency.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Figure 3.
Inconsistent components Gi and Gj violating requirement 2.
An example of consistent components is given in Figure 4, where we have the components G1 ptv1 , v2 , v3 , v4 u, tv1 v2 , v2 v3 , v3 v4 u, tpv1 v2 q a, pv2 v3 q b, pv3 v4 q cuq.
G2 ptw1 , w2 , w3 u, tw1 w2 , w2 w3 u, tpw1 w2 q a, pw2 w3 q cuq.
G1 n G2 ptpv1 , w1 q, pv2 , w2 q, pv3 , w2 q, pv4 , w3 qu, tpv1 , w1 qpv2 , w2 q, pv2 , w2 q pv3 , w2 q, pv3 , w2 q pv4, w3qu, tppv1, w1qpv2, w2qq a, ppv2, w2qpv3, w2qq b, ppv3, w2q pv4, w3qq cuq.
Then we have the weak-homomorphisms A1 : pv1 , w1 q yc v1 , pv2 , w2 q yc v2 , pv3 , w2 q yc v3 , pv4 , w3 q yc v4 A2 : pv1 , w1 q yc w1 , pv2 , w2 q yc w2 , pv3 , w2 q yc w2 , pv4 , w3 q yc w3 Remark 2.
A1 is also a homomorphism.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
1,w.
3,w.
2,w.
4,w.
Figure 4.
Weak-homomorphisms A1 from G1 n G2 to G1 and A2 from G1 n G2 to G2 Basic Properties of the VRSP We start with propositions on identity, the empty graph, commutativity and idem-potency, which are easy to prove.
We use deterministic graphs, because of the required idem-potency of An example of a non-deterministic graph is given in Figure 5.
Ni .
1,v.
G1 G1 .
0,v.
1,v.
2,v.
2,v.
G1 = G1 Figure 5.
Non-deterministic and not idem-potent component.
We state the six propositions without proof.
Let G be a finite directed acyclic labelled multi-graph.
Proposition 3.
G n I G.
Proposition 3.
GH G.
Proposition 3.
G n GH GH .
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Let G1 .
G2 and G3 be deterministic finite directed acyclic labelled multi-graphs, in which all components are pairwise consistent in Proposition 3.
4 through 3.
Note that G1 .
G2 and G3 are pairwise vertex disjoint.
This follows directly from G1 .
G2 and G3 being components.
Proposition 3.
The synchronised product of G1 and G2 is commutative up to isomorphism.
G1 n G2 G2 n G1 .
Proposition 3.
The synchronised product of G1 and G1 .
G1 n G1 is idem-potent up to isomorphism.
So G1 n G1 G1 .
Note that an arc ui vi P ApG1 q and an arc uj vj P ApG1 q, with pui vi q puj vj q, i j, pui , uj q has level A 0 in G1 lG1 and level 0 in G1 b G1 .
ossibly after removing vertices with the same conditio.
and therefore pui , uj q .
nd consequently pui , uj qpvi , vj .
will be removed.
Proposition 3.
The addition over G1 and G1 .
G1 G1 G1 .
G1 is idem-potent.
So G1 Propositions 3.
1, 3.
3, 3.
4 and 3.
5 follow directly from the definition of the synchronised product.
The synchronised product does not distribute over the addition up to isomorphism.
So G1 n pG2 G3q pG1 n G2q pG1 n G3q.
This follows from the example shown in Figure 6.
The set of label pairs used by VRSP are restricted to the label pairs in the components that are multiplied.
G2 G1
(G2 G.
Figure 6.
n does not distribute over .
The propositions 3.
1 through 3.
3 are necessary for Theorem 3.
Theorem 3.
Let G be a finite deterministic directed acyclic labelled multi-graph, consisting of components G1 .
G2 .
G3 , where G1 .
G2 .
G3 .
G1 n G2 .
G1 n G3 and G2 n G3 are pairwise consistent.
Then the synchronised product is associative up to isomorphism.
In particular, given components G1 .
G2 , and G3 , the map Ippu1 , u2 q, u3 q pu1 , pu2 , u3 qq is an isomorphism from pG1 n G2 q n G3 to G1 n pG2 n G3 q.
Proof.
Assume there is a full path x1 .
xm in G1 n pG2 n G3 q and any full path t1 .
to in pG1 n G2q n G3, such that x1 .
xm t1 .
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Because G1 and G2 n G3 are consistent, there exist weak-homomorphisms A1 and A2 with a full path u1 .
ui in G1 , where A1 px1 .
xm q u1 .
ui and a full path y1 .
yl in G2 n G3 , where A2 px1 .
xm q y1 .
Then there exist weak-homomorphisms A3 and A4 with a full path vj in G2 , where A3 py1 .
yl q v1 .
vj and a full path w1 .
wk in G3 , where A4 py1 .
yl q But, due to Corollary 2.
2, because u1 .
ui is a full path in G1 and v1 .
vj is a full path in G2 , there is a full path z1 .
zn in G1 n G2 .
For these two full paths w1 .
zk and z1 .
zn there is a full path t1 .
to in pG1 n G2 q n G3 , contradicting our assumption.
Thus for every full path in G1 npG2 nG3 q there exists a full path in pG1 nG2 qnG3 .
Analogously for every full path in pG1 n G2 q n G3 there exists a full path in G1 n pG2 n G3 q.
Therefore G1 n pG2 n G3 q pG1 n G2 q n G3 .
Figure 7 shows the weak-homomorphisms Ai from a set of full paths of the VRSP of two components to these components.
Associativity is necessary to calculate the number of possible leaf covers of a target tree D by the Bell number, given in Section 4.
G1 (G2
(G1 G.
Figure 7.
Weak-homomorphisms from sets of full paths to sets of full paths.
Feasibility of a Target Tree Let D be a target tree.
Recall that the leaves of D represent processes as specified by the designer of the periodic real-time application.
A leaf cover of D is a solution if it represents a set of .
processes that meet their deadlines and fit in the available memory.
The On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
cardinalityof the set of leaf covers of all target trees over n leaves is given by the Bell number , 1 n 1 Bk .
B0 1, .
Bn k 0 Because for two isomorphic target trees the order in which VRSP is executed over components can be different, the synchronised product of the components of the graph G has to be associative (G1 n pG2 n G3 q pG1 n G2 q n G3 ) and commutative (G1 n G2 G2 n G1 ).
For this reason the components in the graph G have to be consistent.
Moreover each product of components has to be consistent with the other remaining components.
Figure 8 gives an example where G1 .
G2 and G3 are pairwise consistent.
But G1 n G2 and G3 are not pairwise consistent.
Figure 8.
VRSP does not preserve consistency.
Therefore a heuristic has to check whether the components are still consistent after every multiplication by VRSP.
Synchronised Product Decision Problem The cardinality of the set of leaf covers of all target trees over n leaves has an exponential We show that a leaf cover of a target tree D can be checked in polynomial time.
Definition 1.
A monoid pG, n q is an algebraic structure which is closed under the associative operator n and has the identity element I, where G is generated by G under n.
Definition 2.
Synchronised Product Decision Problem (SPDP) Let pG, n q be a monoid, together with a memory budget M and a deadline D.
Can a feasible target tree D on V pGq be constructed? Note that Gn is represented by a leaf cover of D.
SPDP is in NP if there exists some oracle that points out a solution and there exists an algorithm that can check the solution in polynomial time.
To formalise this, we need the following definitions.
A Ai paq be the set of arcs tai .
i P Ai ^ pai q au On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
A Aij k paq be the arc-set Ak paq where k i if |Ai pa.
A |Aj pa.
else k j A Hij be the graph with arc-set A A ij Ak paq and vertex-set tv .
P V ^ A V V u.
n1 n |A.
A |A1.
| A A ApHij .
i1 j i 1 H q can be calculated in polynomial time.
For all i, j, i j, mpG q Then |A1 | i 1j i 1 mpHij q.
So mpGi q mpGj q mpHij q A mpGi n Gj q.
As soon as mpGn q A An i 1j i 1 mpGj q Au mpHi,j q A M the calculation can stop, as further multiplications will not lead to a solution.
In this case.
Gn is not a solution that full-fills the requirements for the deadline and memory occupancy.
Remark 5.
This is only true because the components .
nd the products of the component.
are Furthermore, the calculation is not performed in the target system but in a general purpose computing system, so the available memory may be significantly greater than the memory available in the target system.
Having calculated the synchronisedA product Gn and performing a breadth first search for each component, we obtain the length of Gn , `pGn q.
Therefore we have in polynomial time an answer whether the oracleAos solution is valid.
Because Gn is represented by a leaf cover in the target tree D, a valid solution implies that D is feasible.
For these reasons SPDP is in NP.
Leung .
defines the 0/1-Knapsack Decision Problem (KDP).
Given a set U tu1 , u2 , , un u with each item uj having a size A sj and a valueAvj , a knapsack with size K, and a bound B.
Is there a subset U AE U such that sj A K and vj Au B.
uj U 1 uj U 1 Theorem 5.
SPDP is NP-complete.
Proof.
Let G An Gi , `pGq An `pGi q T .
Let vj be a vertex in a leaf cover LC with cardinality k of D, where D is a target tree generated by G.
Suppose U tu1 , , uk u is a solution for the 0/1 Knapsack Decision Problem, with uj having size sj mpvj q m B T D.
Because Ak Ak Ak 1 A 1 and value u1j kT `pvj q.
A k1 A 1.
K M, mpvj q A M K and Ak `pvj q A D y `pGq `pLC q Au T D B.
LC is a solution for SPDP.
Conversely, if LC is a solution for SPDP, then `pLC q A D and mpLC q A M K, therefore Ak sj A M K and `pLC q A D y the 0/1 Knapsack Problem.
Ak 1 Ak ui T `pvi q Au T D B.
So U is a solution for On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
This means that, for a Yes-instance of the 0/1 Knapsack Decision Problem, the constructed instance of the decision version of SPDP is a Yes-instance and, conversely, for a Yes-instance of the SPDP, the constructed instance of the decision version of 0/1 Knapsack Decision Problem is a Yes-instance.
As the 0/1 Knapsack Decision Problem is NP-complete and SPDP is in NP.
SPDP is NP-complete.
Heuristics In .
we describe three heuristics that give an answer for SPDP in polynomial time.
The heuristics multiply using VRSP for a graph G An Gi up to k A n components.
These heuristics are based on the .
umber o.
actions that synchronise.
All heuristics choose two components out of a series of n components, where A the Largest Alphabetical Intersection (LAI) heuristic calculates the cardinality of the largest intersection of the alphabets of two components.
A the Maximising Synchronising Arcs (MSA) heuristic calculates the largest number of synchronising arcs of two components.
A the Minimising Not Synchronising Arcs (MNSA) heuristic calculates the smallest cardinality of the not-synchronising arcs set of two components.
Another approach is taking the VRSP of components Gi and Gj .
ontaining synchronising arc.
where the two components chosen for multiplication have the smallest occupancy of memory.
This gives the Minimising Memory Occupancy (MMO) heuristic.
So for Gi .
Gj , mpGi n Gj q pmpGiq mpGj qq is the minimum of all VRSPs mpGk n Gl q pmpGk q mpGl qq .
ontaining synchronising arc.
taken over G1 .
Gn .
Let LC be a leaf cover of the target tree D with cardinality 1.
Then, if mpLC q A M and `pLC q A D.
LC is a solution for the optimisation problem of G.
if mpLC q A M and `pLC q A D, there exists no solution for the optimisation problem of G, if mpLC q A M and `pLC q A D, a solution may exist for the optimisation problem of G, if mpLC q A M and `pLC q A D, there exists no solution for the optimisation problem of G.
Remark 6.
The solution may not be optimal.
That depends on the requirements with respect to memory occupancy and processor utilisation.
As the same reasoning as for AuSPDP is in NPAy is valid, if mpLC q A M then items 1 and 2 can be calculated in polynomial time.
For item 4 no solution exists, because `pLC q A D .
This can be calculated in polynomial time, because as soon as for a leaf cover LC 1 , mpLC 1 q A A An i 1j i 1 mpHij qq the algorithm can stop as no solution exists.
Remains item 3, where mpLC q A M and `pLC q A D.
As SPDP is NP-complete, an optimal solution cannot be found in polynomial time .
nless P=NP).
We compare the three algorithms in On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
Figure 9.
Deadlines and Memory Occupancy of MNSA.
LAI.
MMO and MSA.
together with the algorithm introduced in this paper.
Minimal Memory Occupancy (MMO), given in the Appendix.
Algorithm 2.
The level of the tail of a synchronising arc determines whether LAI or MMO will perform For two components where these levels are low in one component and high in the other component.
MMO will perform better because the VRSP over these two components will be .
optimal with respect to memory occupancy.
Whereas LAI may choose two components with a larger alphabetical intersection that have the levels for tails of the synchronising arcs that are relatively on the same level.
But with respect to the length of the product of the components this can be the opposite.
In Figure 9 we give for the Production Cell case study in .
the results for the four algorithms.
MNSA.
LAI.
MSA and MMO.
Note the logarithmic scale in the y-abyss.
Due to the specification of the processes where each process synchronises over at least one action with all other processes.
MMO performs best up till the last multiplication.
To achieve a length of 37 LAI has the best .
s minima.
memory occupancy.
On a directed tree problem motivated by a newly introduced graph product Antoon H.
Boode et al.
The algorithms replace two components by their product until all components are multiplied.
So from a leaf cover with cardinality n to a leaf cover with cardinality 1.
Conclusions A set of processes that does not meet its deadline or does not fit in the available memory can, under certain conditions, be transformed into a set of processes that will fulfil both requirements.
For this transformation we use our Vertex Removing Synchronised Product (VRSP) on consistent finite labelled weighted deterministic directed acyclic multi-components.
We have given a definition for consistency such that consistent components are deadlock free.
This is essential for the processes represented by these components, because otherwise in the target system deadlines will be missed.
Missing a deadline leads to a catastrophe in hard realtime systems.
We have given conditions and proof for VRSP to be commutative, associative and idem-potent.
This is necessary because otherwise components may not be pairwise consistent.
We have introduced a directed tree problem motivated by VRSP in the context of periodic hard real-time processes.
The number of target trees is exponential with respect to the number of components, representing the original set of processes and is given by the Bell number.
We have dealt with the graph theoretical and computational complexity issues.
We have shown that the directed tree problem is NP-complete and we have presented and compared several heuristics for this problem.
Because SPDP is NP-complete, in practice heuristics have to be used .
ike MMO and the ones we proposed in .
) to calculate a set of components which represent processes that will not be tardy and fit in the available memory.
We have introduced a new heuristic based on memory occupancy that shows for our case study that its performance is in most cases better than the heuristics given in .
In our case the new set of processes is calculated off-line during the design process and forms no burden on the target system, in our case an active real-time system.
Because the components have to be consistent, to compose the original set of components, the designer is limited in his description of the system.
In our view this is not a problem, because, if the set of graphs would be not consistent, it contains graphs that represent processes that form a This is a situation that has to be avoided.
Acknowledgement The authors would like to express their gratitude to the anonymous reviewers for their useful suggestions and comments.
The research of the first author has been funded by the InHolland University of Applied Sciences.
Alkmaar.
The Netherlands.
References