8.21/3.06 YES 8.21/3.08 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.21/3.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.21/3.08 8.21/3.08 8.21/3.08 Termination w.r.t. Q of the given QTRS could be proven: 8.21/3.08 8.21/3.08 (0) QTRS 8.21/3.08 (1) DependencyPairsProof [EQUIVALENT, 29 ms] 8.21/3.08 (2) QDP 8.21/3.08 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 8.21/3.08 (4) AND 8.21/3.08 (5) QDP 8.21/3.08 (6) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (7) QDP 8.21/3.08 (8) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (9) QDP 8.21/3.08 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (11) YES 8.21/3.08 (12) QDP 8.21/3.08 (13) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (14) QDP 8.21/3.08 (15) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (16) QDP 8.21/3.08 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (18) YES 8.21/3.08 (19) QDP 8.21/3.08 (20) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (21) QDP 8.21/3.08 (22) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (23) QDP 8.21/3.08 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (25) YES 8.21/3.08 (26) QDP 8.21/3.08 (27) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (28) QDP 8.21/3.08 (29) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (30) QDP 8.21/3.08 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (32) YES 8.21/3.08 (33) QDP 8.21/3.08 (34) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (35) QDP 8.21/3.08 (36) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (37) QDP 8.21/3.08 (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (39) YES 8.21/3.08 (40) QDP 8.21/3.08 (41) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (42) QDP 8.21/3.08 (43) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (44) QDP 8.21/3.08 (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (46) YES 8.21/3.08 (47) QDP 8.21/3.08 (48) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (49) QDP 8.21/3.08 (50) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (51) QDP 8.21/3.08 (52) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (53) YES 8.21/3.08 (54) QDP 8.21/3.08 (55) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (56) QDP 8.21/3.08 (57) QDPOrderProof [EQUIVALENT, 11 ms] 8.21/3.08 (58) QDP 8.21/3.08 (59) QDPOrderProof [EQUIVALENT, 8 ms] 8.21/3.08 (60) QDP 8.21/3.08 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 8.21/3.08 (62) QDP 8.21/3.08 (63) UsableRulesProof [EQUIVALENT, 0 ms] 8.21/3.08 (64) QDP 8.21/3.08 (65) QReductionProof [EQUIVALENT, 0 ms] 8.21/3.08 (66) QDP 8.21/3.08 (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.21/3.08 (68) YES 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (0) 8.21/3.08 Obligation: 8.21/3.08 Q restricted rewrite system: 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (1) DependencyPairsProof (EQUIVALENT) 8.21/3.08 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (2) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 ACTIVE(and(true, X)) -> MARK(X) 8.21/3.08 ACTIVE(and(false, Y)) -> MARK(false) 8.21/3.08 ACTIVE(if(true, X, Y)) -> MARK(X) 8.21/3.08 ACTIVE(if(false, X, Y)) -> MARK(Y) 8.21/3.08 ACTIVE(add(0, X)) -> MARK(X) 8.21/3.08 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 8.21/3.08 ACTIVE(add(s(X), Y)) -> S(add(X, Y)) 8.21/3.08 ACTIVE(add(s(X), Y)) -> ADD(X, Y) 8.21/3.08 ACTIVE(first(0, X)) -> MARK(nil) 8.21/3.08 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 8.21/3.08 ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z)) 8.21/3.08 ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z) 8.21/3.08 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.21/3.08 ACTIVE(from(X)) -> CONS(X, from(s(X))) 8.21/3.08 ACTIVE(from(X)) -> FROM(s(X)) 8.21/3.08 ACTIVE(from(X)) -> S(X) 8.21/3.08 MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) 8.21/3.08 MARK(and(X1, X2)) -> AND(mark(X1), X2) 8.21/3.08 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.08 MARK(true) -> ACTIVE(true) 8.21/3.08 MARK(false) -> ACTIVE(false) 8.21/3.08 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) 8.21/3.08 MARK(if(X1, X2, X3)) -> IF(mark(X1), X2, X3) 8.21/3.08 MARK(if(X1, X2, X3)) -> MARK(X1) 8.21/3.08 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) 8.21/3.08 MARK(add(X1, X2)) -> ADD(mark(X1), X2) 8.21/3.08 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.08 MARK(0) -> ACTIVE(0) 8.21/3.08 MARK(s(X)) -> ACTIVE(s(X)) 8.21/3.08 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 8.21/3.08 MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2)) 8.21/3.08 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.08 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.08 MARK(nil) -> ACTIVE(nil) 8.21/3.08 MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) 8.21/3.08 MARK(from(X)) -> ACTIVE(from(X)) 8.21/3.08 AND(mark(X1), X2) -> AND(X1, X2) 8.21/3.08 AND(X1, mark(X2)) -> AND(X1, X2) 8.21/3.08 AND(active(X1), X2) -> AND(X1, X2) 8.21/3.08 AND(X1, active(X2)) -> AND(X1, X2) 8.21/3.08 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.08 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 8.21/3.08 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 8.21/3.08 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.08 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 8.21/3.08 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 8.21/3.08 ADD(mark(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.21/3.08 ADD(active(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(X1, active(X2)) -> ADD(X1, X2) 8.21/3.08 S(mark(X)) -> S(X) 8.21/3.08 S(active(X)) -> S(X) 8.21/3.08 FIRST(mark(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 8.21/3.08 FIRST(active(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(X1, active(X2)) -> FIRST(X1, X2) 8.21/3.08 CONS(mark(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.21/3.08 CONS(active(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(X1, active(X2)) -> CONS(X1, X2) 8.21/3.08 FROM(mark(X)) -> FROM(X) 8.21/3.08 FROM(active(X)) -> FROM(X) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (3) DependencyGraphProof (EQUIVALENT) 8.21/3.08 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 8 SCCs with 23 less nodes. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (4) 8.21/3.08 Complex Obligation (AND) 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (5) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FROM(active(X)) -> FROM(X) 8.21/3.08 FROM(mark(X)) -> FROM(X) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (6) UsableRulesProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (7) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FROM(active(X)) -> FROM(X) 8.21/3.08 FROM(mark(X)) -> FROM(X) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (8) QReductionProof (EQUIVALENT) 8.21/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.08 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (9) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FROM(active(X)) -> FROM(X) 8.21/3.08 FROM(mark(X)) -> FROM(X) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (10) QDPSizeChangeProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 8.21/3.08 From the DPs we obtained the following set of size-change graphs: 8.21/3.08 *FROM(active(X)) -> FROM(X) 8.21/3.08 The graph contains the following edges 1 > 1 8.21/3.08 8.21/3.08 8.21/3.08 *FROM(mark(X)) -> FROM(X) 8.21/3.08 The graph contains the following edges 1 > 1 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (11) 8.21/3.08 YES 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (12) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.21/3.08 CONS(mark(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(active(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(X1, active(X2)) -> CONS(X1, X2) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (13) UsableRulesProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (14) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.21/3.08 CONS(mark(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(active(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(X1, active(X2)) -> CONS(X1, X2) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (15) QReductionProof (EQUIVALENT) 8.21/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.08 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (16) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.21/3.08 CONS(mark(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(active(X1), X2) -> CONS(X1, X2) 8.21/3.08 CONS(X1, active(X2)) -> CONS(X1, X2) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (17) QDPSizeChangeProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 8.21/3.08 From the DPs we obtained the following set of size-change graphs: 8.21/3.08 *CONS(X1, mark(X2)) -> CONS(X1, X2) 8.21/3.08 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.08 8.21/3.08 8.21/3.08 *CONS(mark(X1), X2) -> CONS(X1, X2) 8.21/3.08 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.08 8.21/3.08 8.21/3.08 *CONS(active(X1), X2) -> CONS(X1, X2) 8.21/3.08 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.08 8.21/3.08 8.21/3.08 *CONS(X1, active(X2)) -> CONS(X1, X2) 8.21/3.08 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (18) 8.21/3.08 YES 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (19) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 8.21/3.08 FIRST(mark(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(active(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(X1, active(X2)) -> FIRST(X1, X2) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (20) UsableRulesProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (21) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 8.21/3.08 FIRST(mark(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(active(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(X1, active(X2)) -> FIRST(X1, X2) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (22) QReductionProof (EQUIVALENT) 8.21/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.08 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (23) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 8.21/3.08 FIRST(mark(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(active(X1), X2) -> FIRST(X1, X2) 8.21/3.08 FIRST(X1, active(X2)) -> FIRST(X1, X2) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (24) QDPSizeChangeProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 8.21/3.08 From the DPs we obtained the following set of size-change graphs: 8.21/3.08 *FIRST(X1, mark(X2)) -> FIRST(X1, X2) 8.21/3.08 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.08 8.21/3.08 8.21/3.08 *FIRST(mark(X1), X2) -> FIRST(X1, X2) 8.21/3.08 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.08 8.21/3.08 8.21/3.08 *FIRST(active(X1), X2) -> FIRST(X1, X2) 8.21/3.08 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.08 8.21/3.08 8.21/3.08 *FIRST(X1, active(X2)) -> FIRST(X1, X2) 8.21/3.08 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (25) 8.21/3.08 YES 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (26) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 S(active(X)) -> S(X) 8.21/3.08 S(mark(X)) -> S(X) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (27) UsableRulesProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (28) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 S(active(X)) -> S(X) 8.21/3.08 S(mark(X)) -> S(X) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (29) QReductionProof (EQUIVALENT) 8.21/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.08 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (30) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 S(active(X)) -> S(X) 8.21/3.08 S(mark(X)) -> S(X) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (31) QDPSizeChangeProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 8.21/3.08 From the DPs we obtained the following set of size-change graphs: 8.21/3.08 *S(active(X)) -> S(X) 8.21/3.08 The graph contains the following edges 1 > 1 8.21/3.08 8.21/3.08 8.21/3.08 *S(mark(X)) -> S(X) 8.21/3.08 The graph contains the following edges 1 > 1 8.21/3.08 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (32) 8.21/3.08 YES 8.21/3.08 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (33) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.21/3.08 ADD(mark(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(active(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(X1, active(X2)) -> ADD(X1, X2) 8.21/3.08 8.21/3.08 The TRS R consists of the following rules: 8.21/3.08 8.21/3.08 active(and(true, X)) -> mark(X) 8.21/3.08 active(and(false, Y)) -> mark(false) 8.21/3.08 active(if(true, X, Y)) -> mark(X) 8.21/3.08 active(if(false, X, Y)) -> mark(Y) 8.21/3.08 active(add(0, X)) -> mark(X) 8.21/3.08 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.08 active(first(0, X)) -> mark(nil) 8.21/3.08 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.08 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.08 mark(true) -> active(true) 8.21/3.08 mark(false) -> active(false) 8.21/3.08 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.08 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.08 mark(0) -> active(0) 8.21/3.08 mark(s(X)) -> active(s(X)) 8.21/3.08 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.08 mark(nil) -> active(nil) 8.21/3.08 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.08 mark(from(X)) -> active(from(X)) 8.21/3.08 and(mark(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.08 and(active(X1), X2) -> and(X1, X2) 8.21/3.08 and(X1, active(X2)) -> and(X1, X2) 8.21/3.08 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.08 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.08 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.08 add(mark(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.08 add(active(X1), X2) -> add(X1, X2) 8.21/3.08 add(X1, active(X2)) -> add(X1, X2) 8.21/3.08 s(mark(X)) -> s(X) 8.21/3.08 s(active(X)) -> s(X) 8.21/3.08 first(mark(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.08 first(active(X1), X2) -> first(X1, X2) 8.21/3.08 first(X1, active(X2)) -> first(X1, X2) 8.21/3.08 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.08 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.08 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.08 from(mark(X)) -> from(X) 8.21/3.08 from(active(X)) -> from(X) 8.21/3.08 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.08 mark(and(x0, x1)) 8.21/3.08 mark(true) 8.21/3.08 mark(false) 8.21/3.08 mark(if(x0, x1, x2)) 8.21/3.08 mark(add(x0, x1)) 8.21/3.08 mark(0) 8.21/3.08 mark(s(x0)) 8.21/3.08 mark(first(x0, x1)) 8.21/3.08 mark(nil) 8.21/3.08 mark(cons(x0, x1)) 8.21/3.08 mark(from(x0)) 8.21/3.08 and(mark(x0), x1) 8.21/3.08 and(x0, mark(x1)) 8.21/3.08 and(active(x0), x1) 8.21/3.08 and(x0, active(x1)) 8.21/3.08 if(mark(x0), x1, x2) 8.21/3.08 if(x0, mark(x1), x2) 8.21/3.08 if(x0, x1, mark(x2)) 8.21/3.08 if(active(x0), x1, x2) 8.21/3.08 if(x0, active(x1), x2) 8.21/3.08 if(x0, x1, active(x2)) 8.21/3.08 add(mark(x0), x1) 8.21/3.08 add(x0, mark(x1)) 8.21/3.08 add(active(x0), x1) 8.21/3.08 add(x0, active(x1)) 8.21/3.08 s(mark(x0)) 8.21/3.08 s(active(x0)) 8.21/3.08 first(mark(x0), x1) 8.21/3.08 first(x0, mark(x1)) 8.21/3.08 first(active(x0), x1) 8.21/3.08 first(x0, active(x1)) 8.21/3.08 cons(mark(x0), x1) 8.21/3.08 cons(x0, mark(x1)) 8.21/3.08 cons(active(x0), x1) 8.21/3.08 cons(x0, active(x1)) 8.21/3.08 from(mark(x0)) 8.21/3.08 from(active(x0)) 8.21/3.08 8.21/3.08 We have to consider all minimal (P,Q,R)-chains. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (34) UsableRulesProof (EQUIVALENT) 8.21/3.08 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. 8.21/3.08 ---------------------------------------- 8.21/3.08 8.21/3.08 (35) 8.21/3.08 Obligation: 8.21/3.08 Q DP problem: 8.21/3.08 The TRS P consists of the following rules: 8.21/3.08 8.21/3.08 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.21/3.08 ADD(mark(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(active(X1), X2) -> ADD(X1, X2) 8.21/3.08 ADD(X1, active(X2)) -> ADD(X1, X2) 8.21/3.08 8.21/3.08 R is empty. 8.21/3.08 The set Q consists of the following terms: 8.21/3.08 8.21/3.08 active(and(true, x0)) 8.21/3.08 active(and(false, x0)) 8.21/3.08 active(if(true, x0, x1)) 8.21/3.08 active(if(false, x0, x1)) 8.21/3.08 active(add(0, x0)) 8.21/3.08 active(add(s(x0), x1)) 8.21/3.08 active(first(0, x0)) 8.21/3.08 active(first(s(x0), cons(x1, x2))) 8.21/3.08 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (36) QReductionProof (EQUIVALENT) 8.21/3.09 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.09 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (37) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.21/3.09 ADD(mark(X1), X2) -> ADD(X1, X2) 8.21/3.09 ADD(active(X1), X2) -> ADD(X1, X2) 8.21/3.09 ADD(X1, active(X2)) -> ADD(X1, X2) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (38) QDPSizeChangeProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 8.21/3.09 From the DPs we obtained the following set of size-change graphs: 8.21/3.09 *ADD(X1, mark(X2)) -> ADD(X1, X2) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.09 8.21/3.09 8.21/3.09 *ADD(mark(X1), X2) -> ADD(X1, X2) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.09 8.21/3.09 8.21/3.09 *ADD(active(X1), X2) -> ADD(X1, X2) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.09 8.21/3.09 8.21/3.09 *ADD(X1, active(X2)) -> ADD(X1, X2) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (39) 8.21/3.09 YES 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (40) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 8.21/3.09 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 s(mark(X)) -> s(X) 8.21/3.09 s(active(X)) -> s(X) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.09 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.09 from(mark(X)) -> from(X) 8.21/3.09 from(active(X)) -> from(X) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (41) UsableRulesProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (42) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 8.21/3.09 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (43) QReductionProof (EQUIVALENT) 8.21/3.09 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.09 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (44) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 8.21/3.09 IF(active(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, active(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (45) QDPSizeChangeProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 8.21/3.09 From the DPs we obtained the following set of size-change graphs: 8.21/3.09 *IF(X1, mark(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 8.21/3.09 8.21/3.09 8.21/3.09 *IF(mark(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 8.21/3.09 8.21/3.09 8.21/3.09 *IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 8.21/3.09 8.21/3.09 8.21/3.09 *IF(active(X1), X2, X3) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 8.21/3.09 8.21/3.09 8.21/3.09 *IF(X1, active(X2), X3) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 8.21/3.09 8.21/3.09 8.21/3.09 *IF(X1, X2, active(X3)) -> IF(X1, X2, X3) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (46) 8.21/3.09 YES 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (47) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 AND(X1, mark(X2)) -> AND(X1, X2) 8.21/3.09 AND(mark(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(active(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(X1, active(X2)) -> AND(X1, X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 s(mark(X)) -> s(X) 8.21/3.09 s(active(X)) -> s(X) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.09 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.09 from(mark(X)) -> from(X) 8.21/3.09 from(active(X)) -> from(X) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (48) UsableRulesProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (49) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 AND(X1, mark(X2)) -> AND(X1, X2) 8.21/3.09 AND(mark(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(active(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(X1, active(X2)) -> AND(X1, X2) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (50) QReductionProof (EQUIVALENT) 8.21/3.09 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.09 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (51) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 AND(X1, mark(X2)) -> AND(X1, X2) 8.21/3.09 AND(mark(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(active(X1), X2) -> AND(X1, X2) 8.21/3.09 AND(X1, active(X2)) -> AND(X1, X2) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (52) QDPSizeChangeProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 8.21/3.09 From the DPs we obtained the following set of size-change graphs: 8.21/3.09 *AND(X1, mark(X2)) -> AND(X1, X2) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.09 8.21/3.09 8.21/3.09 *AND(mark(X1), X2) -> AND(X1, X2) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.09 8.21/3.09 8.21/3.09 *AND(active(X1), X2) -> AND(X1, X2) 8.21/3.09 The graph contains the following edges 1 > 1, 2 >= 2 8.21/3.09 8.21/3.09 8.21/3.09 *AND(X1, active(X2)) -> AND(X1, X2) 8.21/3.09 The graph contains the following edges 1 >= 1, 2 > 2 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (53) 8.21/3.09 YES 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (54) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) 8.21/3.09 ACTIVE(and(true, X)) -> MARK(X) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) 8.21/3.09 ACTIVE(if(true, X, Y)) -> MARK(X) 8.21/3.09 MARK(if(X1, X2, X3)) -> MARK(X1) 8.21/3.09 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) 8.21/3.09 ACTIVE(if(false, X, Y)) -> MARK(Y) 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 8.21/3.09 ACTIVE(add(0, X)) -> MARK(X) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 s(mark(X)) -> s(X) 8.21/3.09 s(active(X)) -> s(X) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 cons(mark(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, mark(X2)) -> cons(X1, X2) 8.21/3.09 cons(active(X1), X2) -> cons(X1, X2) 8.21/3.09 cons(X1, active(X2)) -> cons(X1, X2) 8.21/3.09 from(mark(X)) -> from(X) 8.21/3.09 from(active(X)) -> from(X) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (55) UsableRulesProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (56) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) 8.21/3.09 ACTIVE(and(true, X)) -> MARK(X) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) 8.21/3.09 ACTIVE(if(true, X, Y)) -> MARK(X) 8.21/3.09 MARK(if(X1, X2, X3)) -> MARK(X1) 8.21/3.09 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) 8.21/3.09 ACTIVE(if(false, X, Y)) -> MARK(Y) 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 8.21/3.09 ACTIVE(add(0, X)) -> MARK(X) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (57) QDPOrderProof (EQUIVALENT) 8.21/3.09 We use the reduction pair processor [LPAR04,JAR06]. 8.21/3.09 8.21/3.09 8.21/3.09 The following pairs can be oriented strictly and are deleted. 8.21/3.09 8.21/3.09 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 8.21/3.09 The remaining pairs can at least be oriented weakly. 8.21/3.09 Used ordering: Polynomial interpretation [POLO]: 8.21/3.09 8.21/3.09 POL(0) = 0 8.21/3.09 POL(ACTIVE(x_1)) = x_1 8.21/3.09 POL(MARK(x_1)) = 1 8.21/3.09 POL(active(x_1)) = 0 8.21/3.09 POL(add(x_1, x_2)) = 1 8.21/3.09 POL(and(x_1, x_2)) = 1 8.21/3.09 POL(cons(x_1, x_2)) = x_1 8.21/3.09 POL(false) = 0 8.21/3.09 POL(first(x_1, x_2)) = 0 8.21/3.09 POL(from(x_1)) = x_1 8.21/3.09 POL(if(x_1, x_2, x_3)) = 1 8.21/3.09 POL(mark(x_1)) = 0 8.21/3.09 POL(nil) = 0 8.21/3.09 POL(s(x_1)) = 0 8.21/3.09 POL(true) = 0 8.21/3.09 8.21/3.09 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.21/3.09 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (58) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) 8.21/3.09 ACTIVE(and(true, X)) -> MARK(X) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) 8.21/3.09 ACTIVE(if(true, X, Y)) -> MARK(X) 8.21/3.09 MARK(if(X1, X2, X3)) -> MARK(X1) 8.21/3.09 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) 8.21/3.09 ACTIVE(if(false, X, Y)) -> MARK(Y) 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 ACTIVE(add(0, X)) -> MARK(X) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (59) QDPOrderProof (EQUIVALENT) 8.21/3.09 We use the reduction pair processor [LPAR04,JAR06]. 8.21/3.09 8.21/3.09 8.21/3.09 The following pairs can be oriented strictly and are deleted. 8.21/3.09 8.21/3.09 MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) 8.21/3.09 MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) 8.21/3.09 ACTIVE(if(true, X, Y)) -> MARK(X) 8.21/3.09 MARK(if(X1, X2, X3)) -> MARK(X1) 8.21/3.09 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) 8.21/3.09 ACTIVE(if(false, X, Y)) -> MARK(Y) 8.21/3.09 The remaining pairs can at least be oriented weakly. 8.21/3.09 Used ordering: Polynomial interpretation [POLO]: 8.21/3.09 8.21/3.09 POL(0) = 1 8.21/3.09 POL(ACTIVE(x_1)) = x_1 8.21/3.09 POL(MARK(x_1)) = 1 + x_1 8.21/3.09 POL(active(x_1)) = x_1 8.21/3.09 POL(add(x_1, x_2)) = x_1 + x_2 8.21/3.09 POL(and(x_1, x_2)) = x_1 + x_2 8.21/3.09 POL(cons(x_1, x_2)) = x_1 8.21/3.09 POL(false) = 1 8.21/3.09 POL(first(x_1, x_2)) = x_1 + x_2 8.21/3.09 POL(from(x_1)) = x_1 8.21/3.09 POL(if(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 8.21/3.09 POL(mark(x_1)) = x_1 8.21/3.09 POL(nil) = 0 8.21/3.09 POL(s(x_1)) = 0 8.21/3.09 POL(true) = 1 8.21/3.09 8.21/3.09 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.21/3.09 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (60) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 ACTIVE(and(true, X)) -> MARK(X) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 ACTIVE(add(0, X)) -> MARK(X) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (61) DependencyGraphProof (EQUIVALENT) 8.21/3.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (62) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 The TRS R consists of the following rules: 8.21/3.09 8.21/3.09 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.21/3.09 active(and(true, X)) -> mark(X) 8.21/3.09 mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) 8.21/3.09 active(if(true, X, Y)) -> mark(X) 8.21/3.09 mark(add(X1, X2)) -> active(add(mark(X1), X2)) 8.21/3.09 active(if(false, X, Y)) -> mark(Y) 8.21/3.09 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 8.21/3.09 active(add(0, X)) -> mark(X) 8.21/3.09 mark(true) -> active(true) 8.21/3.09 mark(false) -> active(false) 8.21/3.09 mark(0) -> active(0) 8.21/3.09 mark(s(X)) -> active(s(X)) 8.21/3.09 mark(nil) -> active(nil) 8.21/3.09 mark(cons(X1, X2)) -> active(cons(X1, X2)) 8.21/3.09 mark(from(X)) -> active(from(X)) 8.21/3.09 first(X1, mark(X2)) -> first(X1, X2) 8.21/3.09 first(mark(X1), X2) -> first(X1, X2) 8.21/3.09 first(active(X1), X2) -> first(X1, X2) 8.21/3.09 first(X1, active(X2)) -> first(X1, X2) 8.21/3.09 active(from(X)) -> mark(cons(X, from(s(X)))) 8.21/3.09 active(and(false, Y)) -> mark(false) 8.21/3.09 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.21/3.09 active(first(0, X)) -> mark(nil) 8.21/3.09 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 8.21/3.09 and(X1, mark(X2)) -> and(X1, X2) 8.21/3.09 and(mark(X1), X2) -> and(X1, X2) 8.21/3.09 and(active(X1), X2) -> and(X1, X2) 8.21/3.09 and(X1, active(X2)) -> and(X1, X2) 8.21/3.09 if(X1, mark(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(mark(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, mark(X3)) -> if(X1, X2, X3) 8.21/3.09 if(active(X1), X2, X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, active(X2), X3) -> if(X1, X2, X3) 8.21/3.09 if(X1, X2, active(X3)) -> if(X1, X2, X3) 8.21/3.09 add(X1, mark(X2)) -> add(X1, X2) 8.21/3.09 add(mark(X1), X2) -> add(X1, X2) 8.21/3.09 add(active(X1), X2) -> add(X1, X2) 8.21/3.09 add(X1, active(X2)) -> add(X1, X2) 8.21/3.09 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (63) UsableRulesProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (64) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (65) QReductionProof (EQUIVALENT) 8.21/3.09 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.21/3.09 8.21/3.09 active(and(true, x0)) 8.21/3.09 active(and(false, x0)) 8.21/3.09 active(if(true, x0, x1)) 8.21/3.09 active(if(false, x0, x1)) 8.21/3.09 active(add(0, x0)) 8.21/3.09 active(add(s(x0), x1)) 8.21/3.09 active(first(0, x0)) 8.21/3.09 active(first(s(x0), cons(x1, x2))) 8.21/3.09 active(from(x0)) 8.21/3.09 mark(and(x0, x1)) 8.21/3.09 mark(true) 8.21/3.09 mark(false) 8.21/3.09 mark(if(x0, x1, x2)) 8.21/3.09 mark(add(x0, x1)) 8.21/3.09 mark(0) 8.21/3.09 mark(s(x0)) 8.21/3.09 mark(first(x0, x1)) 8.21/3.09 mark(nil) 8.21/3.09 mark(cons(x0, x1)) 8.21/3.09 mark(from(x0)) 8.21/3.09 if(mark(x0), x1, x2) 8.21/3.09 if(x0, mark(x1), x2) 8.21/3.09 if(x0, x1, mark(x2)) 8.21/3.09 if(active(x0), x1, x2) 8.21/3.09 if(x0, active(x1), x2) 8.21/3.09 if(x0, x1, active(x2)) 8.21/3.09 s(mark(x0)) 8.21/3.09 s(active(x0)) 8.21/3.09 cons(mark(x0), x1) 8.21/3.09 cons(x0, mark(x1)) 8.21/3.09 cons(active(x0), x1) 8.21/3.09 cons(x0, active(x1)) 8.21/3.09 from(mark(x0)) 8.21/3.09 from(active(x0)) 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (66) 8.21/3.09 Obligation: 8.21/3.09 Q DP problem: 8.21/3.09 The TRS P consists of the following rules: 8.21/3.09 8.21/3.09 MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 8.21/3.09 R is empty. 8.21/3.09 The set Q consists of the following terms: 8.21/3.09 8.21/3.09 and(mark(x0), x1) 8.21/3.09 and(x0, mark(x1)) 8.21/3.09 and(active(x0), x1) 8.21/3.09 and(x0, active(x1)) 8.21/3.09 add(mark(x0), x1) 8.21/3.09 add(x0, mark(x1)) 8.21/3.09 add(active(x0), x1) 8.21/3.09 add(x0, active(x1)) 8.21/3.09 first(mark(x0), x1) 8.21/3.09 first(x0, mark(x1)) 8.21/3.09 first(active(x0), x1) 8.21/3.09 first(x0, active(x1)) 8.21/3.09 8.21/3.09 We have to consider all minimal (P,Q,R)-chains. 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (67) QDPSizeChangeProof (EQUIVALENT) 8.21/3.09 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. 8.21/3.09 8.21/3.09 From the DPs we obtained the following set of size-change graphs: 8.21/3.09 *MARK(add(X1, X2)) -> MARK(X1) 8.21/3.09 The graph contains the following edges 1 > 1 8.21/3.09 8.21/3.09 8.21/3.09 *MARK(and(X1, X2)) -> MARK(X1) 8.21/3.09 The graph contains the following edges 1 > 1 8.21/3.09 8.21/3.09 8.21/3.09 *MARK(first(X1, X2)) -> MARK(X1) 8.21/3.09 The graph contains the following edges 1 > 1 8.21/3.09 8.21/3.09 8.21/3.09 *MARK(first(X1, X2)) -> MARK(X2) 8.21/3.09 The graph contains the following edges 1 > 1 8.21/3.09 8.21/3.09 8.21/3.09 ---------------------------------------- 8.21/3.09 8.21/3.09 (68) 8.21/3.09 YES 8.21/3.11 EOF