353.41/291.46 WORST_CASE(Omega(n^1), O(n^2)) 353.49/291.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 353.49/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 353.49/291.47 353.49/291.47 353.49/291.47 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.49/291.47 353.49/291.47 (0) CpxTRS 353.49/291.47 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 353.49/291.47 (2) CdtProblem 353.49/291.47 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 353.49/291.47 (4) CdtProblem 353.49/291.47 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 353.49/291.47 (6) CdtProblem 353.49/291.47 (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 353.49/291.47 (8) CdtProblem 353.49/291.47 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 353.49/291.47 (10) CdtProblem 353.49/291.47 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 36 ms] 353.49/291.47 (12) CdtProblem 353.49/291.47 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms] 353.49/291.47 (14) CdtProblem 353.49/291.47 (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 353.49/291.47 (16) BOUNDS(1, 1) 353.49/291.47 (17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 353.49/291.47 (18) TRS for Loop Detection 353.49/291.47 (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 353.49/291.47 (20) BEST 353.49/291.47 (21) proven lower bound 353.49/291.47 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 353.49/291.47 (23) BOUNDS(n^1, INF) 353.49/291.47 (24) TRS for Loop Detection 353.49/291.47 353.49/291.47 353.49/291.47 ---------------------------------------- 353.49/291.47 353.49/291.47 (0) 353.49/291.47 Obligation: 353.49/291.47 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.49/291.47 353.49/291.47 353.49/291.47 The TRS R consists of the following rules: 353.49/291.47 353.49/291.47 2nd(cons1(X, cons(Y, Z))) -> Y 353.49/291.47 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) 353.49/291.47 from(X) -> cons(X, n__from(n__s(X))) 353.49/291.47 from(X) -> n__from(X) 353.49/291.47 s(X) -> n__s(X) 353.49/291.47 activate(n__from(X)) -> from(activate(X)) 353.49/291.47 activate(n__s(X)) -> s(activate(X)) 353.49/291.47 activate(X) -> X 353.49/291.47 353.49/291.47 S is empty. 353.49/291.47 Rewrite Strategy: INNERMOST 353.49/291.47 ---------------------------------------- 353.49/291.47 353.49/291.47 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 353.49/291.47 Converted Cpx (relative) TRS to CDT 353.49/291.47 ---------------------------------------- 353.49/291.47 353.49/291.47 (2) 353.49/291.47 Obligation: 353.49/291.47 Complexity Dependency Tuples Problem 353.49/291.47 353.49/291.47 Rules: 353.49/291.47 2nd(cons1(z0, cons(z1, z2))) -> z1 353.49/291.47 2nd(cons(z0, z1)) -> 2nd(cons1(z0, activate(z1))) 353.49/291.47 from(z0) -> cons(z0, n__from(n__s(z0))) 353.49/291.48 from(z0) -> n__from(z0) 353.49/291.48 s(z0) -> n__s(z0) 353.49/291.48 activate(n__from(z0)) -> from(activate(z0)) 353.49/291.48 activate(n__s(z0)) -> s(activate(z0)) 353.49/291.48 activate(z0) -> z0 353.49/291.48 Tuples: 353.49/291.48 2ND(cons1(z0, cons(z1, z2))) -> c 353.49/291.48 2ND(cons(z0, z1)) -> c1(2ND(cons1(z0, activate(z1))), ACTIVATE(z1)) 353.49/291.48 FROM(z0) -> c2 353.49/291.48 FROM(z0) -> c3 353.49/291.48 S(z0) -> c4 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(FROM(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(S(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(z0) -> c7 353.49/291.48 S tuples: 353.49/291.48 2ND(cons1(z0, cons(z1, z2))) -> c 353.49/291.48 2ND(cons(z0, z1)) -> c1(2ND(cons1(z0, activate(z1))), ACTIVATE(z1)) 353.49/291.48 FROM(z0) -> c2 353.49/291.48 FROM(z0) -> c3 353.49/291.48 S(z0) -> c4 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(FROM(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(S(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(z0) -> c7 353.49/291.48 K tuples:none 353.49/291.48 Defined Rule Symbols: 2nd_1, from_1, s_1, activate_1 353.49/291.48 353.49/291.48 Defined Pair Symbols: 2ND_1, FROM_1, S_1, ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c, c1_2, c2, c3, c4, c5_2, c6_2, c7 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 353.49/291.48 Removed 5 trailing nodes: 353.49/291.48 ACTIVATE(z0) -> c7 353.49/291.48 S(z0) -> c4 353.49/291.48 FROM(z0) -> c2 353.49/291.48 FROM(z0) -> c3 353.49/291.48 2ND(cons1(z0, cons(z1, z2))) -> c 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (4) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules: 353.49/291.48 2nd(cons1(z0, cons(z1, z2))) -> z1 353.49/291.48 2nd(cons(z0, z1)) -> 2nd(cons1(z0, activate(z1))) 353.49/291.48 from(z0) -> cons(z0, n__from(n__s(z0))) 353.49/291.48 from(z0) -> n__from(z0) 353.49/291.48 s(z0) -> n__s(z0) 353.49/291.48 activate(n__from(z0)) -> from(activate(z0)) 353.49/291.48 activate(n__s(z0)) -> s(activate(z0)) 353.49/291.48 activate(z0) -> z0 353.49/291.48 Tuples: 353.49/291.48 2ND(cons(z0, z1)) -> c1(2ND(cons1(z0, activate(z1))), ACTIVATE(z1)) 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(FROM(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(S(activate(z0)), ACTIVATE(z0)) 353.49/291.48 S tuples: 353.49/291.48 2ND(cons(z0, z1)) -> c1(2ND(cons1(z0, activate(z1))), ACTIVATE(z1)) 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(FROM(activate(z0)), ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(S(activate(z0)), ACTIVATE(z0)) 353.49/291.48 K tuples:none 353.49/291.48 Defined Rule Symbols: 2nd_1, from_1, s_1, activate_1 353.49/291.48 353.49/291.48 Defined Pair Symbols: 2ND_1, ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c1_2, c5_2, c6_2 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 353.49/291.48 Removed 3 trailing tuple parts 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (6) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules: 353.49/291.48 2nd(cons1(z0, cons(z1, z2))) -> z1 353.49/291.48 2nd(cons(z0, z1)) -> 2nd(cons1(z0, activate(z1))) 353.49/291.48 from(z0) -> cons(z0, n__from(n__s(z0))) 353.49/291.48 from(z0) -> n__from(z0) 353.49/291.48 s(z0) -> n__s(z0) 353.49/291.48 activate(n__from(z0)) -> from(activate(z0)) 353.49/291.48 activate(n__s(z0)) -> s(activate(z0)) 353.49/291.48 activate(z0) -> z0 353.49/291.48 Tuples: 353.49/291.48 2ND(cons(z0, z1)) -> c1(ACTIVATE(z1)) 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 S tuples: 353.49/291.48 2ND(cons(z0, z1)) -> c1(ACTIVATE(z1)) 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 K tuples:none 353.49/291.48 Defined Rule Symbols: 2nd_1, from_1, s_1, activate_1 353.49/291.48 353.49/291.48 Defined Pair Symbols: 2ND_1, ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c1_1, c5_1, c6_1 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) 353.49/291.48 Removed 1 leading nodes: 353.49/291.48 2ND(cons(z0, z1)) -> c1(ACTIVATE(z1)) 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (8) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules: 353.49/291.48 2nd(cons1(z0, cons(z1, z2))) -> z1 353.49/291.48 2nd(cons(z0, z1)) -> 2nd(cons1(z0, activate(z1))) 353.49/291.48 from(z0) -> cons(z0, n__from(n__s(z0))) 353.49/291.48 from(z0) -> n__from(z0) 353.49/291.48 s(z0) -> n__s(z0) 353.49/291.48 activate(n__from(z0)) -> from(activate(z0)) 353.49/291.48 activate(n__s(z0)) -> s(activate(z0)) 353.49/291.48 activate(z0) -> z0 353.49/291.48 Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 S tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 K tuples:none 353.49/291.48 Defined Rule Symbols: 2nd_1, from_1, s_1, activate_1 353.49/291.48 353.49/291.48 Defined Pair Symbols: ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c5_1, c6_1 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 353.49/291.48 The following rules are not usable and were removed: 353.49/291.48 2nd(cons1(z0, cons(z1, z2))) -> z1 353.49/291.48 2nd(cons(z0, z1)) -> 2nd(cons1(z0, activate(z1))) 353.49/291.48 from(z0) -> cons(z0, n__from(n__s(z0))) 353.49/291.48 from(z0) -> n__from(z0) 353.49/291.48 s(z0) -> n__s(z0) 353.49/291.48 activate(n__from(z0)) -> from(activate(z0)) 353.49/291.48 activate(n__s(z0)) -> s(activate(z0)) 353.49/291.48 activate(z0) -> z0 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (10) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules:none 353.49/291.48 Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 S tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 K tuples:none 353.49/291.48 Defined Rule Symbols:none 353.49/291.48 353.49/291.48 Defined Pair Symbols: ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c5_1, c6_1 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 353.49/291.48 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 We considered the (Usable) Rules:none 353.49/291.48 And the Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 The order we found is given by the following interpretation: 353.49/291.48 353.49/291.48 Polynomial interpretation : 353.49/291.48 353.49/291.48 POL(ACTIVATE(x_1)) = [2]x_1^2 353.49/291.48 POL(c5(x_1)) = x_1 353.49/291.48 POL(c6(x_1)) = x_1 353.49/291.48 POL(n__from(x_1)) = [1] + x_1 353.49/291.48 POL(n__s(x_1)) = x_1 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (12) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules:none 353.49/291.48 Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 S tuples: 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 K tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 Defined Rule Symbols:none 353.49/291.48 353.49/291.48 Defined Pair Symbols: ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c5_1, c6_1 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 353.49/291.48 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 We considered the (Usable) Rules:none 353.49/291.48 And the Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 The order we found is given by the following interpretation: 353.49/291.48 353.49/291.48 Polynomial interpretation : 353.49/291.48 353.49/291.48 POL(ACTIVATE(x_1)) = x_1 353.49/291.48 POL(c5(x_1)) = x_1 353.49/291.48 POL(c6(x_1)) = x_1 353.49/291.48 POL(n__from(x_1)) = x_1 353.49/291.48 POL(n__s(x_1)) = [1] + x_1 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (14) 353.49/291.48 Obligation: 353.49/291.48 Complexity Dependency Tuples Problem 353.49/291.48 353.49/291.48 Rules:none 353.49/291.48 Tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 S tuples:none 353.49/291.48 K tuples: 353.49/291.48 ACTIVATE(n__from(z0)) -> c5(ACTIVATE(z0)) 353.49/291.48 ACTIVATE(n__s(z0)) -> c6(ACTIVATE(z0)) 353.49/291.48 Defined Rule Symbols:none 353.49/291.48 353.49/291.48 Defined Pair Symbols: ACTIVATE_1 353.49/291.48 353.49/291.48 Compound Symbols: c5_1, c6_1 353.49/291.48 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (15) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 353.49/291.48 The set S is empty 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (16) 353.49/291.48 BOUNDS(1, 1) 353.49/291.48 353.49/291.48 ---------------------------------------- 353.49/291.48 353.49/291.48 (17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 353.49/291.48 Transformed a relative TRS into a decreasing-loop problem. 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (18) 353.52/291.48 Obligation: 353.52/291.48 Analyzing the following TRS for decreasing loops: 353.52/291.48 353.52/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.52/291.48 353.52/291.48 353.52/291.48 The TRS R consists of the following rules: 353.52/291.48 353.52/291.48 2nd(cons1(X, cons(Y, Z))) -> Y 353.52/291.48 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) 353.52/291.48 from(X) -> cons(X, n__from(n__s(X))) 353.52/291.48 from(X) -> n__from(X) 353.52/291.48 s(X) -> n__s(X) 353.52/291.48 activate(n__from(X)) -> from(activate(X)) 353.52/291.48 activate(n__s(X)) -> s(activate(X)) 353.52/291.48 activate(X) -> X 353.52/291.48 353.52/291.48 S is empty. 353.52/291.48 Rewrite Strategy: INNERMOST 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (19) DecreasingLoopProof (LOWER BOUND(ID)) 353.52/291.48 The following loop(s) give(s) rise to the lower bound Omega(n^1): 353.52/291.48 353.52/291.48 The rewrite sequence 353.52/291.48 353.52/291.48 activate(n__s(X)) ->^+ s(activate(X)) 353.52/291.48 353.52/291.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 353.52/291.48 353.52/291.48 The pumping substitution is [X / n__s(X)]. 353.52/291.48 353.52/291.48 The result substitution is [ ]. 353.52/291.48 353.52/291.48 353.52/291.48 353.52/291.48 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (20) 353.52/291.48 Complex Obligation (BEST) 353.52/291.48 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (21) 353.52/291.48 Obligation: 353.52/291.48 Proved the lower bound n^1 for the following obligation: 353.52/291.48 353.52/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.52/291.48 353.52/291.48 353.52/291.48 The TRS R consists of the following rules: 353.52/291.48 353.52/291.48 2nd(cons1(X, cons(Y, Z))) -> Y 353.52/291.48 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) 353.52/291.48 from(X) -> cons(X, n__from(n__s(X))) 353.52/291.48 from(X) -> n__from(X) 353.52/291.48 s(X) -> n__s(X) 353.52/291.48 activate(n__from(X)) -> from(activate(X)) 353.52/291.48 activate(n__s(X)) -> s(activate(X)) 353.52/291.48 activate(X) -> X 353.52/291.48 353.52/291.48 S is empty. 353.52/291.48 Rewrite Strategy: INNERMOST 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (22) LowerBoundPropagationProof (FINISHED) 353.52/291.48 Propagated lower bound. 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (23) 353.52/291.48 BOUNDS(n^1, INF) 353.52/291.48 353.52/291.48 ---------------------------------------- 353.52/291.48 353.52/291.48 (24) 353.52/291.48 Obligation: 353.52/291.48 Analyzing the following TRS for decreasing loops: 353.52/291.48 353.52/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.52/291.48 353.52/291.48 353.52/291.48 The TRS R consists of the following rules: 353.52/291.48 353.52/291.48 2nd(cons1(X, cons(Y, Z))) -> Y 353.52/291.48 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) 353.52/291.48 from(X) -> cons(X, n__from(n__s(X))) 353.52/291.48 from(X) -> n__from(X) 353.52/291.48 s(X) -> n__s(X) 353.52/291.48 activate(n__from(X)) -> from(activate(X)) 353.52/291.48 activate(n__s(X)) -> s(activate(X)) 353.52/291.48 activate(X) -> X 353.52/291.48 353.52/291.48 S is empty. 353.52/291.48 Rewrite Strategy: INNERMOST 353.54/291.53 EOF