12.66/4.04 YES 12.74/4.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 12.74/4.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.74/4.06 12.74/4.06 12.74/4.06 Termination w.r.t. Q of the given QTRS could be proven: 12.74/4.06 12.74/4.06 (0) QTRS 12.74/4.06 (1) QTRSRRRProof [EQUIVALENT, 46 ms] 12.74/4.06 (2) QTRS 12.74/4.06 (3) DependencyPairsProof [EQUIVALENT, 45 ms] 12.74/4.06 (4) QDP 12.74/4.06 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 12.74/4.06 (6) AND 12.74/4.06 (7) QDP 12.74/4.06 (8) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (9) QDP 12.74/4.06 (10) QReductionProof [EQUIVALENT, 0 ms] 12.74/4.06 (11) QDP 12.74/4.06 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (13) YES 12.74/4.06 (14) QDP 12.74/4.06 (15) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (16) QDP 12.74/4.06 (17) QReductionProof [EQUIVALENT, 0 ms] 12.74/4.06 (18) QDP 12.74/4.06 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (20) YES 12.74/4.06 (21) QDP 12.74/4.06 (22) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (23) QDP 12.74/4.06 (24) QReductionProof [EQUIVALENT, 0 ms] 12.74/4.06 (25) QDP 12.74/4.06 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (27) YES 12.74/4.06 (28) QDP 12.74/4.06 (29) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (30) QDP 12.74/4.06 (31) QReductionProof [EQUIVALENT, 0 ms] 12.74/4.06 (32) QDP 12.74/4.06 (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (34) YES 12.74/4.06 (35) QDP 12.74/4.06 (36) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (37) QDP 12.74/4.06 (38) QReductionProof [EQUIVALENT, 1 ms] 12.74/4.06 (39) QDP 12.74/4.06 (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (41) YES 12.74/4.06 (42) QDP 12.74/4.06 (43) UsableRulesProof [EQUIVALENT, 0 ms] 12.74/4.06 (44) QDP 12.74/4.06 (45) QReductionProof [EQUIVALENT, 1 ms] 12.74/4.06 (46) QDP 12.74/4.06 (47) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.74/4.06 (48) YES 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (0) 12.74/4.06 Obligation: 12.74/4.06 Q restricted rewrite system: 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 active(h(X)) -> mark(c(d(X))) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (1) QTRSRRRProof (EQUIVALENT) 12.74/4.06 Used ordering: 12.74/4.06 Polynomial interpretation [POLO]: 12.74/4.06 12.74/4.06 POL(active(x_1)) = x_1 12.74/4.06 POL(c(x_1)) = x_1 12.74/4.06 POL(d(x_1)) = x_1 12.74/4.06 POL(f(x_1)) = x_1 12.74/4.06 POL(g(x_1)) = x_1 12.74/4.06 POL(h(x_1)) = 1 + x_1 12.74/4.06 POL(mark(x_1)) = x_1 12.74/4.06 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 12.74/4.06 12.74/4.06 active(h(X)) -> mark(c(d(X))) 12.74/4.06 12.74/4.06 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (2) 12.74/4.06 Obligation: 12.74/4.06 Q restricted rewrite system: 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (3) DependencyPairsProof (EQUIVALENT) 12.74/4.06 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (4) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 ACTIVE(f(f(X))) -> MARK(c(f(g(f(X))))) 12.74/4.06 ACTIVE(f(f(X))) -> C(f(g(f(X)))) 12.74/4.06 ACTIVE(f(f(X))) -> F(g(f(X))) 12.74/4.06 ACTIVE(f(f(X))) -> G(f(X)) 12.74/4.06 ACTIVE(c(X)) -> MARK(d(X)) 12.74/4.06 ACTIVE(c(X)) -> D(X) 12.74/4.06 MARK(f(X)) -> ACTIVE(f(mark(X))) 12.74/4.06 MARK(f(X)) -> F(mark(X)) 12.74/4.06 MARK(f(X)) -> MARK(X) 12.74/4.06 MARK(c(X)) -> ACTIVE(c(X)) 12.74/4.06 MARK(g(X)) -> ACTIVE(g(X)) 12.74/4.06 MARK(d(X)) -> ACTIVE(d(X)) 12.74/4.06 MARK(h(X)) -> ACTIVE(h(mark(X))) 12.74/4.06 MARK(h(X)) -> H(mark(X)) 12.74/4.06 MARK(h(X)) -> MARK(X) 12.74/4.06 F(mark(X)) -> F(X) 12.74/4.06 F(active(X)) -> F(X) 12.74/4.06 C(mark(X)) -> C(X) 12.74/4.06 C(active(X)) -> C(X) 12.74/4.06 G(mark(X)) -> G(X) 12.74/4.06 G(active(X)) -> G(X) 12.74/4.06 D(mark(X)) -> D(X) 12.74/4.06 D(active(X)) -> D(X) 12.74/4.06 H(mark(X)) -> H(X) 12.74/4.06 H(active(X)) -> H(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (5) DependencyGraphProof (EQUIVALENT) 12.74/4.06 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 13 less nodes. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (6) 12.74/4.06 Complex Obligation (AND) 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (7) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 H(active(X)) -> H(X) 12.74/4.06 H(mark(X)) -> H(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (8) UsableRulesProof (EQUIVALENT) 12.74/4.06 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (9) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 H(active(X)) -> H(X) 12.74/4.06 H(mark(X)) -> H(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (10) QReductionProof (EQUIVALENT) 12.74/4.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.06 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (11) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 H(active(X)) -> H(X) 12.74/4.06 H(mark(X)) -> H(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (12) QDPSizeChangeProof (EQUIVALENT) 12.74/4.06 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.06 12.74/4.06 From the DPs we obtained the following set of size-change graphs: 12.74/4.06 *H(active(X)) -> H(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 *H(mark(X)) -> H(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (13) 12.74/4.06 YES 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (14) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 D(active(X)) -> D(X) 12.74/4.06 D(mark(X)) -> D(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (15) UsableRulesProof (EQUIVALENT) 12.74/4.06 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (16) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 D(active(X)) -> D(X) 12.74/4.06 D(mark(X)) -> D(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (17) QReductionProof (EQUIVALENT) 12.74/4.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.06 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (18) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 D(active(X)) -> D(X) 12.74/4.06 D(mark(X)) -> D(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (19) QDPSizeChangeProof (EQUIVALENT) 12.74/4.06 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.06 12.74/4.06 From the DPs we obtained the following set of size-change graphs: 12.74/4.06 *D(active(X)) -> D(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 *D(mark(X)) -> D(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (20) 12.74/4.06 YES 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (21) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 G(active(X)) -> G(X) 12.74/4.06 G(mark(X)) -> G(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (22) UsableRulesProof (EQUIVALENT) 12.74/4.06 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (23) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 G(active(X)) -> G(X) 12.74/4.06 G(mark(X)) -> G(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (24) QReductionProof (EQUIVALENT) 12.74/4.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.06 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (25) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 G(active(X)) -> G(X) 12.74/4.06 G(mark(X)) -> G(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (26) QDPSizeChangeProof (EQUIVALENT) 12.74/4.06 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.06 12.74/4.06 From the DPs we obtained the following set of size-change graphs: 12.74/4.06 *G(active(X)) -> G(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 *G(mark(X)) -> G(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (27) 12.74/4.06 YES 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (28) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 C(active(X)) -> C(X) 12.74/4.06 C(mark(X)) -> C(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (29) UsableRulesProof (EQUIVALENT) 12.74/4.06 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (30) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 C(active(X)) -> C(X) 12.74/4.06 C(mark(X)) -> C(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (31) QReductionProof (EQUIVALENT) 12.74/4.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.06 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.06 c(mark(x0)) 12.74/4.06 c(active(x0)) 12.74/4.06 g(mark(x0)) 12.74/4.06 g(active(x0)) 12.74/4.06 d(mark(x0)) 12.74/4.06 d(active(x0)) 12.74/4.06 h(mark(x0)) 12.74/4.06 h(active(x0)) 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (32) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 C(active(X)) -> C(X) 12.74/4.06 C(mark(X)) -> C(X) 12.74/4.06 12.74/4.06 R is empty. 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 12.74/4.06 We have to consider all minimal (P,Q,R)-chains. 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (33) QDPSizeChangeProof (EQUIVALENT) 12.74/4.06 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.06 12.74/4.06 From the DPs we obtained the following set of size-change graphs: 12.74/4.06 *C(active(X)) -> C(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 *C(mark(X)) -> C(X) 12.74/4.06 The graph contains the following edges 1 > 1 12.74/4.06 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (34) 12.74/4.06 YES 12.74/4.06 12.74/4.06 ---------------------------------------- 12.74/4.06 12.74/4.06 (35) 12.74/4.06 Obligation: 12.74/4.06 Q DP problem: 12.74/4.06 The TRS P consists of the following rules: 12.74/4.06 12.74/4.06 F(active(X)) -> F(X) 12.74/4.06 F(mark(X)) -> F(X) 12.74/4.06 12.74/4.06 The TRS R consists of the following rules: 12.74/4.06 12.74/4.06 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.06 active(c(X)) -> mark(d(X)) 12.74/4.06 mark(f(X)) -> active(f(mark(X))) 12.74/4.06 mark(c(X)) -> active(c(X)) 12.74/4.06 mark(g(X)) -> active(g(X)) 12.74/4.06 mark(d(X)) -> active(d(X)) 12.74/4.06 mark(h(X)) -> active(h(mark(X))) 12.74/4.06 f(mark(X)) -> f(X) 12.74/4.06 f(active(X)) -> f(X) 12.74/4.06 c(mark(X)) -> c(X) 12.74/4.06 c(active(X)) -> c(X) 12.74/4.06 g(mark(X)) -> g(X) 12.74/4.06 g(active(X)) -> g(X) 12.74/4.06 d(mark(X)) -> d(X) 12.74/4.06 d(active(X)) -> d(X) 12.74/4.06 h(mark(X)) -> h(X) 12.74/4.06 h(active(X)) -> h(X) 12.74/4.06 12.74/4.06 The set Q consists of the following terms: 12.74/4.06 12.74/4.06 active(f(f(x0))) 12.74/4.06 active(c(x0)) 12.74/4.06 active(h(x0)) 12.74/4.06 mark(f(x0)) 12.74/4.06 mark(c(x0)) 12.74/4.06 mark(g(x0)) 12.74/4.06 mark(d(x0)) 12.74/4.06 mark(h(x0)) 12.74/4.06 f(mark(x0)) 12.74/4.06 f(active(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (36) UsableRulesProof (EQUIVALENT) 12.74/4.07 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (37) 12.74/4.07 Obligation: 12.74/4.07 Q DP problem: 12.74/4.07 The TRS P consists of the following rules: 12.74/4.07 12.74/4.07 F(active(X)) -> F(X) 12.74/4.07 F(mark(X)) -> F(X) 12.74/4.07 12.74/4.07 R is empty. 12.74/4.07 The set Q consists of the following terms: 12.74/4.07 12.74/4.07 active(f(f(x0))) 12.74/4.07 active(c(x0)) 12.74/4.07 active(h(x0)) 12.74/4.07 mark(f(x0)) 12.74/4.07 mark(c(x0)) 12.74/4.07 mark(g(x0)) 12.74/4.07 mark(d(x0)) 12.74/4.07 mark(h(x0)) 12.74/4.07 f(mark(x0)) 12.74/4.07 f(active(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (38) QReductionProof (EQUIVALENT) 12.74/4.07 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.07 12.74/4.07 f(mark(x0)) 12.74/4.07 f(active(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (39) 12.74/4.07 Obligation: 12.74/4.07 Q DP problem: 12.74/4.07 The TRS P consists of the following rules: 12.74/4.07 12.74/4.07 F(active(X)) -> F(X) 12.74/4.07 F(mark(X)) -> F(X) 12.74/4.07 12.74/4.07 R is empty. 12.74/4.07 The set Q consists of the following terms: 12.74/4.07 12.74/4.07 active(f(f(x0))) 12.74/4.07 active(c(x0)) 12.74/4.07 active(h(x0)) 12.74/4.07 mark(f(x0)) 12.74/4.07 mark(c(x0)) 12.74/4.07 mark(g(x0)) 12.74/4.07 mark(d(x0)) 12.74/4.07 mark(h(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (40) QDPSizeChangeProof (EQUIVALENT) 12.74/4.07 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.07 12.74/4.07 From the DPs we obtained the following set of size-change graphs: 12.74/4.07 *F(active(X)) -> F(X) 12.74/4.07 The graph contains the following edges 1 > 1 12.74/4.07 12.74/4.07 12.74/4.07 *F(mark(X)) -> F(X) 12.74/4.07 The graph contains the following edges 1 > 1 12.74/4.07 12.74/4.07 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (41) 12.74/4.07 YES 12.74/4.07 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (42) 12.74/4.07 Obligation: 12.74/4.07 Q DP problem: 12.74/4.07 The TRS P consists of the following rules: 12.74/4.07 12.74/4.07 MARK(h(X)) -> MARK(X) 12.74/4.07 MARK(f(X)) -> MARK(X) 12.74/4.07 12.74/4.07 The TRS R consists of the following rules: 12.74/4.07 12.74/4.07 active(f(f(X))) -> mark(c(f(g(f(X))))) 12.74/4.07 active(c(X)) -> mark(d(X)) 12.74/4.07 mark(f(X)) -> active(f(mark(X))) 12.74/4.07 mark(c(X)) -> active(c(X)) 12.74/4.07 mark(g(X)) -> active(g(X)) 12.74/4.07 mark(d(X)) -> active(d(X)) 12.74/4.07 mark(h(X)) -> active(h(mark(X))) 12.74/4.07 f(mark(X)) -> f(X) 12.74/4.07 f(active(X)) -> f(X) 12.74/4.07 c(mark(X)) -> c(X) 12.74/4.07 c(active(X)) -> c(X) 12.74/4.07 g(mark(X)) -> g(X) 12.74/4.07 g(active(X)) -> g(X) 12.74/4.07 d(mark(X)) -> d(X) 12.74/4.07 d(active(X)) -> d(X) 12.74/4.07 h(mark(X)) -> h(X) 12.74/4.07 h(active(X)) -> h(X) 12.74/4.07 12.74/4.07 The set Q consists of the following terms: 12.74/4.07 12.74/4.07 active(f(f(x0))) 12.74/4.07 active(c(x0)) 12.74/4.07 active(h(x0)) 12.74/4.07 mark(f(x0)) 12.74/4.07 mark(c(x0)) 12.74/4.07 mark(g(x0)) 12.74/4.07 mark(d(x0)) 12.74/4.07 mark(h(x0)) 12.74/4.07 f(mark(x0)) 12.74/4.07 f(active(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (43) UsableRulesProof (EQUIVALENT) 12.74/4.07 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (44) 12.74/4.07 Obligation: 12.74/4.07 Q DP problem: 12.74/4.07 The TRS P consists of the following rules: 12.74/4.07 12.74/4.07 MARK(h(X)) -> MARK(X) 12.74/4.07 MARK(f(X)) -> MARK(X) 12.74/4.07 12.74/4.07 R is empty. 12.74/4.07 The set Q consists of the following terms: 12.74/4.07 12.74/4.07 active(f(f(x0))) 12.74/4.07 active(c(x0)) 12.74/4.07 active(h(x0)) 12.74/4.07 mark(f(x0)) 12.74/4.07 mark(c(x0)) 12.74/4.07 mark(g(x0)) 12.74/4.07 mark(d(x0)) 12.74/4.07 mark(h(x0)) 12.74/4.07 f(mark(x0)) 12.74/4.07 f(active(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (45) QReductionProof (EQUIVALENT) 12.74/4.07 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.74/4.07 12.74/4.07 active(f(f(x0))) 12.74/4.07 active(c(x0)) 12.74/4.07 active(h(x0)) 12.74/4.07 mark(f(x0)) 12.74/4.07 mark(c(x0)) 12.74/4.07 mark(g(x0)) 12.74/4.07 mark(d(x0)) 12.74/4.07 mark(h(x0)) 12.74/4.07 c(mark(x0)) 12.74/4.07 c(active(x0)) 12.74/4.07 g(mark(x0)) 12.74/4.07 g(active(x0)) 12.74/4.07 d(mark(x0)) 12.74/4.07 d(active(x0)) 12.74/4.07 12.74/4.07 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (46) 12.74/4.07 Obligation: 12.74/4.07 Q DP problem: 12.74/4.07 The TRS P consists of the following rules: 12.74/4.07 12.74/4.07 MARK(h(X)) -> MARK(X) 12.74/4.07 MARK(f(X)) -> MARK(X) 12.74/4.07 12.74/4.07 R is empty. 12.74/4.07 The set Q consists of the following terms: 12.74/4.07 12.74/4.07 f(mark(x0)) 12.74/4.07 f(active(x0)) 12.74/4.07 h(mark(x0)) 12.74/4.07 h(active(x0)) 12.74/4.07 12.74/4.07 We have to consider all minimal (P,Q,R)-chains. 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (47) QDPSizeChangeProof (EQUIVALENT) 12.74/4.07 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.74/4.07 12.74/4.07 From the DPs we obtained the following set of size-change graphs: 12.74/4.07 *MARK(h(X)) -> MARK(X) 12.74/4.07 The graph contains the following edges 1 > 1 12.74/4.07 12.74/4.07 12.74/4.07 *MARK(f(X)) -> MARK(X) 12.74/4.07 The graph contains the following edges 1 > 1 12.74/4.07 12.74/4.07 12.74/4.07 ---------------------------------------- 12.74/4.07 12.74/4.07 (48) 12.74/4.07 YES 12.88/4.14 EOF