18.91/5.94 WORST_CASE(Omega(n^1), O(n^1)) 18.91/5.95 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 18.91/5.95 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.91/5.95 18.91/5.95 18.91/5.95 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.91/5.95 18.91/5.95 (0) CpxTRS 18.91/5.95 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (2) CpxTRS 18.91/5.95 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 18.91/5.95 (4) CdtProblem 18.91/5.95 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (6) CdtProblem 18.91/5.95 (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (8) CdtProblem 18.91/5.95 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (10) CdtProblem 18.91/5.95 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 39 ms] 18.91/5.95 (12) CdtProblem 18.91/5.95 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (14) BOUNDS(1, 1) 18.91/5.95 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (16) CpxTRS 18.91/5.95 (17) SlicingProof [LOWER BOUND(ID), 0 ms] 18.91/5.95 (18) CpxTRS 18.91/5.95 (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 18.91/5.95 (20) typed CpxTrs 18.91/5.95 (21) OrderProof [LOWER BOUND(ID), 0 ms] 18.91/5.95 (22) typed CpxTrs 18.91/5.95 (23) RewriteLemmaProof [LOWER BOUND(ID), 779 ms] 18.91/5.95 (24) proven lower bound 18.91/5.95 (25) LowerBoundPropagationProof [FINISHED, 0 ms] 18.91/5.95 (26) BOUNDS(n^1, INF) 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (0) 18.91/5.95 Obligation: 18.91/5.95 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.91/5.95 18.91/5.95 18.91/5.95 The TRS R consists of the following rules: 18.91/5.95 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(x)) -> +(sqr(s(x)), sum(x)) 18.91/5.95 sqr(x) -> *(x, x) 18.91/5.95 sum(s(x)) -> +(*(s(x), s(x)), sum(x)) 18.91/5.95 18.91/5.95 S is empty. 18.91/5.95 Rewrite Strategy: FULL 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 Converted rc-obligation to irc-obligation. 18.91/5.95 18.91/5.95 As the TRS does not nest defined symbols, we have rc = irc. 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (2) 18.91/5.95 Obligation: 18.91/5.95 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 18.91/5.95 18.91/5.95 18.91/5.95 The TRS R consists of the following rules: 18.91/5.95 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(x)) -> +(sqr(s(x)), sum(x)) 18.91/5.95 sqr(x) -> *(x, x) 18.91/5.95 sum(s(x)) -> +(*(s(x), s(x)), sum(x)) 18.91/5.95 18.91/5.95 S is empty. 18.91/5.95 Rewrite Strategy: INNERMOST 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 18.91/5.95 Converted Cpx (relative) TRS to CDT 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (4) 18.91/5.95 Obligation: 18.91/5.95 Complexity Dependency Tuples Problem 18.91/5.95 18.91/5.95 Rules: 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(z0)) -> +(sqr(s(z0)), sum(z0)) 18.91/5.95 sum(s(z0)) -> +(*(s(z0), s(z0)), sum(z0)) 18.91/5.95 sqr(z0) -> *(z0, z0) 18.91/5.95 Tuples: 18.91/5.95 SUM(0) -> c 18.91/5.95 SUM(s(z0)) -> c1(SQR(s(z0)), SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SQR(z0) -> c3 18.91/5.95 S tuples: 18.91/5.95 SUM(0) -> c 18.91/5.95 SUM(s(z0)) -> c1(SQR(s(z0)), SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SQR(z0) -> c3 18.91/5.95 K tuples:none 18.91/5.95 Defined Rule Symbols: sum_1, sqr_1 18.91/5.95 18.91/5.95 Defined Pair Symbols: SUM_1, SQR_1 18.91/5.95 18.91/5.95 Compound Symbols: c, c1_2, c2_1, c3 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 Removed 2 trailing nodes: 18.91/5.95 SQR(z0) -> c3 18.91/5.95 SUM(0) -> c 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (6) 18.91/5.95 Obligation: 18.91/5.95 Complexity Dependency Tuples Problem 18.91/5.95 18.91/5.95 Rules: 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(z0)) -> +(sqr(s(z0)), sum(z0)) 18.91/5.95 sum(s(z0)) -> +(*(s(z0), s(z0)), sum(z0)) 18.91/5.95 sqr(z0) -> *(z0, z0) 18.91/5.95 Tuples: 18.91/5.95 SUM(s(z0)) -> c1(SQR(s(z0)), SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 S tuples: 18.91/5.95 SUM(s(z0)) -> c1(SQR(s(z0)), SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 K tuples:none 18.91/5.95 Defined Rule Symbols: sum_1, sqr_1 18.91/5.95 18.91/5.95 Defined Pair Symbols: SUM_1 18.91/5.95 18.91/5.95 Compound Symbols: c1_2, c2_1 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 Removed 1 trailing tuple parts 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (8) 18.91/5.95 Obligation: 18.91/5.95 Complexity Dependency Tuples Problem 18.91/5.95 18.91/5.95 Rules: 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(z0)) -> +(sqr(s(z0)), sum(z0)) 18.91/5.95 sum(s(z0)) -> +(*(s(z0), s(z0)), sum(z0)) 18.91/5.95 sqr(z0) -> *(z0, z0) 18.91/5.95 Tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 S tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 K tuples:none 18.91/5.95 Defined Rule Symbols: sum_1, sqr_1 18.91/5.95 18.91/5.95 Defined Pair Symbols: SUM_1 18.91/5.95 18.91/5.95 Compound Symbols: c2_1, c1_1 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 The following rules are not usable and were removed: 18.91/5.95 sum(0) -> 0 18.91/5.95 sum(s(z0)) -> +(sqr(s(z0)), sum(z0)) 18.91/5.95 sum(s(z0)) -> +(*(s(z0), s(z0)), sum(z0)) 18.91/5.95 sqr(z0) -> *(z0, z0) 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (10) 18.91/5.95 Obligation: 18.91/5.95 Complexity Dependency Tuples Problem 18.91/5.95 18.91/5.95 Rules:none 18.91/5.95 Tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 S tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 K tuples:none 18.91/5.95 Defined Rule Symbols:none 18.91/5.95 18.91/5.95 Defined Pair Symbols: SUM_1 18.91/5.95 18.91/5.95 Compound Symbols: c2_1, c1_1 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 18.91/5.95 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 We considered the (Usable) Rules:none 18.91/5.95 And the Tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 The order we found is given by the following interpretation: 18.91/5.95 18.91/5.95 Polynomial interpretation : 18.91/5.95 18.91/5.95 POL(SUM(x_1)) = [3]x_1 18.91/5.95 POL(c1(x_1)) = x_1 18.91/5.95 POL(c2(x_1)) = x_1 18.91/5.95 POL(s(x_1)) = [3] + x_1 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (12) 18.91/5.95 Obligation: 18.91/5.95 Complexity Dependency Tuples Problem 18.91/5.95 18.91/5.95 Rules:none 18.91/5.95 Tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 S tuples:none 18.91/5.95 K tuples: 18.91/5.95 SUM(s(z0)) -> c2(SUM(z0)) 18.91/5.95 SUM(s(z0)) -> c1(SUM(z0)) 18.91/5.95 Defined Rule Symbols:none 18.91/5.95 18.91/5.95 Defined Pair Symbols: SUM_1 18.91/5.95 18.91/5.95 Compound Symbols: c2_1, c1_1 18.91/5.95 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 The set S is empty 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (14) 18.91/5.95 BOUNDS(1, 1) 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 Renamed function symbols to avoid clashes with predefined symbol. 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (16) 18.91/5.95 Obligation: 18.91/5.95 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.91/5.95 18.91/5.95 18.91/5.95 The TRS R consists of the following rules: 18.91/5.95 18.91/5.95 sum(0') -> 0' 18.91/5.95 sum(s(x)) -> +'(sqr(s(x)), sum(x)) 18.91/5.95 sqr(x) -> *'(x, x) 18.91/5.95 sum(s(x)) -> +'(*'(s(x), s(x)), sum(x)) 18.91/5.95 18.91/5.95 S is empty. 18.91/5.95 Rewrite Strategy: FULL 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (17) SlicingProof (LOWER BOUND(ID)) 18.91/5.95 Sliced the following arguments: 18.91/5.95 sqr/0 18.91/5.95 *'/0 18.91/5.95 *'/1 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (18) 18.91/5.95 Obligation: 18.91/5.95 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.91/5.95 18.91/5.95 18.91/5.95 The TRS R consists of the following rules: 18.91/5.95 18.91/5.95 sum(0') -> 0' 18.91/5.95 sum(s(x)) -> +'(sqr, sum(x)) 18.91/5.95 sqr -> *' 18.91/5.95 sum(s(x)) -> +'(*', sum(x)) 18.91/5.95 18.91/5.95 S is empty. 18.91/5.95 Rewrite Strategy: FULL 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 18.91/5.95 Infered types. 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (20) 18.91/5.95 Obligation: 18.91/5.95 TRS: 18.91/5.95 Rules: 18.91/5.95 sum(0') -> 0' 18.91/5.95 sum(s(x)) -> +'(sqr, sum(x)) 18.91/5.95 sqr -> *' 18.91/5.95 sum(s(x)) -> +'(*', sum(x)) 18.91/5.95 18.91/5.95 Types: 18.91/5.95 sum :: 0':s:+' -> 0':s:+' 18.91/5.95 0' :: 0':s:+' 18.91/5.95 s :: 0':s:+' -> 0':s:+' 18.91/5.95 +' :: *' -> 0':s:+' -> 0':s:+' 18.91/5.95 sqr :: *' 18.91/5.95 *' :: *' 18.91/5.95 hole_0':s:+'1_0 :: 0':s:+' 18.91/5.95 hole_*'2_0 :: *' 18.91/5.95 gen_0':s:+'3_0 :: Nat -> 0':s:+' 18.91/5.95 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (21) OrderProof (LOWER BOUND(ID)) 18.91/5.95 Heuristically decided to analyse the following defined symbols: 18.91/5.95 sum 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (22) 18.91/5.95 Obligation: 18.91/5.95 TRS: 18.91/5.95 Rules: 18.91/5.95 sum(0') -> 0' 18.91/5.95 sum(s(x)) -> +'(sqr, sum(x)) 18.91/5.95 sqr -> *' 18.91/5.95 sum(s(x)) -> +'(*', sum(x)) 18.91/5.95 18.91/5.95 Types: 18.91/5.95 sum :: 0':s:+' -> 0':s:+' 18.91/5.95 0' :: 0':s:+' 18.91/5.95 s :: 0':s:+' -> 0':s:+' 18.91/5.95 +' :: *' -> 0':s:+' -> 0':s:+' 18.91/5.95 sqr :: *' 18.91/5.95 *' :: *' 18.91/5.95 hole_0':s:+'1_0 :: 0':s:+' 18.91/5.95 hole_*'2_0 :: *' 18.91/5.95 gen_0':s:+'3_0 :: Nat -> 0':s:+' 18.91/5.95 18.91/5.95 18.91/5.95 Generator Equations: 18.91/5.95 gen_0':s:+'3_0(0) <=> 0' 18.91/5.95 gen_0':s:+'3_0(+(x, 1)) <=> s(gen_0':s:+'3_0(x)) 18.91/5.95 18.91/5.95 18.91/5.95 The following defined symbols remain to be analysed: 18.91/5.95 sum 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (23) RewriteLemmaProof (LOWER BOUND(ID)) 18.91/5.95 Proved the following rewrite lemma: 18.91/5.95 sum(gen_0':s:+'3_0(n5_0)) -> *4_0, rt in Omega(n5_0) 18.91/5.95 18.91/5.95 Induction Base: 18.91/5.95 sum(gen_0':s:+'3_0(0)) 18.91/5.95 18.91/5.95 Induction Step: 18.91/5.95 sum(gen_0':s:+'3_0(+(n5_0, 1))) ->_R^Omega(1) 18.91/5.95 +'(*', sum(gen_0':s:+'3_0(n5_0))) ->_IH 18.91/5.95 +'(*', *4_0) 18.91/5.95 18.91/5.95 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (24) 18.91/5.95 Obligation: 18.91/5.95 Proved the lower bound n^1 for the following obligation: 18.91/5.95 18.91/5.95 TRS: 18.91/5.95 Rules: 18.91/5.95 sum(0') -> 0' 18.91/5.95 sum(s(x)) -> +'(sqr, sum(x)) 18.91/5.95 sqr -> *' 18.91/5.95 sum(s(x)) -> +'(*', sum(x)) 18.91/5.95 18.91/5.95 Types: 18.91/5.95 sum :: 0':s:+' -> 0':s:+' 18.91/5.95 0' :: 0':s:+' 18.91/5.95 s :: 0':s:+' -> 0':s:+' 18.91/5.95 +' :: *' -> 0':s:+' -> 0':s:+' 18.91/5.95 sqr :: *' 18.91/5.95 *' :: *' 18.91/5.95 hole_0':s:+'1_0 :: 0':s:+' 18.91/5.95 hole_*'2_0 :: *' 18.91/5.95 gen_0':s:+'3_0 :: Nat -> 0':s:+' 18.91/5.95 18.91/5.95 18.91/5.95 Generator Equations: 18.91/5.95 gen_0':s:+'3_0(0) <=> 0' 18.91/5.95 gen_0':s:+'3_0(+(x, 1)) <=> s(gen_0':s:+'3_0(x)) 18.91/5.95 18.91/5.95 18.91/5.95 The following defined symbols remain to be analysed: 18.91/5.95 sum 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (25) LowerBoundPropagationProof (FINISHED) 18.91/5.95 Propagated lower bound. 18.91/5.95 ---------------------------------------- 18.91/5.95 18.91/5.95 (26) 18.91/5.95 BOUNDS(n^1, INF) 19.29/6.16 EOF