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