The web service composition problem can be stated as follows: given a finite state machine M , representing a service business protocol, and a set of finite state machines R, representing the business protocols of existing services, the question is to check whether there is a simulation relation between M and the shuffle product closure of R. In fact the shuffle product is a subclass of the communication free petri net and basic parallel processes, for which the same problem of simulation is known to be 2-Exptime-hard. This paper studies the impact of several parameters on the complexity of this problem. We show that the problem is Exptime-complete if we bound either: (i) the number of instances of services in R that can be used in a composition, or(ii) the number of instances of services in R that can be used in parallel, or (iii) the number of the so-called hybrid states in the finite state machines of R by 2.
Web Services [
We consider in this paper the problem of Web Service Composition (WSC).
This problem arises from the situation where none of the existing services can
provide a requested functionality. In this case, the idea is to find out,
algorithmically, if the target functionality could be composed out of the existing services
(components repository). This automatic approach of composition simplifies the
development of software by reusing existing components and offers capabilities
to customize complex systems built on the fly [
[
Shuffle product of FSMs (and PCSM) is a subclass of Basic Parallel Processes
(BPP), the class of communication free petri nets: every transition has at most
one input place. Simulation of FSM by BPP was proven Expspace-hard by Lasota
[
Complexity analysis of WSC was first considered by Musholl et al.[
In this paper, we consider additional parameters related to
bounded/unbounded web services composition. We consider as inputs an
FSM M (the target protocol) and a set of FSMs R (the protocols of the
available services) and we investigate the complexity of testing simulation
between M and the shuffle closure of R, represented as a PCSM [
Finite State Machine We consider in this paper service business protocols formally described as FSMs. We recall below the definition of such machines. Definition 1. (Finite State Machine (FSM)) A State Machine (SM) M is a tuple M = ( M ; QM ; FM ; qM0 ; M ), where: M is a finite alphabet, QM is a set of states, M QM M QM is a set of labelled transitions, FM QM is a set of final states, and qM0 2 QM is the initial state. If QM is finite then M is called a Finite State Machine (FSM). Moreover, a state q 2 QM is called: intermediate, if q 2= FM and 9p1; p2 2 QM , s.t (p1; a; q) 2 M and (q; b; p2) 2 M , we denote by I(M ) the set of intermediate states of M ; hybrid, if q 2 FM , q 6= q0 and there exist at least one transition (q; b; p) 2 M , with p 2 QM and b 2 , the set of hybrid states is denoted H(M ) and terminal, if q 2 FM and is not hybrid.
We define the norm of a state q as the finite length of the shortest path from q to a final state. The norm of an FSM M , noted norm(M), is the maximal norm of its states. k-Iterated Product Machine (k-IPM) and Product State Machine (PCSM) We start by defining the shuffle (asynchronous product) and union operations on FSMs: Definition 2. (Asynchronous product and Union of two FSMs) Let M = ( M ; QM ; FM ; qM0 ; M ) and M 0 = ( M0 ; QM0 ; FM0 ; qM00 ; M0 ) be two FSMs. We have : – The shuffle or asynchronous product of M and M 0, denoted M M 0, is an FSM ( M [ M0 ; QM QM0 ; FM FM0 ; (qM0 ; qM00 ); ) where the transition function is defined as follows: = f((q; q0); a; (q1; q10)) : ((q; a; q1) 2 M and q0 = q10) or ((q0; a; q10) 2 M0 and q = q1)g. – The union of M and M 0, denoted M [ M 0, is the FSM ( M [ M0 [ f g; QM [ QM0 [ fq0g; FM [ FM0 ; q0; M [ M0 [ f(q0; ; qM0 ); (q0; ; qM00 )g).
For a set of available FSMs R = fM1; :::Mig, we consider a compact structure that abstracts all possible executions that can be produced using the components of R. First, we begin by the simple case where each Mj can be used only once:
Mij ) where j 2 [0; i].
Definition 3. (Union of asynchronous products of FSMs set) Let R = fM1::::Mmg be a FSMs repository. We define (R) the union of asynchronous product of all the subsets of R as the FSM: (R) = SfMi1 ;:::;Mij g22R (Mi1 :::
Second, we consider the case where the number of copies of each Mj 2 R is bounded by an integer k: Definition 4. (k-iterated product of FSMs set R) The k-iterated product of R is defined by R k = R k 1 (R) with R 1 = (R).
Finally, we consider the general case where the number of instances of each
Mj 2 R is unbounded. This corresponds to the product closure of R [
The Product Closure Machine (PCSM) of R, defined in [
Example 1. Figure 2 illustrates the execution of the sequence "abca" by the PCSM of the FSM M in figure 2-(a). M contains one intermediate state q1 and two hybrid states q2 and q5. Therefore, figure 2-(b) depicts a part of the PCSM M with triplets as configurations where integers witness respectively the number of tokens in q1, q2 and q5. For each configuration c in figure 2(b), we associate an instant t (or several instants) during the execution when c describes the PCSM. At the beginning (t = 0), M ’s instantaneous description is (0; 0; 0), interpreting an empty stack in every state of M , except the initial state with an infinite number of tokens (figure 2-(c)). To execute the transition (q0; a; q1), a token is moved from q0 to q1 in figure 2-(d), corresponding to the configuration (1; 0; 0) in instant t = 1. In t = 2, the executed transition (q0; b; q4) corresponds to moving a token from the initial state to a terminal one q4 (figure 2-(e)). Since the instantaneous description does not consider neither initial states nor terminal ones, then the configuration stays the same as the previous instant. Notice that this move corresponds to both creating and terminating an instance of the FSM. Then, the transition (q0; c; q5) is executed by moving a token from q0 to the hybrid state q5. This creates a new instance implying, in this case, an increase in the number of simultaneously used instances in the execution. This is depicted in figure 2-(f). Finally, a token is moved from the state q1 to q2 in figure 2-(g), in order to execute the transition (q1; a; q2). It changes M ’s instantaneous description in t = 4 into (0; 1; 1) which is a final configuration (i.e (0; 1; 1) 2 FC ) since all tokens in the PCSM are in final states (either hybrid or terminal).
Formally, we define the PCSM R as the SM ( R; CR ; FC; c0;
R ), where: 1. R = SMj2R Mj ;
n = nI (R) + nH (R) with: nI (R) is the number of intermediate states in R) (nI (R) = j SMj2R I(Mj )j) and nH (R) is the number of hybrid states in R) (nH (R) = j SMj2R H(Mj )j). For each configuration c, c[m] (the mth component of c) is called a witness of a unique state qm 2 QMj for some j. Note that: – qm is an intermediate state, if 1 m nI (R); – qm is an hybrid state, if nI (R) + 1 m n.
In an abuse of notation, we use c[m] and c[qm] interchangeably. 3. FC is the set of final states. FC = fc 2 CR jc[m] = 0; for each: 1 m nI (R)g; 4. c0 = f0gn is the initial state of R ; 5. CR R CR is the set of transitions. we have (c1; a; c2) 2 R
R iff : – there exists (q0; a; q) 2 QMj , such that: q0 is the initial state of Mj and c2[q] = c1[q] + 1 and c2[p0] = c1[p0] for each p0 6= q. – there exists (p; a; q) 2 QMj , such that: c2[p] = c1[p] 1, c2[q] = c1[q] + 1 and c2[p0] = c1[p0] for each p0 6= p; q. – there exists (p; a; q) 2 QMj , such that: q is a final state or the initial state, c2[p] = c1[p] 1 and c2[p0] = c1[p0] for each p0 6= p.
Simulation preorder We recall below the definition of the simulation preorder between two SMs.
q1 q3 a q2
c (c) PCSM M⊗at the instant t = 0 (d) PCSM M⊗at the instant t = 1
(e) PCSM M⊗at the instant t = 2 (a) An FSM M
(b) A part of the PCSM M⊗ (f) PCSM M⊗at the instant t = 3
1 (g) PCSM M⊗at the instant t = 4 1. 8a 2 M and 8p0 2 QM such that (p; a; p0) 2 M , there exists (q; a; q0) 2 N such that p0 q0, and 2. if p 2 FM , then q 2 FN .
Example 2. Figure 3-(c) is an example of a simulation tree, verifying if the initial state s0 of the FSM A (figure 3-(a)) is simulated by the initial configuration c0 = (0; 0; 0) of the PCSM of M (figure 3-(b)). A branch is terminated with success when a terminal state of A is reached and paired with a final configuration (all intermidiate witnesses are null), or when a configuration of M that covers one of its predecessors is reached and paired with the same state of A. In this case, the simulation tree proves that A M .
A s0 a c s1 s3
M q0 b q4 a b a s2 c a q5 (a)- An FSM A
a q1 c a q3 q2
c s3, c0 = (0, 0, 0)
Success s0, c0 = (0, 0, 0)
a s1, c1 = (1, 0, 0)
c s3, c2 = (1, 0, 1)
Fail s1, c5 = (0, 1, 0)
a c s3, c6 = (0, 1, 1)
Success b s2, c5 = (0, 1, 0)
a s1, c7 = (1, 1, 0) c1/c7 Success b s2, c1 = (1, 0, 0)
a s1, c3 = (2, 0, 0) c s3, c1 = (1, 0, 0)
Fail
c s3, c4 = (2, 0, 1)
Fail (b)- An FSM M
(c)- Simulation tree between A and M⊗
Interestingly, the simulation verification defined above can be seen as a two players game in a directed graph (Va; Vd; ; v0), such that V = Va [Vd is the set of vertices with Va QM QN and Vd QM QN M , (Va Vd) [ (Vd Va) is the edges set verifying: -for (q; p) 2 Va and (q; a; q0) 2 M , we have ((q; p); (q0; p; a)) 2 ; and -for (q; p; a) 2 Vd and (p; a; p0) 2 N , we have ((q; p; a); (q; p0)) 2 .
The game is played by an attacker and a defender. It starts by putting a token in v0 = (qM0 ; qN0 ) 2 Va, then the players move it along the edges of the graph. If the token is on a vertex v 2 Va then the attacker moves it, otherwise it is the defender’s turn.
A strategy of a player x 2 fa; dg is a function S : V :Vx 7! V , where V :Vx denotes all sequences of vertices in V that end with a vertex in Vx and S(v0; :::; vk) = vk+1 implies that (vk; vk+1) 2 . In each different play, a player x adapts a strategy that decides his moves.
The defender wins every infinite play. Otherwise, the first player who can not move loses. M is simulated by N iff the defender has a wining strategy regardless of his opponent’s strategy.
Observe that, by definition, each transition of a PCSM can at most increase or decrease a configuration component by 1. In addition, if a configuration is final then all intermediate states witnesses are equal to 0. Therefore, given a set of FSMs R and c 2 CR , we have q2SMi2R I(Mi)c[q] norm(c). Moreover, since final states can only be simulated by final ones, then for M an FSM and p 2 QM , if p c then norm(c) norm(p). Hence, we are able to derive the following property.
CR j q2SMi2R I(Mi)c[q] q2SMi2R I(Mi)c[q]
norm(M )g.
Property 1. (Intermediate witnesses bound) [
In [
We say that c0 covers c, denoted c / c0.
We introduce below the algorithm of [
Definition 7. (Simulation Tree) We call a simulation tree Tsim(M; R ) a tree (V; v0; E) where: – v0 = (qM0 ; c0) is the root of the tree; – V QM CRM is the set of nodes; – If (q; c) 2 V and q is final in M then so is c in R ; – E V V is the set of the tree’s edges. 8e = ((p; c); (q; d)) 2 E : 9a 2
M s.t (p; a; q) 2 M and (c; a; d) 2 R ; – v = (p; c) 2 V is a leaf in Tsim(M; R ) iff p is terminal in A or there exists an ancestor (p; c0) 2 V of v in Tsim(M; R ) such that c/c0.
In the next section, we shall bound the size of this tree in the case of bounded WSC problem (i.e., when the instances of services allowed to be used in the simulation is bounded by a parameter k).
We call a bounded WSC problem, a service composition problem where the number of copies of each web service in the repository R used to compose the target M is bounded a priori by an integer k. This problem is formally stated as follows.
Problem 1. Bounded Composition BC(M; R; k) Input : R a set of FSMs; M a target FSM; k an integer.
Question : M Sik=0 R i ? Sik=0fR1; R3g i , for any k
The particular case BC(M; R; 1) has been investigated by Muscholl and
Walukiewicz [
The parameter k drops the infinite aspect and reduces the search space. In this case, a loop in M can only be simulated by loops in R. For example, one can observe that, in figure 4, St is not simulated by Sk i=0fR1; R3g i for every k 2 N. This is because when we repeat the loop in St (k + 1) times, there is no corresponding execution in Sik=0fR1; R3g i . However, we have St 1.
St
a b c a
R1
a b c
R2 b a
R3 a
In the following, we give an upper bound of the number of states that might appear in Sik=0 R i , with k 2 N.
Lemma 1. Let R be a set of FSM and k is an integer. The number of states in Sik=0 R i is bounded by O(2nlogk) where n = nI (R) + nH (R). Proof. Notice that R
= (Sik=0 R i ) [ (Si+=1k+1 R i ).
In fact, the states in Sik=0 R i correspond to the PCSM’s configurations subset fc 2 CR k j 0 c[i] k; i 2 [1; n]g. Hence, the number of states of Sik=0 R i is bounded by (k + 1) : : : (k + 1) = 2nlog(k+1). tu
This lemma reduces the search space to an exponential size and leads to the following theorem.
Theorem 1. BC(M; R; k) is Exptime-Complete Proof. Exptime. To show that BC(M; R; k) is Exptime, we bound the size of the simulation tree. A node of the simulation tree corresponds to (q; c) where q is a state of M and c a configuration of R k . According to Lemma 1, the number of PCSM’s configurations is bounded by kn. So the number of nodes in the simulation tree is at most jQM j kn = 2nlog(k)+log(jQM j) and therefore the complexity is in Exptime.
Exptime-Hardness. It can be deducted directly from the Exptime-Hardness
of the particular case BC(M; R; 1) [
Instead of the total number of instances used in the simulation, what happens if we bound only the number of instances used simultaneously? we raise this question in the next section and prove that the problem stays Exptime-complete. 4
Now we consider a new parameter in service web composition that bounds the number of communications in parallel between the target and the services, i.e. the number of live services executions is bounded, but the number of instances is not. It appears that the web services composition with unbounded instances and bounded parallel instances is Exptime-Complete.
To do so, we limit the configurations of the PCSM R to configurations where the number of waiting instances is bounded by k. Indeed, when we need to use a new instance in R , we check if Pin=1 c[i] k. If so, we decrease c[j] for some j 2 [nI (R) + 1; nH (R)], i.e. we finish an instance that is waiting in an hybrid state. Let us denote by R k;p the obtained PCSM.
Problem 2. Bounded Parallel Instances Composition (P BC(M; R; k)) Input : R a set of FSMs;
M a target FSM.
k an integer, bounding the number of parallel instances of R’s components used simultaneously in the simulation.
Question : M R k;p ?
Note that P BC(M; R; k) can use an unbounded number of instances but only k instances in parallel.
Theorem 2. P BC(M; R; k) is Exptime-complete. Proof. First we show that P BC(M; R; k) is Exptime. Clearly the entry of any configuration is bounded by k (hybrid states are included) and therefore we can check simulation in Exptime, since the depth of the simulation tree is bounded by kn (see Lemma 1).
To show the Exptime-hardness, it suffices to note that the unbounded composition without hybrid states U CHS(M; R; 0) is a particular case of P BC(M; R; k), since we prove later in theorem 4 that U CHS(M; R; 0) is Exptime-hard. In fact, the number of tokens in intermediate states of R is bounded by norm(M ) (property 1). Hence, when R is hybrid state free, the number of instances that can be used in the simulation is bounded by norm(M ). In other words, it corresponds to P BC(M; R; norm(M )). tu
For k a constant, we obtain the following.
Corollary 1. P BC(M; R; k) is polynomial when k is a constant. Proof. First of all, let us consider for every configuration c of R k;p , a new component c[n + 1] = k (Pin=1 c[i]), with n = nI (R) + nH (R).
For every configuration c in R k;p , the non-empty witnesses fc[i] > 0; i n + 1g correspond to a partition of k elements (instances) into a sequence of j non empty subsets, for j = jfc[i] > 0; 1 i ngj k. Note that j is in fact inferior to min(k; n), but since k is a constant then it is more interesting to keep it as a lower bound of j.
For every j k, the number of labeled partitions of k elements into a
sequence of j non empty subsets is j! fjkg, where fjkg is a Stirling number of
the second kind [
We conclude that the number of configurations in R k;p is bounded by Pjk=1 Cnj j! fjkg 2 O(nk).
Finally, by applying the simulation algorithm in [
In the following, we show that P BC(M; R; k) is NP-Complete for loop-free
target FSM. Let a sequence of letters (a word) over and M the FSM that
recognizes exactly . We call the language recognized by M . We consider
the following NP-complete Problem [
Problem 3. SHUFFLE PRODUCT Input : and 0 two words over an alphabet Question : 2 0 ? ; Theorem 3. P BC(M; R; k) is NP-complete whenever M is loop-free. Proof. Clearly P BC(M; R; k) is in NP since the simulation relation is polynomial in the size of M . To show the NP-hardness, we reduce SHUFFLE PRODUCT to it. Let and 0 be an instance of SHUFFLE PRODUCT. We associate an FSM M which recognizes exactly and R = fN g where N is the FSM that recognizes exactly 0. Since M is a chain, then the size of a branch of the simulation tree can not surpass j j. Thus,the simulation verification will only explore R k;p ’s executions where the size is bounded by j j k:j 0j with k = d jj 0jj e and therefore the number of instances is bounded by k. Hence, 2 0 iff M R k;p iff M R . We give an example in figure 5. tu M N a a b b a c c b c
μ = {abacbc} μ0 = {abc}
μ k = d||μ0||e = 2 M
N⊗2,p
Another factor of complexity of the WSC problem is the number of hybrid states in the available services. We investigate next the effect of this parameter on the complexity of the WSC problem. 5
The presence of hybrid states is a source of complexity in a WSC problem. As mentioned before, the size of intermediate states witnesses in configurations of R used to simulate M is bounded by norm(M ). We are however unable to provide a similar bound for the number of hybrid states witnesses.
Figure 6 is an example of simulation between an FSM M and a PCSM R . The FSMs in R contain two hybrid states (state 1 and 2) and no intermediate state. Hence, a configuration of R is a pair of integers witnessing the number of tokens in state 1 and state 2. The example illustrates the different roles that an hybrid state of R can play to simulate a state of M . Indeed an hybrid state of R, can be used as:
(i) a terminal state, e.g., when testing whether q5 (1; 1), we can consider the second hybrid state of R as a terminal state and terminate the test, or (ii)an intermediate state, e.g., when testing whether q2 (1; 1), the second hybrid state of R here plays the role of intermediate state, or
both a terminal and an intermediate state, e.g., when testing whether q1 (1; 0), a transition of R labeled by (b; ( 1; 0)) only appears in one branch in the simulation tree Tsim(M; R ). Hence, the first hybrid state of R is considered intermediate in one branch and terminal in the other, or a hybrid state, e.g., when it is used to simulate an hybrid state of H(M ). We consider in the following the problem defined below.
M q0 q1 a c q5 b 1
R c d 2 d, (0, −1)
q4, (1, 0) c, (0, 1) q5, (1, 1)
Tsim(M, R⊗)
It is worth noting that U CHS(M; R; k + 1) is harder then U CHS(M; R; k). In the sequel, we progressively investigate the complexity of U CHS(M; R; k) problem for k = 0, then for k = 1 and finally for k = 2.
Case of composition without hybrid states (i.e. k = 0) In this section, we are interested in the problem U CHS(M; R; 0). We first give a polynomial transformation, denoted K, which is used to reduce BC(M; R; 1) to U CHS(N; R0; 0). This transformation provides a mean to bound the number of instances used to prove simulation.
Definition 8. Transformation K. For an FSM M = ( M ; QM ; FM ; q0M ; M ) and a set of FSMs R = fM1; :::; Mmg, we define K(M; R)=(N; R0=fN1; ::; Nmg) where: 1. Each Ni is built based on Mi, by adding a letter ti to its alphabet, a final state fi and a transition set f(q0Mi ; ti; fi)g [ f(q; ti; fi)jq 2 FMi g. All final states of Mi become intermediate in Ni. 2. N is defined as: – N = M [ ftij1 i mg; – QN = QM [ frij1 i mg; – FN = frmg; – N = M [ f(q; t1; r1)jq 2 FM g [ f(ri; ti+1; ri+1)j1 i < mg.
R c p3
Proposition 1. Let M be an FSM, R = fM1; :::; Mmg be a set of FSMs and K(M; R) = (N; R0 = fN1; ::; Nmg). For p and q two states of respectively M and R 1 , we have: p (M;(R) 1 ) q iff p (N;(R0) 1 ) q. q0.
Proof. By construction of K(M; R), if p then p (N;(R0) 1 ) q.
We suppose next that: If (p; a; p0) 2 M , (q; a; q0) 2
R 1 and p0 and prove that p
(N;(R0) 1 ) q.
For each (p; a; p0) 2 N , we have: (M;R 1 ) q and p is terminal in M (M;R 1 ) q0, then p0 (N;(R0) 1 )
M , then there exists (q; a; q0) 2
R 1 (N;(R0) 1 ) q0. – else a = t1, p0 = r1 and q is a product of final states of R. therefore, there exists (q; t1; q0) 2 (R0) 1 such that q0 = (f1; q0i1 ; :::; q0il ) where q0ij is final in R such that p0 (N;(R0) 1 ) q0.
(R0) 1 such that p0 (M;R 1 ) q.
(N;(R0) 1 ) q then p We conclude that if p (M;R 1 ) q then p (N;(R0) 1 ) q.
Reciprocally, we have (p; a; p0) 2 N (respectively (R0) 1 ) and a 2= ftij1 i mg iff (p; a; p0) 2 M (respectively R 1 ). In addition, the definition of K ensures that if p is final in M and p (N;(R0) 1 ) q then q is final in R 1 . Hence if p tu In particular, we take p as the initial state of M and q the initial state of R 1 . This implies that: Proposition 2. Let M be an FSM, R = fM1; :::; Mmg be a set of FSMs and K(M; R) = (N; R0 = fN1; ::; Nmg). We have: M R 1 iff N (R0) . Proof. We have N (R0) 1 iff N (R0) . Indeed, each path that starts from the initial state to a final one in N contains exactly one transition labelled by ti, for each i 2 [1; m] and a similar path in each Ni contains exactly one transition labelled by ti. tu Hence, K is a polynomial reduction of BC(M; R; 1) problem to the UCHS problem. This enables to derive the following result.
Theorem 4. U CHS(M; R; 0) problem is Exptime-complete.
Proof. According to proposition 2, the K transformation reduces BC(M; R; 1)
to U CHS(M; R; 0) in polynomial time. Thus U CHS(M; R; 0) is Exptime-hard.
Since it is also proven Exptime in [
Case of composition with one hybrid state We consider the problem U CHS(M; R; 1) where M is an FSM and R a set of FSMs containing at most one hybrid state (nH (R) 1). We denote k0 = jQM j:2nI (R):log(norm(M)). Two nodes (q; c) and (q0; c0) in a simulation tree are called comparable if q = q0 and either c/c0 or c0/c. The nodes (q; c) and (q0; c0) are said incomparable otherwise.
Property 3. Let R be a set of FSMs containing at most one hybrid state. Two configurations of R are comparable by the cover relation, iff they have exactly the same intermediate witnesses.
Proof. Acoording to property 2, for c; c0 two configurations in R c0 iff : we have c / 1. c and c0 have the same intermediate witnesses; and 2. for every hybrid witness c[h], we have: c[h] c0[h].
In the current case, we consider that R has at most one hybrid witness. Hence, for any pair of configurations of R , condition 2 is verified.
We conclude that for every two configurations c; c0 in R , c / c0 iff c and c0 have the same intermediate witnesses. tu Property 4. Let S be a set of nodes of Tsim(M; R ) that are pairwise incomparable, then jSj k0.
Proof. In configurations considered in Tsim(M; R ), intermediate witnesses are bounded by norm(M ) (property 1). Therefore and according to property 3, the number of incomparable configurations considered in Tsim(M; R ) is at most
Proposition 3. If nH (R) (nI (R) + 1)] k02.
1, then foreach (q; c) 2 Tsim(M; R ), c[h = Proof. let P be a path in Tsim(M; R ), Int be an interval in N and S = (vn = (qn; cn))n2Int be a sequence of nodes in P such that: -vi is the ith node met in P that is comparable to one of its predecessors v = (qi; c); and -For each i; j 2 Int, vi and vj are incomparable.
If Int = ;, then all nodes of P are not comparable. The size of P is then bounded by k0, therefore, c[nI (R) + 1] k0 for each (q,c) in P.
We suppose next that Int 6= ; and take Int = [1; k], k 2 N. We prove recursively that for each l 2 [1; k], cl[h] l:k0.
For l = 1, we have c1[nI (h] k0.
For 1 < l < k, we suppose that cl[h] vl+1 in P is either: 1. comparable to a node vi with i 2 [1; l]. In this case, c[h] < ci[h] l:k0 (otherwise v should be a leaf). 2. incomparable to all its predecessors. The number of such nodes is bounded by k0. And since transitions displacements is in f 1; 0; 1gh, then we have c[h] < l:k0 + k0.
Therefore cl+1[h]
(l + 1):K0.
Once we reach vk, each one of its possible successors v = (q; c) is comparable to a node vi with c[h] < ci[h], except for the last one that is the leaf of P.
Finally, since k < k0 (because S is a sequence of incomparable nodes), we conclude that each node of P is in QA ([1; norm(A)]I [1; k02]). tu l:k0. Each node v = (q; c) between vl and
Since deciding simulation only requires to visit a node once, we argue next that this problem is in APspace (i.e a problem that can be solved by an alternating Turing machine in polynomial space): the size of a position of the simulation tree is polynomial in the input size (Proposition 3). Hence a polynomial space alternating turing machine can solve this simulation problem: universal states correspond to the target’s and existential states correspond to the shuffle product’s configurations. Note that APspace corresponds to Exponential time complexity. Given the above, we conclude that: Lemma 2. U CHS(M; R; 1) is in Exptime.
To prove the Exptime-hardness of the problem, we recall that U CHS(M; R; 0) is Exptime-hard (theorem 4) and that U CHS(M; R; 1) is harder than U CHS(M; R; 0).
Theorem 5. U CHS(M; R; 1) is Exptime-complete.
Case of composition with two hybrid states In this section, we consider the problem of unbounded composition of web services with at most 2 hybrid states in R, i.e. U CHS(M; R; 2). Our approach is based on relating this simulation problem to the reachability issue.
For x 2 Ni1 and y 2 Ni2 , we denote the concatenation of two vectors x and y, (x:y) 2 Ni1+i2 such that: – States: S QM fc 2 NnI (R)j Pii==1nI (R) c[i] norm(M )g. – Transitions: W S S f 1; 0; 1g2 such that: ((q; c); (p; d); x) 2 W iff there exists a 2 M , y 2 N2 such that (p; a; q) 2 QM and ((c; y); a; (d; y + x)) 2 R and Pii==1nI (R) c[i] norm(M ) and Pii==1nI (R) d[i] norm(M ). – Initial configuration: the system starts with the state (q0M ; f0gnI (R)) and the vector (0; 0).
Figure 8 depicts an example of a VASS associated to an FSM M and a set of FSMs R. q3 a c
M q0 a q1 a q4 b q2 (a) a 2 c R 1 3 a b a
The reachability issue in 2-dimension VASSs has been investigated by
Hopcroft and Pansiot [
We consider in the following a simulation tree Tsim(M; R )=(V; v0; E), a recheability tree Treach(VM;R)=(V 0; v00; E0) and a function defined as follows:
Proposition 4. Let = v0:::vt be a path in Tsim(M; R ). Then there exists a path 0 = v00:::vt0 in Treach(VM;R) such that vi = (vi0), i 2 [0; t]. Proof. We proof by induction on the length i of the path = v0:::vt.
For i = 0 we have v0 = (q0M ; c0) = ((q0M ; f0gnI (R)); x0; Ac0 ) = (v00).
Now suppose that the property is true for i < t and v0:::vi+1 is a path in Tsim(M; R ). Then by hypothesis there exists a path v00:::vi0 in Treach(VM;R), such that vj = (vj0 ), j 2 [0; i].
Suppose that vi0 is a leaf in Treach(VM;R). Then according to the algorithm
of Hopcroft and Pansiot [
But for vi = (p; (c; x)) and vi+1 = (q; (d; y)) we have vivi+1 2 E which means that (p; a; q) 2 M and ((c; x); a; (d; y)) 2 R . This implies that ((p; c); (q; d); y x) 2 W . Contradiction.
Therefore, we have : vi0+1 = ((q; d); y; Ay) is a successor of vi0 in Treach(VM;R), with vi+1 = (q; (d; y)). We conclude that 0 is a path in Treach(VM;R). tu
The following corollary is a consequence of Proposition 4.
Corollary 2. Tsim(M; R ) is a sub-tree of Treach(VM;R).
Clearly the time complexity for computing Tsim(M; R ) is dominated by the
complexity of computing Treach(VM;R). Moreover we know from [
Theorem 6. U CHS(M; R; 2) is in 3-Exptime.
Proof. According to [
Our proof for Theorem 6 can be seen more as an embedding of the search
space explored by a simulation test to the one explored when the reachability
issue is considered. This is an approach that can not so far be generalized because
the best upper bound provided for vector addition systems reachability is
nonprimitive recursive; in fact even the existence of a primitive upper-bound is still
open [
In this paper we have considered two parameters that are source of
complexity of the web services composition problem. We have shown that among the
considered problems, several instances remain Exptime-complete when a
parameter is bounded. It remains an open question to identify the complexity of
U CHS(M; R; k) for any k 2 N; [