/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 62 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 0 ms] (10) QDP (11) TransformationProof [EQUIVALENT, 0 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) QDP (15) NonTerminationLoopProof [COMPLETE, 31 ms] (16) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) length(nil) -> 0 length(cons(N, L)) -> U11(tt, activate(L)) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(length(x_1)) = x_1 POL(n__zeros) = 0 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: length(nil) -> 0 ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) length(cons(N, L)) -> U11(tt, activate(L)) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, L) -> U12^1(tt, activate(L)) U11^1(tt, L) -> ACTIVATE(L) U12^1(tt, L) -> LENGTH(activate(L)) U12^1(tt, L) -> ACTIVATE(L) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) LENGTH(cons(N, L)) -> ACTIVATE(L) ACTIVATE(n__zeros) -> ZEROS The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) length(cons(N, L)) -> U11(tt, activate(L)) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) length(cons(N, L)) -> U11(tt, activate(L)) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(X) -> X zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U12^1(tt, L) -> LENGTH(activate(L)) at position [0] we obtained the following new rules [LPAR04]: (U12^1(tt, n__zeros) -> LENGTH(zeros),U12^1(tt, n__zeros) -> LENGTH(zeros)) (U12^1(tt, x0) -> LENGTH(x0),U12^1(tt, x0) -> LENGTH(x0)) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, n__zeros) -> LENGTH(zeros) U12^1(tt, x0) -> LENGTH(x0) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(X) -> X zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U12^1(tt, n__zeros) -> LENGTH(zeros) at position [0] we obtained the following new rules [LPAR04]: (U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)),U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros))) (U12^1(tt, n__zeros) -> LENGTH(n__zeros),U12^1(tt, n__zeros) -> LENGTH(n__zeros)) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, x0) -> LENGTH(x0) U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) U12^1(tt, n__zeros) -> LENGTH(n__zeros) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(X) -> X zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, x0) -> LENGTH(x0) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(X) -> X zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = U12^1(tt, activate(activate(n__zeros))) evaluates to t =U12^1(tt, activate(activate(n__zeros))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U12^1(tt, activate(activate(n__zeros))) -> U12^1(tt, activate(n__zeros)) with rule activate(X) -> X at position [1] and matcher [X / activate(n__zeros)] U12^1(tt, activate(n__zeros)) -> U12^1(tt, n__zeros) with rule activate(X) -> X at position [1] and matcher [X / n__zeros] U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) with rule U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) at position [] and matcher [ ] LENGTH(cons(0, n__zeros)) -> U11^1(tt, activate(n__zeros)) with rule LENGTH(cons(N, L')) -> U11^1(tt, activate(L')) at position [] and matcher [N / 0, L' / n__zeros] U11^1(tt, activate(n__zeros)) -> U12^1(tt, activate(activate(n__zeros))) with rule U11^1(tt, L) -> U12^1(tt, activate(L)) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (16) NO