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