7.69/7.58 YES 7.69/7.59 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.69/7.59 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.69/7.59 7.69/7.59 7.69/7.59 Termination w.r.t. Q of the given QTRS could be proven: 7.69/7.59 7.69/7.59 (0) QTRS 7.69/7.59 (1) DependencyPairsProof [EQUIVALENT, 26 ms] 7.69/7.59 (2) QDP 7.69/7.59 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 7.69/7.59 (4) AND 7.69/7.59 (5) QDP 7.69/7.59 (6) UsableRulesProof [EQUIVALENT, 0 ms] 7.69/7.59 (7) QDP 7.69/7.59 (8) QReductionProof [EQUIVALENT, 0 ms] 7.69/7.59 (9) QDP 7.69/7.59 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.69/7.59 (11) YES 7.69/7.59 (12) QDP 7.69/7.59 (13) UsableRulesProof [EQUIVALENT, 0 ms] 7.69/7.59 (14) QDP 7.69/7.59 (15) QReductionProof [EQUIVALENT, 0 ms] 7.69/7.59 (16) QDP 7.69/7.59 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.69/7.59 (18) YES 7.69/7.59 (19) QDP 7.69/7.59 (20) UsableRulesProof [EQUIVALENT, 0 ms] 7.69/7.59 (21) QDP 7.69/7.59 (22) QReductionProof [EQUIVALENT, 0 ms] 7.69/7.59 (23) QDP 7.69/7.59 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.69/7.59 (25) YES 7.69/7.59 (26) QDP 7.69/7.59 (27) UsableRulesProof [EQUIVALENT, 0 ms] 7.69/7.59 (28) QDP 7.69/7.59 (29) QReductionProof [EQUIVALENT, 0 ms] 7.69/7.59 (30) QDP 7.69/7.59 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.69/7.59 (32) YES 7.69/7.59 (33) QDP 7.69/7.59 (34) QDPOrderProof [EQUIVALENT, 48 ms] 7.69/7.59 (35) QDP 7.69/7.59 (36) QDPOrderProof [EQUIVALENT, 11 ms] 7.69/7.59 (37) QDP 7.69/7.59 (38) QDPOrderProof [EQUIVALENT, 0 ms] 7.69/7.59 (39) QDP 7.69/7.59 (40) DependencyGraphProof [EQUIVALENT, 0 ms] 7.69/7.59 (41) QDP 7.69/7.59 (42) UsableRulesProof [EQUIVALENT, 0 ms] 7.69/7.59 (43) QDP 7.69/7.59 (44) QReductionProof [EQUIVALENT, 0 ms] 7.69/7.59 (45) QDP 7.69/7.59 (46) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.69/7.59 (47) YES 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (0) 7.69/7.59 Obligation: 7.69/7.59 Q restricted rewrite system: 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (1) DependencyPairsProof (EQUIVALENT) 7.69/7.59 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (2) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 ACTIVE(first(0, X)) -> MARK(nil) 7.69/7.59 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 7.69/7.59 ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z)) 7.69/7.59 ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z) 7.69/7.59 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 7.69/7.59 ACTIVE(from(X)) -> CONS(X, from(s(X))) 7.69/7.59 ACTIVE(from(X)) -> FROM(s(X)) 7.69/7.59 ACTIVE(from(X)) -> S(X) 7.69/7.59 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 7.69/7.59 MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2)) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X2) 7.69/7.59 MARK(0) -> ACTIVE(0) 7.69/7.59 MARK(nil) -> ACTIVE(nil) 7.69/7.59 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.69/7.59 MARK(s(X)) -> S(mark(X)) 7.69/7.59 MARK(s(X)) -> MARK(X) 7.69/7.59 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.69/7.59 MARK(cons(X1, X2)) -> CONS(mark(X1), X2) 7.69/7.59 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(from(X)) -> ACTIVE(from(mark(X))) 7.69/7.59 MARK(from(X)) -> FROM(mark(X)) 7.69/7.59 MARK(from(X)) -> MARK(X) 7.69/7.59 FIRST(mark(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 7.69/7.59 FIRST(active(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(X1, active(X2)) -> FIRST(X1, X2) 7.69/7.59 S(mark(X)) -> S(X) 7.69/7.59 S(active(X)) -> S(X) 7.69/7.59 CONS(mark(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.69/7.59 CONS(active(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(X1, active(X2)) -> CONS(X1, X2) 7.69/7.59 FROM(mark(X)) -> FROM(X) 7.69/7.59 FROM(active(X)) -> FROM(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (3) DependencyGraphProof (EQUIVALENT) 7.69/7.59 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 12 less nodes. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (4) 7.69/7.59 Complex Obligation (AND) 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (5) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FROM(active(X)) -> FROM(X) 7.69/7.59 FROM(mark(X)) -> FROM(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (6) UsableRulesProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (7) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FROM(active(X)) -> FROM(X) 7.69/7.59 FROM(mark(X)) -> FROM(X) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (8) QReductionProof (EQUIVALENT) 7.69/7.59 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.69/7.59 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (9) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FROM(active(X)) -> FROM(X) 7.69/7.59 FROM(mark(X)) -> FROM(X) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (10) QDPSizeChangeProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 7.69/7.59 From the DPs we obtained the following set of size-change graphs: 7.69/7.59 *FROM(active(X)) -> FROM(X) 7.69/7.59 The graph contains the following edges 1 > 1 7.69/7.59 7.69/7.59 7.69/7.59 *FROM(mark(X)) -> FROM(X) 7.69/7.59 The graph contains the following edges 1 > 1 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (11) 7.69/7.59 YES 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (12) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.69/7.59 CONS(mark(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(active(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(X1, active(X2)) -> CONS(X1, X2) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (13) UsableRulesProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (14) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.69/7.59 CONS(mark(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(active(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(X1, active(X2)) -> CONS(X1, X2) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (15) QReductionProof (EQUIVALENT) 7.69/7.59 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.69/7.59 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (16) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.69/7.59 CONS(mark(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(active(X1), X2) -> CONS(X1, X2) 7.69/7.59 CONS(X1, active(X2)) -> CONS(X1, X2) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (17) QDPSizeChangeProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 7.69/7.59 From the DPs we obtained the following set of size-change graphs: 7.69/7.59 *CONS(X1, mark(X2)) -> CONS(X1, X2) 7.69/7.59 The graph contains the following edges 1 >= 1, 2 > 2 7.69/7.59 7.69/7.59 7.69/7.59 *CONS(mark(X1), X2) -> CONS(X1, X2) 7.69/7.59 The graph contains the following edges 1 > 1, 2 >= 2 7.69/7.59 7.69/7.59 7.69/7.59 *CONS(active(X1), X2) -> CONS(X1, X2) 7.69/7.59 The graph contains the following edges 1 > 1, 2 >= 2 7.69/7.59 7.69/7.59 7.69/7.59 *CONS(X1, active(X2)) -> CONS(X1, X2) 7.69/7.59 The graph contains the following edges 1 >= 1, 2 > 2 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (18) 7.69/7.59 YES 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (19) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 S(active(X)) -> S(X) 7.69/7.59 S(mark(X)) -> S(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (20) UsableRulesProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (21) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 S(active(X)) -> S(X) 7.69/7.59 S(mark(X)) -> S(X) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (22) QReductionProof (EQUIVALENT) 7.69/7.59 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.69/7.59 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (23) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 S(active(X)) -> S(X) 7.69/7.59 S(mark(X)) -> S(X) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (24) QDPSizeChangeProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 7.69/7.59 From the DPs we obtained the following set of size-change graphs: 7.69/7.59 *S(active(X)) -> S(X) 7.69/7.59 The graph contains the following edges 1 > 1 7.69/7.59 7.69/7.59 7.69/7.59 *S(mark(X)) -> S(X) 7.69/7.59 The graph contains the following edges 1 > 1 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (25) 7.69/7.59 YES 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (26) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 7.69/7.59 FIRST(mark(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(active(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(X1, active(X2)) -> FIRST(X1, X2) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (27) UsableRulesProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (28) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 7.69/7.59 FIRST(mark(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(active(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(X1, active(X2)) -> FIRST(X1, X2) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (29) QReductionProof (EQUIVALENT) 7.69/7.59 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.69/7.59 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (30) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 7.69/7.59 FIRST(mark(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(active(X1), X2) -> FIRST(X1, X2) 7.69/7.59 FIRST(X1, active(X2)) -> FIRST(X1, X2) 7.69/7.59 7.69/7.59 R is empty. 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (31) QDPSizeChangeProof (EQUIVALENT) 7.69/7.59 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. 7.69/7.59 7.69/7.59 From the DPs we obtained the following set of size-change graphs: 7.69/7.59 *FIRST(X1, mark(X2)) -> FIRST(X1, X2) 7.69/7.59 The graph contains the following edges 1 >= 1, 2 > 2 7.69/7.59 7.69/7.59 7.69/7.59 *FIRST(mark(X1), X2) -> FIRST(X1, X2) 7.69/7.59 The graph contains the following edges 1 > 1, 2 >= 2 7.69/7.59 7.69/7.59 7.69/7.59 *FIRST(active(X1), X2) -> FIRST(X1, X2) 7.69/7.59 The graph contains the following edges 1 > 1, 2 >= 2 7.69/7.59 7.69/7.59 7.69/7.59 *FIRST(X1, active(X2)) -> FIRST(X1, X2) 7.69/7.59 The graph contains the following edges 1 >= 1, 2 > 2 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (32) 7.69/7.59 YES 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (33) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 7.69/7.59 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.69/7.59 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 7.69/7.59 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X2) 7.69/7.59 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.69/7.59 MARK(s(X)) -> MARK(X) 7.69/7.59 MARK(from(X)) -> ACTIVE(from(mark(X))) 7.69/7.59 MARK(from(X)) -> MARK(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (34) QDPOrderProof (EQUIVALENT) 7.69/7.59 We use the reduction pair processor [LPAR04,JAR06]. 7.69/7.59 7.69/7.59 7.69/7.59 The following pairs can be oriented strictly and are deleted. 7.69/7.59 7.69/7.59 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> MARK(X2) 7.69/7.59 The remaining pairs can at least be oriented weakly. 7.69/7.59 Used ordering: Combined order from the following AFS and order. 7.69/7.59 ACTIVE(x1) = x1 7.69/7.59 7.69/7.59 first(x1, x2) = first(x1, x2) 7.69/7.59 7.69/7.59 s(x1) = x1 7.69/7.59 7.69/7.59 cons(x1, x2) = x1 7.69/7.59 7.69/7.59 MARK(x1) = x1 7.69/7.59 7.69/7.59 mark(x1) = x1 7.69/7.59 7.69/7.59 from(x1) = x1 7.69/7.59 7.69/7.59 active(x1) = x1 7.69/7.59 7.69/7.59 0 = 0 7.69/7.59 7.69/7.59 nil = nil 7.69/7.59 7.69/7.59 7.69/7.59 Knuth-Bendix order [KBO] with precedence:trivial 7.69/7.59 7.69/7.59 and weight map: 7.69/7.59 7.69/7.59 0=2 7.69/7.59 first_2=2 7.69/7.59 nil=4 7.69/7.59 7.69/7.59 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.69/7.59 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (35) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.69/7.59 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 7.69/7.59 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 7.69/7.59 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.69/7.59 MARK(s(X)) -> MARK(X) 7.69/7.59 MARK(from(X)) -> ACTIVE(from(mark(X))) 7.69/7.59 MARK(from(X)) -> MARK(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (36) QDPOrderProof (EQUIVALENT) 7.69/7.59 We use the reduction pair processor [LPAR04,JAR06]. 7.69/7.59 7.69/7.59 7.69/7.59 The following pairs can be oriented strictly and are deleted. 7.69/7.59 7.69/7.59 MARK(s(X)) -> MARK(X) 7.69/7.59 The remaining pairs can at least be oriented weakly. 7.69/7.59 Used ordering: Combined order from the following AFS and order. 7.69/7.59 MARK(x1) = x1 7.69/7.59 7.69/7.59 cons(x1, x2) = x1 7.69/7.59 7.69/7.59 ACTIVE(x1) = x1 7.69/7.59 7.69/7.59 mark(x1) = x1 7.69/7.59 7.69/7.59 from(x1) = x1 7.69/7.59 7.69/7.59 first(x1, x2) = x2 7.69/7.59 7.69/7.59 s(x1) = s(x1) 7.69/7.59 7.69/7.59 active(x1) = x1 7.69/7.59 7.69/7.59 0 = 0 7.69/7.59 7.69/7.59 nil = nil 7.69/7.59 7.69/7.59 7.69/7.59 Knuth-Bendix order [KBO] with precedence:trivial 7.69/7.59 7.69/7.59 and weight map: 7.69/7.59 7.69/7.59 s_1=1 7.69/7.59 0=2 7.69/7.59 nil=1 7.69/7.59 7.69/7.59 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.69/7.59 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 7.69/7.59 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (37) 7.69/7.59 Obligation: 7.69/7.59 Q DP problem: 7.69/7.59 The TRS P consists of the following rules: 7.69/7.59 7.69/7.59 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.69/7.59 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 7.69/7.59 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.59 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 7.69/7.59 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.69/7.59 MARK(from(X)) -> ACTIVE(from(mark(X))) 7.69/7.59 MARK(from(X)) -> MARK(X) 7.69/7.59 7.69/7.59 The TRS R consists of the following rules: 7.69/7.59 7.69/7.59 active(first(0, X)) -> mark(nil) 7.69/7.59 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.59 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.59 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.59 mark(0) -> active(0) 7.69/7.59 mark(nil) -> active(nil) 7.69/7.59 mark(s(X)) -> active(s(mark(X))) 7.69/7.59 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.59 mark(from(X)) -> active(from(mark(X))) 7.69/7.59 first(mark(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.59 first(active(X1), X2) -> first(X1, X2) 7.69/7.59 first(X1, active(X2)) -> first(X1, X2) 7.69/7.59 s(mark(X)) -> s(X) 7.69/7.59 s(active(X)) -> s(X) 7.69/7.59 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.59 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.59 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.59 from(mark(X)) -> from(X) 7.69/7.59 from(active(X)) -> from(X) 7.69/7.59 7.69/7.59 The set Q consists of the following terms: 7.69/7.59 7.69/7.59 active(first(0, x0)) 7.69/7.59 active(first(s(x0), cons(x1, x2))) 7.69/7.59 active(from(x0)) 7.69/7.59 mark(first(x0, x1)) 7.69/7.59 mark(0) 7.69/7.59 mark(nil) 7.69/7.59 mark(s(x0)) 7.69/7.59 mark(cons(x0, x1)) 7.69/7.59 mark(from(x0)) 7.69/7.59 first(mark(x0), x1) 7.69/7.59 first(x0, mark(x1)) 7.69/7.59 first(active(x0), x1) 7.69/7.59 first(x0, active(x1)) 7.69/7.59 s(mark(x0)) 7.69/7.59 s(active(x0)) 7.69/7.59 cons(mark(x0), x1) 7.69/7.59 cons(x0, mark(x1)) 7.69/7.59 cons(active(x0), x1) 7.69/7.59 cons(x0, active(x1)) 7.69/7.59 from(mark(x0)) 7.69/7.59 from(active(x0)) 7.69/7.59 7.69/7.59 We have to consider all minimal (P,Q,R)-chains. 7.69/7.59 ---------------------------------------- 7.69/7.59 7.69/7.59 (38) QDPOrderProof (EQUIVALENT) 7.69/7.59 We use the reduction pair processor [LPAR04,JAR06]. 7.69/7.59 7.69/7.59 7.69/7.59 The following pairs can be oriented strictly and are deleted. 7.69/7.59 7.69/7.59 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 7.69/7.59 MARK(from(X)) -> MARK(X) 7.69/7.59 The remaining pairs can at least be oriented weakly. 7.69/7.59 Used ordering: Combined order from the following AFS and order. 7.69/7.59 MARK(x1) = x1 7.69/7.59 7.69/7.59 cons(x1, x2) = x1 7.69/7.59 7.69/7.59 ACTIVE(x1) = x1 7.69/7.59 7.69/7.59 mark(x1) = x1 7.69/7.59 7.69/7.59 from(x1) = from(x1) 7.69/7.59 7.69/7.59 first(x1, x2) = x2 7.69/7.59 7.69/7.59 s(x1) = s 7.69/7.59 7.69/7.59 active(x1) = x1 7.69/7.59 7.69/7.59 0 = 0 7.69/7.59 7.69/7.59 nil = nil 7.69/7.59 7.69/7.59 7.69/7.59 Knuth-Bendix order [KBO] with precedence:trivial 7.69/7.59 7.69/7.59 and weight map: 7.69/7.59 7.69/7.59 s=2 7.69/7.59 0=2 7.69/7.59 from_1=1 7.69/7.59 nil=1 7.69/7.59 7.69/7.59 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.69/7.60 7.69/7.60 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.60 mark(0) -> active(0) 7.69/7.60 mark(nil) -> active(nil) 7.69/7.60 mark(s(X)) -> active(s(mark(X))) 7.69/7.60 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.60 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.60 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.60 mark(from(X)) -> active(from(mark(X))) 7.69/7.60 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.60 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.60 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.60 first(mark(X1), X2) -> first(X1, X2) 7.69/7.60 first(active(X1), X2) -> first(X1, X2) 7.69/7.60 first(X1, active(X2)) -> first(X1, X2) 7.69/7.60 s(active(X)) -> s(X) 7.69/7.60 s(mark(X)) -> s(X) 7.69/7.60 from(active(X)) -> from(X) 7.69/7.60 from(mark(X)) -> from(X) 7.69/7.60 active(first(0, X)) -> mark(nil) 7.69/7.60 7.69/7.60 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (39) 7.69/7.60 Obligation: 7.69/7.60 Q DP problem: 7.69/7.60 The TRS P consists of the following rules: 7.69/7.60 7.69/7.60 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.69/7.60 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.60 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 7.69/7.60 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.69/7.60 MARK(from(X)) -> ACTIVE(from(mark(X))) 7.69/7.60 7.69/7.60 The TRS R consists of the following rules: 7.69/7.60 7.69/7.60 active(first(0, X)) -> mark(nil) 7.69/7.60 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.60 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.60 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.60 mark(0) -> active(0) 7.69/7.60 mark(nil) -> active(nil) 7.69/7.60 mark(s(X)) -> active(s(mark(X))) 7.69/7.60 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.60 mark(from(X)) -> active(from(mark(X))) 7.69/7.60 first(mark(X1), X2) -> first(X1, X2) 7.69/7.60 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.60 first(active(X1), X2) -> first(X1, X2) 7.69/7.60 first(X1, active(X2)) -> first(X1, X2) 7.69/7.60 s(mark(X)) -> s(X) 7.69/7.60 s(active(X)) -> s(X) 7.69/7.60 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.60 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.60 from(mark(X)) -> from(X) 7.69/7.60 from(active(X)) -> from(X) 7.69/7.60 7.69/7.60 The set Q consists of the following terms: 7.69/7.60 7.69/7.60 active(first(0, x0)) 7.69/7.60 active(first(s(x0), cons(x1, x2))) 7.69/7.60 active(from(x0)) 7.69/7.60 mark(first(x0, x1)) 7.69/7.60 mark(0) 7.69/7.60 mark(nil) 7.69/7.60 mark(s(x0)) 7.69/7.60 mark(cons(x0, x1)) 7.69/7.60 mark(from(x0)) 7.69/7.60 first(mark(x0), x1) 7.69/7.60 first(x0, mark(x1)) 7.69/7.60 first(active(x0), x1) 7.69/7.60 first(x0, active(x1)) 7.69/7.60 s(mark(x0)) 7.69/7.60 s(active(x0)) 7.69/7.60 cons(mark(x0), x1) 7.69/7.60 cons(x0, mark(x1)) 7.69/7.60 cons(active(x0), x1) 7.69/7.60 cons(x0, active(x1)) 7.69/7.60 from(mark(x0)) 7.69/7.60 from(active(x0)) 7.69/7.60 7.69/7.60 We have to consider all minimal (P,Q,R)-chains. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (40) DependencyGraphProof (EQUIVALENT) 7.69/7.60 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (41) 7.69/7.60 Obligation: 7.69/7.60 Q DP problem: 7.69/7.60 The TRS P consists of the following rules: 7.69/7.60 7.69/7.60 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.60 7.69/7.60 The TRS R consists of the following rules: 7.69/7.60 7.69/7.60 active(first(0, X)) -> mark(nil) 7.69/7.60 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 7.69/7.60 active(from(X)) -> mark(cons(X, from(s(X)))) 7.69/7.60 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 7.69/7.60 mark(0) -> active(0) 7.69/7.60 mark(nil) -> active(nil) 7.69/7.60 mark(s(X)) -> active(s(mark(X))) 7.69/7.60 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.69/7.60 mark(from(X)) -> active(from(mark(X))) 7.69/7.60 first(mark(X1), X2) -> first(X1, X2) 7.69/7.60 first(X1, mark(X2)) -> first(X1, X2) 7.69/7.60 first(active(X1), X2) -> first(X1, X2) 7.69/7.60 first(X1, active(X2)) -> first(X1, X2) 7.69/7.60 s(mark(X)) -> s(X) 7.69/7.60 s(active(X)) -> s(X) 7.69/7.60 cons(mark(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(X1, mark(X2)) -> cons(X1, X2) 7.69/7.60 cons(active(X1), X2) -> cons(X1, X2) 7.69/7.60 cons(X1, active(X2)) -> cons(X1, X2) 7.69/7.60 from(mark(X)) -> from(X) 7.69/7.60 from(active(X)) -> from(X) 7.69/7.60 7.69/7.60 The set Q consists of the following terms: 7.69/7.60 7.69/7.60 active(first(0, x0)) 7.69/7.60 active(first(s(x0), cons(x1, x2))) 7.69/7.60 active(from(x0)) 7.69/7.60 mark(first(x0, x1)) 7.69/7.60 mark(0) 7.69/7.60 mark(nil) 7.69/7.60 mark(s(x0)) 7.69/7.60 mark(cons(x0, x1)) 7.69/7.60 mark(from(x0)) 7.69/7.60 first(mark(x0), x1) 7.69/7.60 first(x0, mark(x1)) 7.69/7.60 first(active(x0), x1) 7.69/7.60 first(x0, active(x1)) 7.69/7.60 s(mark(x0)) 7.69/7.60 s(active(x0)) 7.69/7.60 cons(mark(x0), x1) 7.69/7.60 cons(x0, mark(x1)) 7.69/7.60 cons(active(x0), x1) 7.69/7.60 cons(x0, active(x1)) 7.69/7.60 from(mark(x0)) 7.69/7.60 from(active(x0)) 7.69/7.60 7.69/7.60 We have to consider all minimal (P,Q,R)-chains. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (42) UsableRulesProof (EQUIVALENT) 7.69/7.60 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. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (43) 7.69/7.60 Obligation: 7.69/7.60 Q DP problem: 7.69/7.60 The TRS P consists of the following rules: 7.69/7.60 7.69/7.60 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.60 7.69/7.60 R is empty. 7.69/7.60 The set Q consists of the following terms: 7.69/7.60 7.69/7.60 active(first(0, x0)) 7.69/7.60 active(first(s(x0), cons(x1, x2))) 7.69/7.60 active(from(x0)) 7.69/7.60 mark(first(x0, x1)) 7.69/7.60 mark(0) 7.69/7.60 mark(nil) 7.69/7.60 mark(s(x0)) 7.69/7.60 mark(cons(x0, x1)) 7.69/7.60 mark(from(x0)) 7.69/7.60 first(mark(x0), x1) 7.69/7.60 first(x0, mark(x1)) 7.69/7.60 first(active(x0), x1) 7.69/7.60 first(x0, active(x1)) 7.69/7.60 s(mark(x0)) 7.69/7.60 s(active(x0)) 7.69/7.60 cons(mark(x0), x1) 7.69/7.60 cons(x0, mark(x1)) 7.69/7.60 cons(active(x0), x1) 7.69/7.60 cons(x0, active(x1)) 7.69/7.60 from(mark(x0)) 7.69/7.60 from(active(x0)) 7.69/7.60 7.69/7.60 We have to consider all minimal (P,Q,R)-chains. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (44) QReductionProof (EQUIVALENT) 7.69/7.60 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.69/7.60 7.69/7.60 active(first(0, x0)) 7.69/7.60 active(first(s(x0), cons(x1, x2))) 7.69/7.60 active(from(x0)) 7.69/7.60 mark(first(x0, x1)) 7.69/7.60 mark(0) 7.69/7.60 mark(nil) 7.69/7.60 mark(s(x0)) 7.69/7.60 mark(cons(x0, x1)) 7.69/7.60 mark(from(x0)) 7.69/7.60 first(mark(x0), x1) 7.69/7.60 first(x0, mark(x1)) 7.69/7.60 first(active(x0), x1) 7.69/7.60 first(x0, active(x1)) 7.69/7.60 s(mark(x0)) 7.69/7.60 s(active(x0)) 7.69/7.60 from(mark(x0)) 7.69/7.60 from(active(x0)) 7.69/7.60 7.69/7.60 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (45) 7.69/7.60 Obligation: 7.69/7.60 Q DP problem: 7.69/7.60 The TRS P consists of the following rules: 7.69/7.60 7.69/7.60 MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.60 7.69/7.60 R is empty. 7.69/7.60 The set Q consists of the following terms: 7.69/7.60 7.69/7.60 cons(mark(x0), x1) 7.69/7.60 cons(x0, mark(x1)) 7.69/7.60 cons(active(x0), x1) 7.69/7.60 cons(x0, active(x1)) 7.69/7.60 7.69/7.60 We have to consider all minimal (P,Q,R)-chains. 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (46) QDPSizeChangeProof (EQUIVALENT) 7.69/7.60 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. 7.69/7.60 7.69/7.60 From the DPs we obtained the following set of size-change graphs: 7.69/7.60 *MARK(cons(X1, X2)) -> MARK(X1) 7.69/7.60 The graph contains the following edges 1 > 1 7.69/7.60 7.69/7.60 7.69/7.60 ---------------------------------------- 7.69/7.60 7.69/7.60 (47) 7.69/7.60 YES 7.88/7.64 EOF