3.86/1.87 YES 3.86/1.88 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.86/1.88 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.86/1.88 3.86/1.88 3.86/1.88 Termination w.r.t. Q of the given QTRS could be proven: 3.86/1.88 3.86/1.88 (0) QTRS 3.86/1.88 (1) DependencyPairsProof [EQUIVALENT, 10 ms] 3.86/1.88 (2) QDP 3.86/1.88 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 3.86/1.88 (4) AND 3.86/1.88 (5) QDP 3.86/1.88 (6) UsableRulesProof [EQUIVALENT, 0 ms] 3.86/1.88 (7) QDP 3.86/1.88 (8) QReductionProof [EQUIVALENT, 0 ms] 3.86/1.88 (9) QDP 3.86/1.88 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.86/1.88 (11) YES 3.86/1.88 (12) QDP 3.86/1.88 (13) MRRProof [EQUIVALENT, 29 ms] 3.86/1.88 (14) QDP 3.86/1.88 (15) TransformationProof [EQUIVALENT, 0 ms] 3.86/1.88 (16) QDP 3.86/1.88 (17) UsableRulesProof [EQUIVALENT, 0 ms] 3.86/1.88 (18) QDP 3.86/1.88 (19) TransformationProof [EQUIVALENT, 0 ms] 3.86/1.88 (20) QDP 3.86/1.88 (21) UsableRulesProof [EQUIVALENT, 0 ms] 3.86/1.88 (22) QDP 3.86/1.88 (23) TransformationProof [EQUIVALENT, 0 ms] 3.86/1.88 (24) QDP 3.86/1.88 (25) UsableRulesProof [EQUIVALENT, 0 ms] 3.86/1.88 (26) QDP 3.86/1.88 (27) TransformationProof [EQUIVALENT, 0 ms] 3.86/1.88 (28) QDP 3.86/1.88 (29) UsableRulesProof [EQUIVALENT, 0 ms] 3.86/1.88 (30) QDP 3.86/1.88 (31) TransformationProof [EQUIVALENT, 0 ms] 3.86/1.88 (32) QDP 3.86/1.88 (33) DependencyGraphProof [EQUIVALENT, 0 ms] 3.86/1.88 (34) TRUE 3.86/1.88 3.86/1.88 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (0) 3.86/1.88 Obligation: 3.86/1.88 Q restricted rewrite system: 3.86/1.88 The TRS R consists of the following rules: 3.86/1.88 3.86/1.88 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.88 active(b) -> mark(a) 3.86/1.88 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.88 mark(a) -> active(a) 3.86/1.88 mark(b) -> active(b) 3.86/1.88 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.88 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.88 3.86/1.88 The set Q consists of the following terms: 3.86/1.88 3.86/1.88 active(f(a, x0, x0)) 3.86/1.88 active(b) 3.86/1.88 mark(f(x0, x1, x2)) 3.86/1.88 mark(a) 3.86/1.88 mark(b) 3.86/1.88 f(mark(x0), x1, x2) 3.86/1.88 f(x0, mark(x1), x2) 3.86/1.88 f(x0, x1, mark(x2)) 3.86/1.88 f(active(x0), x1, x2) 3.86/1.88 f(x0, active(x1), x2) 3.86/1.88 f(x0, x1, active(x2)) 3.86/1.88 3.86/1.88 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (1) DependencyPairsProof (EQUIVALENT) 3.86/1.88 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (2) 3.86/1.88 Obligation: 3.86/1.88 Q DP problem: 3.86/1.88 The TRS P consists of the following rules: 3.86/1.88 3.86/1.88 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.88 ACTIVE(f(a, X, X)) -> F(X, b, b) 3.86/1.88 ACTIVE(b) -> MARK(a) 3.86/1.88 MARK(f(X1, X2, X3)) -> ACTIVE(f(X1, mark(X2), X3)) 3.86/1.88 MARK(f(X1, X2, X3)) -> F(X1, mark(X2), X3) 3.86/1.88 MARK(f(X1, X2, X3)) -> MARK(X2) 3.86/1.88 MARK(a) -> ACTIVE(a) 3.86/1.88 MARK(b) -> ACTIVE(b) 3.86/1.88 F(mark(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, mark(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, mark(X3)) -> F(X1, X2, X3) 3.86/1.88 F(active(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, active(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, active(X3)) -> F(X1, X2, X3) 3.86/1.88 3.86/1.88 The TRS R consists of the following rules: 3.86/1.88 3.86/1.88 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.88 active(b) -> mark(a) 3.86/1.88 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.88 mark(a) -> active(a) 3.86/1.88 mark(b) -> active(b) 3.86/1.88 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.88 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.88 3.86/1.88 The set Q consists of the following terms: 3.86/1.88 3.86/1.88 active(f(a, x0, x0)) 3.86/1.88 active(b) 3.86/1.88 mark(f(x0, x1, x2)) 3.86/1.88 mark(a) 3.86/1.88 mark(b) 3.86/1.88 f(mark(x0), x1, x2) 3.86/1.88 f(x0, mark(x1), x2) 3.86/1.88 f(x0, x1, mark(x2)) 3.86/1.88 f(active(x0), x1, x2) 3.86/1.88 f(x0, active(x1), x2) 3.86/1.88 f(x0, x1, active(x2)) 3.86/1.88 3.86/1.88 We have to consider all minimal (P,Q,R)-chains. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (3) DependencyGraphProof (EQUIVALENT) 3.86/1.88 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (4) 3.86/1.88 Complex Obligation (AND) 3.86/1.88 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (5) 3.86/1.88 Obligation: 3.86/1.88 Q DP problem: 3.86/1.88 The TRS P consists of the following rules: 3.86/1.88 3.86/1.88 F(X1, mark(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(mark(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, mark(X3)) -> F(X1, X2, X3) 3.86/1.88 F(active(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, active(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, active(X3)) -> F(X1, X2, X3) 3.86/1.88 3.86/1.88 The TRS R consists of the following rules: 3.86/1.88 3.86/1.88 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.88 active(b) -> mark(a) 3.86/1.88 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.88 mark(a) -> active(a) 3.86/1.88 mark(b) -> active(b) 3.86/1.88 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.88 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.88 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.88 3.86/1.88 The set Q consists of the following terms: 3.86/1.88 3.86/1.88 active(f(a, x0, x0)) 3.86/1.88 active(b) 3.86/1.88 mark(f(x0, x1, x2)) 3.86/1.88 mark(a) 3.86/1.88 mark(b) 3.86/1.88 f(mark(x0), x1, x2) 3.86/1.88 f(x0, mark(x1), x2) 3.86/1.88 f(x0, x1, mark(x2)) 3.86/1.88 f(active(x0), x1, x2) 3.86/1.88 f(x0, active(x1), x2) 3.86/1.88 f(x0, x1, active(x2)) 3.86/1.88 3.86/1.88 We have to consider all minimal (P,Q,R)-chains. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (6) UsableRulesProof (EQUIVALENT) 3.86/1.88 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. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (7) 3.86/1.88 Obligation: 3.86/1.88 Q DP problem: 3.86/1.88 The TRS P consists of the following rules: 3.86/1.88 3.86/1.88 F(X1, mark(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(mark(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, mark(X3)) -> F(X1, X2, X3) 3.86/1.88 F(active(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, active(X2), X3) -> F(X1, X2, X3) 3.86/1.88 F(X1, X2, active(X3)) -> F(X1, X2, X3) 3.86/1.88 3.86/1.88 R is empty. 3.86/1.88 The set Q consists of the following terms: 3.86/1.88 3.86/1.88 active(f(a, x0, x0)) 3.86/1.88 active(b) 3.86/1.88 mark(f(x0, x1, x2)) 3.86/1.88 mark(a) 3.86/1.88 mark(b) 3.86/1.88 f(mark(x0), x1, x2) 3.86/1.88 f(x0, mark(x1), x2) 3.86/1.88 f(x0, x1, mark(x2)) 3.86/1.88 f(active(x0), x1, x2) 3.86/1.88 f(x0, active(x1), x2) 3.86/1.88 f(x0, x1, active(x2)) 3.86/1.88 3.86/1.88 We have to consider all minimal (P,Q,R)-chains. 3.86/1.88 ---------------------------------------- 3.86/1.88 3.86/1.88 (8) QReductionProof (EQUIVALENT) 3.86/1.88 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.86/1.89 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (9) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 F(X1, mark(X2), X3) -> F(X1, X2, X3) 3.86/1.89 F(mark(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.89 F(X1, X2, mark(X3)) -> F(X1, X2, X3) 3.86/1.89 F(active(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.89 F(X1, active(X2), X3) -> F(X1, X2, X3) 3.86/1.89 F(X1, X2, active(X3)) -> F(X1, X2, X3) 3.86/1.89 3.86/1.89 R is empty. 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (10) QDPSizeChangeProof (EQUIVALENT) 3.86/1.89 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. 3.86/1.89 3.86/1.89 From the DPs we obtained the following set of size-change graphs: 3.86/1.89 *F(X1, mark(X2), X3) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 3.86/1.89 3.86/1.89 3.86/1.89 *F(mark(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 3.86/1.89 3.86/1.89 3.86/1.89 *F(X1, X2, mark(X3)) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 3.86/1.89 3.86/1.89 3.86/1.89 *F(active(X1), X2, X3) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 3.86/1.89 3.86/1.89 3.86/1.89 *F(X1, active(X2), X3) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 3.86/1.89 3.86/1.89 3.86/1.89 *F(X1, X2, active(X3)) -> F(X1, X2, X3) 3.86/1.89 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (11) 3.86/1.89 YES 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (12) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 MARK(f(X1, X2, X3)) -> ACTIVE(f(X1, mark(X2), X3)) 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(X1, X2, X3)) -> MARK(X2) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.89 active(b) -> mark(a) 3.86/1.89 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 mark(b) -> active(b) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (13) MRRProof (EQUIVALENT) 3.86/1.89 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 3.86/1.89 3.86/1.89 Strictly oriented dependency pairs: 3.86/1.89 3.86/1.89 MARK(f(X1, X2, X3)) -> MARK(X2) 3.86/1.89 3.86/1.89 3.86/1.89 Used ordering: Polynomial interpretation [POLO]: 3.86/1.89 3.86/1.89 POL(ACTIVE(x_1)) = 2*x_1 3.86/1.89 POL(MARK(x_1)) = 2*x_1 3.86/1.89 POL(a) = 0 3.86/1.89 POL(active(x_1)) = x_1 3.86/1.89 POL(b) = 0 3.86/1.89 POL(f(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3 3.86/1.89 POL(mark(x_1)) = x_1 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (14) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 MARK(f(X1, X2, X3)) -> ACTIVE(f(X1, mark(X2), X3)) 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.89 active(b) -> mark(a) 3.86/1.89 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 mark(b) -> active(b) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (15) TransformationProof (EQUIVALENT) 3.86/1.89 By instantiating [LPAR04] the rule MARK(f(X1, X2, X3)) -> ACTIVE(f(X1, mark(X2), X3)) we obtained the following new rules [LPAR04]: 3.86/1.89 3.86/1.89 (MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(b), b)),MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(b), b))) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (16) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(b), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 active(f(a, X, X)) -> mark(f(X, b, b)) 3.86/1.89 active(b) -> mark(a) 3.86/1.89 mark(f(X1, X2, X3)) -> active(f(X1, mark(X2), X3)) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 mark(b) -> active(b) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (17) UsableRulesProof (EQUIVALENT) 3.86/1.89 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. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (18) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(b), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 mark(b) -> active(b) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 active(b) -> mark(a) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (19) TransformationProof (EQUIVALENT) 3.86/1.89 By rewriting [LPAR04] the rule MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(b), b)) at position [0,1] we obtained the following new rules [LPAR04]: 3.86/1.89 3.86/1.89 (MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(b), b)),MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(b), b))) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (20) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(b), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 mark(b) -> active(b) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 active(b) -> mark(a) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (21) UsableRulesProof (EQUIVALENT) 3.86/1.89 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. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (22) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(b), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 active(b) -> mark(a) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (23) TransformationProof (EQUIVALENT) 3.86/1.89 By rewriting [LPAR04] the rule MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(b), b)) at position [0,1] we obtained the following new rules [LPAR04]: 3.86/1.89 3.86/1.89 (MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(a), b)),MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(a), b))) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (24) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(a), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 active(b) -> mark(a) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 mark(a) -> active(a) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (25) UsableRulesProof (EQUIVALENT) 3.86/1.89 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. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (26) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(a), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 mark(a) -> active(a) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (27) TransformationProof (EQUIVALENT) 3.86/1.89 By rewriting [LPAR04] the rule MARK(f(z0, b, b)) -> ACTIVE(f(z0, mark(a), b)) at position [0,1] we obtained the following new rules [LPAR04]: 3.86/1.89 3.86/1.89 (MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(a), b)),MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(a), b))) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (28) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(a), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 mark(a) -> active(a) 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (29) UsableRulesProof (EQUIVALENT) 3.86/1.89 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. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (30) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(a), b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (31) TransformationProof (EQUIVALENT) 3.86/1.89 By narrowing [LPAR04] the rule MARK(f(z0, b, b)) -> ACTIVE(f(z0, active(a), b)) at position [0] we obtained the following new rules [LPAR04]: 3.86/1.89 3.86/1.89 (MARK(f(x0, b, b)) -> ACTIVE(f(x0, a, b)),MARK(f(x0, b, b)) -> ACTIVE(f(x0, a, b))) 3.86/1.89 3.86/1.89 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (32) 3.86/1.89 Obligation: 3.86/1.89 Q DP problem: 3.86/1.89 The TRS P consists of the following rules: 3.86/1.89 3.86/1.89 ACTIVE(f(a, X, X)) -> MARK(f(X, b, b)) 3.86/1.89 MARK(f(x0, b, b)) -> ACTIVE(f(x0, a, b)) 3.86/1.89 3.86/1.89 The TRS R consists of the following rules: 3.86/1.89 3.86/1.89 f(X1, mark(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(mark(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, mark(X3)) -> f(X1, X2, X3) 3.86/1.89 f(active(X1), X2, X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, active(X2), X3) -> f(X1, X2, X3) 3.86/1.89 f(X1, X2, active(X3)) -> f(X1, X2, X3) 3.86/1.89 3.86/1.89 The set Q consists of the following terms: 3.86/1.89 3.86/1.89 active(f(a, x0, x0)) 3.86/1.89 active(b) 3.86/1.89 mark(f(x0, x1, x2)) 3.86/1.89 mark(a) 3.86/1.89 mark(b) 3.86/1.89 f(mark(x0), x1, x2) 3.86/1.89 f(x0, mark(x1), x2) 3.86/1.89 f(x0, x1, mark(x2)) 3.86/1.89 f(active(x0), x1, x2) 3.86/1.89 f(x0, active(x1), x2) 3.86/1.89 f(x0, x1, active(x2)) 3.86/1.89 3.86/1.89 We have to consider all minimal (P,Q,R)-chains. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (33) DependencyGraphProof (EQUIVALENT) 3.86/1.89 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 3.86/1.89 ---------------------------------------- 3.86/1.89 3.86/1.89 (34) 3.86/1.89 TRUE 4.10/1.92 EOF