5.22/2.32 NO 5.22/2.33 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.22/2.33 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.22/2.33 5.22/2.33 5.22/2.33 Termination w.r.t. Q of the given QTRS could be disproven: 5.22/2.33 5.22/2.33 (0) QTRS 5.22/2.33 (1) QTRSRRRProof [EQUIVALENT, 77 ms] 5.22/2.33 (2) QTRS 5.22/2.33 (3) QTRSRRRProof [EQUIVALENT, 0 ms] 5.22/2.33 (4) QTRS 5.22/2.33 (5) QTRSRRRProof [EQUIVALENT, 7 ms] 5.22/2.33 (6) QTRS 5.22/2.33 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 5.22/2.33 (8) QTRS 5.22/2.33 (9) DependencyPairsProof [EQUIVALENT, 0 ms] 5.22/2.33 (10) QDP 5.22/2.33 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 5.22/2.33 (12) AND 5.22/2.33 (13) QDP 5.22/2.33 (14) UsableRulesProof [EQUIVALENT, 0 ms] 5.22/2.33 (15) QDP 5.22/2.33 (16) QReductionProof [EQUIVALENT, 0 ms] 5.22/2.33 (17) QDP 5.22/2.33 (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.22/2.33 (19) YES 5.22/2.33 (20) QDP 5.22/2.33 (21) UsableRulesProof [EQUIVALENT, 0 ms] 5.22/2.33 (22) QDP 5.22/2.33 (23) QReductionProof [EQUIVALENT, 0 ms] 5.22/2.33 (24) QDP 5.22/2.33 (25) MRRProof [EQUIVALENT, 0 ms] 5.22/2.33 (26) QDP 5.22/2.33 (27) TransformationProof [EQUIVALENT, 0 ms] 5.22/2.33 (28) QDP 5.22/2.33 (29) UsableRulesProof [EQUIVALENT, 0 ms] 5.22/2.33 (30) QDP 5.22/2.33 (31) QReductionProof [EQUIVALENT, 0 ms] 5.22/2.33 (32) QDP 5.22/2.33 (33) TransformationProof [EQUIVALENT, 0 ms] 5.22/2.33 (34) QDP 5.22/2.33 (35) UsableRulesProof [EQUIVALENT, 0 ms] 5.22/2.33 (36) QDP 5.22/2.33 (37) QReductionProof [EQUIVALENT, 0 ms] 5.22/2.33 (38) QDP 5.22/2.33 (39) TransformationProof [EQUIVALENT, 0 ms] 5.22/2.33 (40) QDP 5.22/2.33 (41) NonTerminationLoopProof [COMPLETE, 0 ms] 5.22/2.33 (42) NO 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (0) 5.22/2.33 Obligation: 5.22/2.33 Q restricted rewrite system: 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__and(tt, X) -> mark(X) 5.22/2.33 a__length(nil) -> 0 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.22/2.33 mark(length(X)) -> a__length(mark(X)) 5.22/2.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.22/2.33 mark(0) -> 0 5.22/2.33 mark(tt) -> tt 5.22/2.33 mark(nil) -> nil 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 a__zeros -> zeros 5.22/2.33 a__and(X1, X2) -> and(X1, X2) 5.22/2.33 a__length(X) -> length(X) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (1) QTRSRRRProof (EQUIVALENT) 5.22/2.33 Used ordering: 5.22/2.33 Polynomial interpretation [POLO]: 5.22/2.33 5.22/2.33 POL(0) = 0 5.22/2.33 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 5.22/2.33 POL(a__length(x_1)) = 2 + x_1 5.22/2.33 POL(a__zeros) = 0 5.22/2.33 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 5.22/2.33 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.22/2.33 POL(length(x_1)) = 1 + x_1 5.22/2.33 POL(mark(x_1)) = 2*x_1 5.22/2.33 POL(nil) = 2 5.22/2.33 POL(s(x_1)) = x_1 5.22/2.33 POL(tt) = 2 5.22/2.33 POL(zeros) = 0 5.22/2.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.22/2.33 5.22/2.33 a__and(tt, X) -> mark(X) 5.22/2.33 a__length(nil) -> 0 5.22/2.33 mark(tt) -> tt 5.22/2.33 mark(nil) -> nil 5.22/2.33 a__length(X) -> length(X) 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (2) 5.22/2.33 Obligation: 5.22/2.33 Q restricted rewrite system: 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.22/2.33 mark(length(X)) -> a__length(mark(X)) 5.22/2.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.22/2.33 mark(0) -> 0 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 a__zeros -> zeros 5.22/2.33 a__and(X1, X2) -> and(X1, X2) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (3) QTRSRRRProof (EQUIVALENT) 5.22/2.33 Used ordering: 5.22/2.33 Polynomial interpretation [POLO]: 5.22/2.33 5.22/2.33 POL(0) = 0 5.22/2.33 POL(a__and(x_1, x_2)) = 2 + x_1 + 2*x_2 5.22/2.33 POL(a__length(x_1)) = 2*x_1 5.22/2.33 POL(a__zeros) = 2 5.22/2.33 POL(and(x_1, x_2)) = 1 + x_1 + x_2 5.22/2.33 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.22/2.33 POL(length(x_1)) = 2 + 2*x_1 5.22/2.33 POL(mark(x_1)) = 2*x_1 5.22/2.33 POL(s(x_1)) = x_1 5.22/2.33 POL(zeros) = 1 5.22/2.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.22/2.33 5.22/2.33 mark(length(X)) -> a__length(mark(X)) 5.22/2.33 a__zeros -> zeros 5.22/2.33 a__and(X1, X2) -> and(X1, X2) 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (4) 5.22/2.33 Obligation: 5.22/2.33 Q restricted rewrite system: 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.22/2.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.22/2.33 mark(0) -> 0 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (5) QTRSRRRProof (EQUIVALENT) 5.22/2.33 Used ordering: 5.22/2.33 Polynomial interpretation [POLO]: 5.22/2.33 5.22/2.33 POL(0) = 0 5.22/2.33 POL(a__and(x_1, x_2)) = 1 + x_1 + 2*x_2 5.22/2.33 POL(a__length(x_1)) = 2*x_1 5.22/2.33 POL(a__zeros) = 0 5.22/2.33 POL(and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.22/2.33 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.22/2.33 POL(mark(x_1)) = x_1 5.22/2.33 POL(s(x_1)) = 2*x_1 5.22/2.33 POL(zeros) = 0 5.22/2.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.22/2.33 5.22/2.33 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (6) 5.22/2.33 Obligation: 5.22/2.33 Q restricted rewrite system: 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.22/2.33 mark(0) -> 0 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (7) QTRSRRRProof (EQUIVALENT) 5.22/2.33 Used ordering: 5.22/2.33 Polynomial interpretation [POLO]: 5.22/2.33 5.22/2.33 POL(0) = 0 5.22/2.33 POL(a__length(x_1)) = 2*x_1 5.22/2.33 POL(a__zeros) = 2 5.22/2.33 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 5.22/2.33 POL(mark(x_1)) = 2 + 2*x_1 5.22/2.33 POL(s(x_1)) = x_1 5.22/2.33 POL(zeros) = 0 5.22/2.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.22/2.33 5.22/2.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.22/2.33 mark(0) -> 0 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (8) 5.22/2.33 Obligation: 5.22/2.33 Q restricted rewrite system: 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (9) DependencyPairsProof (EQUIVALENT) 5.22/2.33 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (10) 5.22/2.33 Obligation: 5.22/2.33 Q DP problem: 5.22/2.33 The TRS P consists of the following rules: 5.22/2.33 5.22/2.33 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 5.22/2.33 A__LENGTH(cons(N, L)) -> MARK(L) 5.22/2.33 MARK(zeros) -> A__ZEROS 5.22/2.33 MARK(s(X)) -> MARK(X) 5.22/2.33 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 We have to consider all minimal (P,Q,R)-chains. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (11) DependencyGraphProof (EQUIVALENT) 5.22/2.33 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (12) 5.22/2.33 Complex Obligation (AND) 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (13) 5.22/2.33 Obligation: 5.22/2.33 Q DP problem: 5.22/2.33 The TRS P consists of the following rules: 5.22/2.33 5.22/2.33 MARK(s(X)) -> MARK(X) 5.22/2.33 5.22/2.33 The TRS R consists of the following rules: 5.22/2.33 5.22/2.33 a__zeros -> cons(0, zeros) 5.22/2.33 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.33 mark(zeros) -> a__zeros 5.22/2.33 mark(s(X)) -> s(mark(X)) 5.22/2.33 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 We have to consider all minimal (P,Q,R)-chains. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (14) UsableRulesProof (EQUIVALENT) 5.22/2.33 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (15) 5.22/2.33 Obligation: 5.22/2.33 Q DP problem: 5.22/2.33 The TRS P consists of the following rules: 5.22/2.33 5.22/2.33 MARK(s(X)) -> MARK(X) 5.22/2.33 5.22/2.33 R is empty. 5.22/2.33 The set Q consists of the following terms: 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 We have to consider all minimal (P,Q,R)-chains. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (16) QReductionProof (EQUIVALENT) 5.22/2.33 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.22/2.33 5.22/2.33 a__zeros 5.22/2.33 mark(zeros) 5.22/2.33 mark(and(x0, x1)) 5.22/2.33 mark(length(x0)) 5.22/2.33 mark(cons(x0, x1)) 5.22/2.33 mark(0) 5.22/2.33 mark(tt) 5.22/2.33 mark(nil) 5.22/2.33 mark(s(x0)) 5.22/2.33 a__and(x0, x1) 5.22/2.33 a__length(x0) 5.22/2.33 5.22/2.33 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (17) 5.22/2.33 Obligation: 5.22/2.33 Q DP problem: 5.22/2.33 The TRS P consists of the following rules: 5.22/2.33 5.22/2.33 MARK(s(X)) -> MARK(X) 5.22/2.33 5.22/2.33 R is empty. 5.22/2.33 Q is empty. 5.22/2.33 We have to consider all minimal (P,Q,R)-chains. 5.22/2.33 ---------------------------------------- 5.22/2.33 5.22/2.33 (18) QDPSizeChangeProof (EQUIVALENT) 5.22/2.33 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.22/2.33 5.22/2.33 From the DPs we obtained the following set of size-change graphs: 5.22/2.34 *MARK(s(X)) -> MARK(X) 5.22/2.34 The graph contains the following edges 1 > 1 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (19) 5.22/2.34 YES 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (20) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 a__length(cons(N, L)) -> s(a__length(mark(L))) 5.22/2.34 mark(zeros) -> a__zeros 5.22/2.34 mark(s(X)) -> s(mark(X)) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 a__and(x0, x1) 5.22/2.34 a__length(x0) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (21) UsableRulesProof (EQUIVALENT) 5.22/2.34 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (22) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 mark(zeros) -> a__zeros 5.22/2.34 mark(s(X)) -> s(mark(X)) 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 a__and(x0, x1) 5.22/2.34 a__length(x0) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (23) QReductionProof (EQUIVALENT) 5.22/2.34 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.22/2.34 5.22/2.34 a__and(x0, x1) 5.22/2.34 a__length(x0) 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (24) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 mark(zeros) -> a__zeros 5.22/2.34 mark(s(X)) -> s(mark(X)) 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (25) MRRProof (EQUIVALENT) 5.22/2.34 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.22/2.34 5.22/2.34 5.22/2.34 Strictly oriented rules of the TRS R: 5.22/2.34 5.22/2.34 mark(s(X)) -> s(mark(X)) 5.22/2.34 5.22/2.34 Used ordering: Polynomial interpretation [POLO]: 5.22/2.34 5.22/2.34 POL(0) = 0 5.22/2.34 POL(A__LENGTH(x_1)) = 2*x_1 5.22/2.34 POL(a__zeros) = 0 5.22/2.34 POL(cons(x_1, x_2)) = x_1 + 2*x_2 5.22/2.34 POL(mark(x_1)) = 2*x_1 5.22/2.34 POL(s(x_1)) = 1 + 2*x_1 5.22/2.34 POL(zeros) = 0 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (26) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 mark(zeros) -> a__zeros 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (27) TransformationProof (EQUIVALENT) 5.22/2.34 By narrowing [LPAR04] the rule A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) at position [0] we obtained the following new rules [LPAR04]: 5.22/2.34 5.22/2.34 (A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros),A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros)) 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (28) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 mark(zeros) -> a__zeros 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (29) UsableRulesProof (EQUIVALENT) 5.22/2.34 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (30) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (31) QReductionProof (EQUIVALENT) 5.22/2.34 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.22/2.34 5.22/2.34 mark(zeros) 5.22/2.34 mark(and(x0, x1)) 5.22/2.34 mark(length(x0)) 5.22/2.34 mark(cons(x0, x1)) 5.22/2.34 mark(0) 5.22/2.34 mark(tt) 5.22/2.34 mark(nil) 5.22/2.34 mark(s(x0)) 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (32) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (33) TransformationProof (EQUIVALENT) 5.22/2.34 By rewriting [LPAR04] the rule A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) at position [0] we obtained the following new rules [LPAR04]: 5.22/2.34 5.22/2.34 (A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)),A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros))) 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (34) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 5.22/2.34 5.22/2.34 The TRS R consists of the following rules: 5.22/2.34 5.22/2.34 a__zeros -> cons(0, zeros) 5.22/2.34 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (35) UsableRulesProof (EQUIVALENT) 5.22/2.34 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (36) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 5.22/2.34 5.22/2.34 R is empty. 5.22/2.34 The set Q consists of the following terms: 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (37) QReductionProof (EQUIVALENT) 5.22/2.34 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.22/2.34 5.22/2.34 a__zeros 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (38) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 5.22/2.34 5.22/2.34 R is empty. 5.22/2.34 Q is empty. 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (39) TransformationProof (EQUIVALENT) 5.22/2.34 By instantiating [LPAR04] the rule A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) we obtained the following new rules [LPAR04]: 5.22/2.34 5.22/2.34 (A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros)),A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros))) 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (40) 5.22/2.34 Obligation: 5.22/2.34 Q DP problem: 5.22/2.34 The TRS P consists of the following rules: 5.22/2.34 5.22/2.34 A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros)) 5.22/2.34 5.22/2.34 R is empty. 5.22/2.34 Q is empty. 5.22/2.34 We have to consider all minimal (P,Q,R)-chains. 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (41) NonTerminationLoopProof (COMPLETE) 5.22/2.34 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 5.22/2.34 Found a loop by semiunifying a rule from P directly. 5.22/2.34 5.22/2.34 s = A__LENGTH(cons(0, zeros)) evaluates to t =A__LENGTH(cons(0, zeros)) 5.22/2.34 5.22/2.34 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 5.22/2.34 * Matcher: [ ] 5.22/2.34 * Semiunifier: [ ] 5.22/2.34 5.22/2.34 -------------------------------------------------------------------------------- 5.22/2.34 Rewriting sequence 5.22/2.34 5.22/2.34 The DP semiunifies directly so there is only one rewrite step from A__LENGTH(cons(0, zeros)) to A__LENGTH(cons(0, zeros)). 5.22/2.34 5.22/2.34 5.22/2.34 5.22/2.34 5.22/2.34 ---------------------------------------- 5.22/2.34 5.22/2.34 (42) 5.22/2.34 NO 5.22/2.37 EOF