5.51/2.40 YES 5.86/2.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.86/2.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.86/2.41 5.86/2.41 5.86/2.41 Termination w.r.t. Q of the given QTRS could be proven: 5.86/2.41 5.86/2.41 (0) QTRS 5.86/2.41 (1) QTRSRRRProof [EQUIVALENT, 73 ms] 5.86/2.41 (2) QTRS 5.86/2.41 (3) QTRSRRRProof [EQUIVALENT, 19 ms] 5.86/2.41 (4) QTRS 5.86/2.41 (5) DependencyPairsProof [EQUIVALENT, 39 ms] 5.86/2.41 (6) QDP 5.86/2.41 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.41 (8) AND 5.86/2.41 (9) QDP 5.86/2.41 (10) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.41 (11) QDP 5.86/2.41 (12) QReductionProof [EQUIVALENT, 0 ms] 5.86/2.41 (13) QDP 5.86/2.41 (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.86/2.41 (15) YES 5.86/2.41 (16) QDP 5.86/2.41 (17) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.41 (18) QDP 5.86/2.41 (19) QReductionProof [EQUIVALENT, 0 ms] 5.86/2.41 (20) QDP 5.86/2.41 (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.86/2.41 (22) YES 5.86/2.41 (23) QDP 5.86/2.41 (24) MRRProof [EQUIVALENT, 29 ms] 5.86/2.41 (25) QDP 5.86/2.41 (26) QDPOrderProof [EQUIVALENT, 20 ms] 5.86/2.41 (27) QDP 5.86/2.41 (28) DependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.41 (29) TRUE 5.86/2.41 5.86/2.41 5.86/2.41 ---------------------------------------- 5.86/2.41 5.86/2.41 (0) 5.86/2.41 Obligation: 5.86/2.41 Q restricted rewrite system: 5.86/2.41 The TRS R consists of the following rules: 5.86/2.41 5.86/2.41 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.41 active(if(true, X, Y)) -> mark(X) 5.86/2.41 active(if(false, X, Y)) -> mark(Y) 5.86/2.41 mark(f(X)) -> active(f(mark(X))) 5.86/2.41 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.41 mark(c) -> active(c) 5.86/2.41 mark(true) -> active(true) 5.86/2.41 mark(false) -> active(false) 5.86/2.41 f(mark(X)) -> f(X) 5.86/2.41 f(active(X)) -> f(X) 5.86/2.41 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.41 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.41 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.41 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.41 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.41 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.41 5.86/2.41 The set Q consists of the following terms: 5.86/2.41 5.86/2.41 active(f(x0)) 5.86/2.41 active(if(true, x0, x1)) 5.86/2.41 active(if(false, x0, x1)) 5.86/2.41 mark(f(x0)) 5.86/2.41 mark(if(x0, x1, x2)) 5.86/2.41 mark(c) 5.86/2.41 mark(true) 5.86/2.41 mark(false) 5.86/2.41 f(mark(x0)) 5.86/2.41 f(active(x0)) 5.86/2.41 if(mark(x0), x1, x2) 5.86/2.41 if(x0, mark(x1), x2) 5.86/2.41 if(x0, x1, mark(x2)) 5.86/2.41 if(active(x0), x1, x2) 5.86/2.41 if(x0, active(x1), x2) 5.86/2.41 if(x0, x1, active(x2)) 5.86/2.41 5.86/2.41 5.86/2.41 ---------------------------------------- 5.86/2.41 5.86/2.41 (1) QTRSRRRProof (EQUIVALENT) 5.86/2.41 Used ordering: 5.86/2.41 Polynomial interpretation [POLO]: 5.86/2.41 5.86/2.41 POL(active(x_1)) = x_1 5.86/2.41 POL(c) = 0 5.86/2.41 POL(f(x_1)) = x_1 5.86/2.41 POL(false) = 1 5.86/2.41 POL(if(x_1, x_2, x_3)) = x_1 + x_2 + x_3 5.86/2.41 POL(mark(x_1)) = x_1 5.86/2.41 POL(true) = 0 5.86/2.41 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.41 5.86/2.41 active(if(false, X, Y)) -> mark(Y) 5.86/2.41 5.86/2.41 5.86/2.41 5.86/2.41 5.86/2.41 ---------------------------------------- 5.86/2.41 5.86/2.41 (2) 5.86/2.41 Obligation: 5.86/2.41 Q restricted rewrite system: 5.86/2.41 The TRS R consists of the following rules: 5.86/2.41 5.86/2.41 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.41 active(if(true, X, Y)) -> mark(X) 5.86/2.41 mark(f(X)) -> active(f(mark(X))) 5.86/2.41 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.41 mark(c) -> active(c) 5.86/2.41 mark(true) -> active(true) 5.86/2.41 mark(false) -> active(false) 5.86/2.41 f(mark(X)) -> f(X) 5.86/2.41 f(active(X)) -> f(X) 5.86/2.41 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (3) QTRSRRRProof (EQUIVALENT) 5.86/2.42 Used ordering: 5.86/2.42 Polynomial interpretation [POLO]: 5.86/2.42 5.86/2.42 POL(active(x_1)) = x_1 5.86/2.42 POL(c) = 0 5.86/2.42 POL(f(x_1)) = 2*x_1 5.86/2.42 POL(false) = 1 5.86/2.42 POL(if(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 5.86/2.42 POL(mark(x_1)) = 2*x_1 5.86/2.42 POL(true) = 0 5.86/2.42 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.42 5.86/2.42 mark(false) -> active(false) 5.86/2.42 5.86/2.42 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (4) 5.86/2.42 Obligation: 5.86/2.42 Q restricted rewrite system: 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (5) DependencyPairsProof (EQUIVALENT) 5.86/2.42 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (6) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 ACTIVE(f(X)) -> MARK(if(X, c, f(true))) 5.86/2.42 ACTIVE(f(X)) -> IF(X, c, f(true)) 5.86/2.42 ACTIVE(f(X)) -> F(true) 5.86/2.42 ACTIVE(if(true, X, Y)) -> MARK(X) 5.86/2.42 MARK(f(X)) -> ACTIVE(f(mark(X))) 5.86/2.42 MARK(f(X)) -> F(mark(X)) 5.86/2.42 MARK(f(X)) -> MARK(X) 5.86/2.42 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), mark(X2), X3)) 5.86/2.42 MARK(if(X1, X2, X3)) -> IF(mark(X1), mark(X2), X3) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X1) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X2) 5.86/2.42 MARK(c) -> ACTIVE(c) 5.86/2.42 MARK(true) -> ACTIVE(true) 5.86/2.42 F(mark(X)) -> F(X) 5.86/2.42 F(active(X)) -> F(X) 5.86/2.42 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 5.86/2.42 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (7) DependencyGraphProof (EQUIVALENT) 5.86/2.42 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 6 less nodes. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (8) 5.86/2.42 Complex Obligation (AND) 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (9) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 5.86/2.42 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (10) UsableRulesProof (EQUIVALENT) 5.86/2.42 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. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (11) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 5.86/2.42 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 5.86/2.42 5.86/2.42 R is empty. 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (12) QReductionProof (EQUIVALENT) 5.86/2.42 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.86/2.42 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (13) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 5.86/2.42 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 5.86/2.42 5.86/2.42 R is empty. 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (14) QDPSizeChangeProof (EQUIVALENT) 5.86/2.42 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. 5.86/2.42 5.86/2.42 From the DPs we obtained the following set of size-change graphs: 5.86/2.42 *IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 5.86/2.42 5.86/2.42 5.86/2.42 *IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 5.86/2.42 5.86/2.42 5.86/2.42 *IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 5.86/2.42 5.86/2.42 5.86/2.42 *IF(active(X1), X2, X3) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 5.86/2.42 5.86/2.42 5.86/2.42 *IF(X1, active(X2), X3) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 5.86/2.42 5.86/2.42 5.86/2.42 *IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 5.86/2.42 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (15) 5.86/2.42 YES 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (16) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 F(active(X)) -> F(X) 5.86/2.42 F(mark(X)) -> F(X) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (17) UsableRulesProof (EQUIVALENT) 5.86/2.42 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. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (18) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 F(active(X)) -> F(X) 5.86/2.42 F(mark(X)) -> F(X) 5.86/2.42 5.86/2.42 R is empty. 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (19) QReductionProof (EQUIVALENT) 5.86/2.42 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.86/2.42 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (20) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 F(active(X)) -> F(X) 5.86/2.42 F(mark(X)) -> F(X) 5.86/2.42 5.86/2.42 R is empty. 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (21) QDPSizeChangeProof (EQUIVALENT) 5.86/2.42 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. 5.86/2.42 5.86/2.42 From the DPs we obtained the following set of size-change graphs: 5.86/2.42 *F(active(X)) -> F(X) 5.86/2.42 The graph contains the following edges 1 > 1 5.86/2.42 5.86/2.42 5.86/2.42 *F(mark(X)) -> F(X) 5.86/2.42 The graph contains the following edges 1 > 1 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (22) 5.86/2.42 YES 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (23) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), mark(X2), X3)) 5.86/2.42 ACTIVE(f(X)) -> MARK(if(X, c, f(true))) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X1) 5.86/2.42 MARK(f(X)) -> ACTIVE(f(mark(X))) 5.86/2.42 ACTIVE(if(true, X, Y)) -> MARK(X) 5.86/2.42 MARK(f(X)) -> MARK(X) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X2) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (24) MRRProof (EQUIVALENT) 5.86/2.42 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. 5.86/2.42 5.86/2.42 Strictly oriented dependency pairs: 5.86/2.42 5.86/2.42 MARK(f(X)) -> MARK(X) 5.86/2.42 5.86/2.42 5.86/2.42 Used ordering: Polynomial interpretation [POLO]: 5.86/2.42 5.86/2.42 POL(ACTIVE(x_1)) = 2 + x_1 5.86/2.42 POL(MARK(x_1)) = 2 + x_1 5.86/2.42 POL(active(x_1)) = x_1 5.86/2.42 POL(c) = 0 5.86/2.42 POL(f(x_1)) = 2 + 2*x_1 5.86/2.42 POL(if(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 5.86/2.42 POL(mark(x_1)) = x_1 5.86/2.42 POL(true) = 0 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (25) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), mark(X2), X3)) 5.86/2.42 ACTIVE(f(X)) -> MARK(if(X, c, f(true))) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X1) 5.86/2.42 MARK(f(X)) -> ACTIVE(f(mark(X))) 5.86/2.42 ACTIVE(if(true, X, Y)) -> MARK(X) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X2) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (26) QDPOrderProof (EQUIVALENT) 5.86/2.42 We use the reduction pair processor [LPAR04,JAR06]. 5.86/2.42 5.86/2.42 5.86/2.42 The following pairs can be oriented strictly and are deleted. 5.86/2.42 5.86/2.42 ACTIVE(f(X)) -> MARK(if(X, c, f(true))) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X1) 5.86/2.42 ACTIVE(if(true, X, Y)) -> MARK(X) 5.86/2.42 MARK(if(X1, X2, X3)) -> MARK(X2) 5.86/2.42 The remaining pairs can at least be oriented weakly. 5.86/2.42 Used ordering: Combined order from the following AFS and order. 5.86/2.42 MARK(x1) = x1 5.86/2.42 5.86/2.42 if(x1, x2, x3) = if(x1, x2) 5.86/2.42 5.86/2.42 ACTIVE(x1) = x1 5.86/2.42 5.86/2.42 mark(x1) = x1 5.86/2.42 5.86/2.42 f(x1) = f(x1) 5.86/2.42 5.86/2.42 c = c 5.86/2.42 5.86/2.42 true = true 5.86/2.42 5.86/2.42 active(x1) = x1 5.86/2.42 5.86/2.42 5.86/2.42 Knuth-Bendix order [KBO] with precedence:trivial 5.86/2.42 5.86/2.42 and weight map: 5.86/2.42 5.86/2.42 true=1 5.86/2.42 c=2 5.86/2.42 f_1=4 5.86/2.42 if_2=1 5.86/2.42 5.86/2.42 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 5.86/2.42 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 5.86/2.42 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (27) 5.86/2.42 Obligation: 5.86/2.42 Q DP problem: 5.86/2.42 The TRS P consists of the following rules: 5.86/2.42 5.86/2.42 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), mark(X2), X3)) 5.86/2.42 MARK(f(X)) -> ACTIVE(f(mark(X))) 5.86/2.42 5.86/2.42 The TRS R consists of the following rules: 5.86/2.42 5.86/2.42 active(f(X)) -> mark(if(X, c, f(true))) 5.86/2.42 active(if(true, X, Y)) -> mark(X) 5.86/2.42 mark(f(X)) -> active(f(mark(X))) 5.86/2.42 mark(if(X1, X2, X3)) -> active(if(mark(X1), mark(X2), X3)) 5.86/2.42 mark(c) -> active(c) 5.86/2.42 mark(true) -> active(true) 5.86/2.42 f(mark(X)) -> f(X) 5.86/2.42 f(active(X)) -> f(X) 5.86/2.42 if(mark(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, mark(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 5.86/2.42 if(active(X1), X2, X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, active(X2), X3) -> if(X1, X2, X3) 5.86/2.42 if(X1, X2, active(X3)) -> if(X1, X2, X3) 5.86/2.42 5.86/2.42 The set Q consists of the following terms: 5.86/2.42 5.86/2.42 active(f(x0)) 5.86/2.42 active(if(true, x0, x1)) 5.86/2.42 active(if(false, x0, x1)) 5.86/2.42 mark(f(x0)) 5.86/2.42 mark(if(x0, x1, x2)) 5.86/2.42 mark(c) 5.86/2.42 mark(true) 5.86/2.42 mark(false) 5.86/2.42 f(mark(x0)) 5.86/2.42 f(active(x0)) 5.86/2.42 if(mark(x0), x1, x2) 5.86/2.42 if(x0, mark(x1), x2) 5.86/2.42 if(x0, x1, mark(x2)) 5.86/2.42 if(active(x0), x1, x2) 5.86/2.42 if(x0, active(x1), x2) 5.86/2.42 if(x0, x1, active(x2)) 5.86/2.42 5.86/2.42 We have to consider all minimal (P,Q,R)-chains. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (28) DependencyGraphProof (EQUIVALENT) 5.86/2.42 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 5.86/2.42 ---------------------------------------- 5.86/2.42 5.86/2.42 (29) 5.86/2.42 TRUE 5.86/2.45 EOF