399.88/291.52 WORST_CASE(Omega(n^1), O(n^3)) 399.88/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 399.88/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 399.88/291.53 399.88/291.53 399.88/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 399.88/291.53 399.88/291.53 (0) CpxTRS 399.88/291.53 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 399.88/291.53 (2) CpxTRS 399.88/291.53 (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (4) CpxTRS 399.88/291.53 (5) CpxTrsToCdtProof [UPPER BOUND(ID), 3 ms] 399.88/291.53 (6) CdtProblem 399.88/291.53 (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (8) CdtProblem 399.88/291.53 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (10) CdtProblem 399.88/291.53 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 37 ms] 399.88/291.53 (12) CdtProblem 399.88/291.53 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (14) BOUNDS(1, 1) 399.88/291.53 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (16) CpxTRS 399.88/291.53 (17) SlicingProof [LOWER BOUND(ID), 0 ms] 399.88/291.53 (18) CpxTRS 399.88/291.53 (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 399.88/291.53 (20) typed CpxTrs 399.88/291.53 (21) OrderProof [LOWER BOUND(ID), 0 ms] 399.88/291.53 (22) typed CpxTrs 399.88/291.53 (23) RewriteLemmaProof [LOWER BOUND(ID), 674 ms] 399.88/291.53 (24) proven lower bound 399.88/291.53 (25) LowerBoundPropagationProof [FINISHED, 0 ms] 399.88/291.53 (26) BOUNDS(n^1, INF) 399.88/291.53 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (0) 399.88/291.53 Obligation: 399.88/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 399.88/291.53 399.88/291.53 399.88/291.53 The TRS R consists of the following rules: 399.88/291.53 399.88/291.53 *(x, *(y, z)) -> *(otimes(x, y), z) 399.88/291.53 *(1, y) -> y 399.88/291.53 *(+(x, y), z) -> oplus(*(x, z), *(y, z)) 399.88/291.53 *(x, oplus(y, z)) -> oplus(*(x, y), *(x, z)) 399.88/291.53 399.88/291.53 S is empty. 399.88/291.53 Rewrite Strategy: FULL 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 399.88/291.53 The TRS does not nest defined symbols. 399.88/291.53 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 399.88/291.53 *(x, *(y, z)) -> *(otimes(x, y), z) 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (2) 399.88/291.53 Obligation: 399.88/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 399.88/291.53 399.88/291.53 399.88/291.53 The TRS R consists of the following rules: 399.88/291.53 399.88/291.53 *(1, y) -> y 399.88/291.53 *(+(x, y), z) -> oplus(*(x, z), *(y, z)) 399.88/291.53 *(x, oplus(y, z)) -> oplus(*(x, y), *(x, z)) 399.88/291.53 399.88/291.53 S is empty. 399.88/291.53 Rewrite Strategy: FULL 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 Converted rc-obligation to irc-obligation. 399.88/291.53 399.88/291.53 As the TRS does not nest defined symbols, we have rc = irc. 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (4) 399.88/291.53 Obligation: 399.88/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 399.88/291.53 399.88/291.53 399.88/291.53 The TRS R consists of the following rules: 399.88/291.53 399.88/291.53 *(1, y) -> y 399.88/291.53 *(+(x, y), z) -> oplus(*(x, z), *(y, z)) 399.88/291.53 *(x, oplus(y, z)) -> oplus(*(x, y), *(x, z)) 399.88/291.53 399.88/291.53 S is empty. 399.88/291.53 Rewrite Strategy: INNERMOST 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (5) CpxTrsToCdtProof (UPPER BOUND(ID)) 399.88/291.53 Converted Cpx (relative) TRS to CDT 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (6) 399.88/291.53 Obligation: 399.88/291.53 Complexity Dependency Tuples Problem 399.88/291.53 399.88/291.53 Rules: 399.88/291.53 *(1, z0) -> z0 399.88/291.53 *(+(z0, z1), z2) -> oplus(*(z0, z2), *(z1, z2)) 399.88/291.53 *(z0, oplus(z1, z2)) -> oplus(*(z0, z1), *(z0, z2)) 399.88/291.53 Tuples: 399.88/291.53 *'(1, z0) -> c 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 S tuples: 399.88/291.53 *'(1, z0) -> c 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 K tuples:none 399.88/291.53 Defined Rule Symbols: *_2 399.88/291.53 399.88/291.53 Defined Pair Symbols: *'_2 399.88/291.53 399.88/291.53 Compound Symbols: c, c1_2, c2_2 399.88/291.53 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 Removed 1 trailing nodes: 399.88/291.53 *'(1, z0) -> c 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (8) 399.88/291.53 Obligation: 399.88/291.53 Complexity Dependency Tuples Problem 399.88/291.53 399.88/291.53 Rules: 399.88/291.53 *(1, z0) -> z0 399.88/291.53 *(+(z0, z1), z2) -> oplus(*(z0, z2), *(z1, z2)) 399.88/291.53 *(z0, oplus(z1, z2)) -> oplus(*(z0, z1), *(z0, z2)) 399.88/291.53 Tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 S tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 K tuples:none 399.88/291.53 Defined Rule Symbols: *_2 399.88/291.53 399.88/291.53 Defined Pair Symbols: *'_2 399.88/291.53 399.88/291.53 Compound Symbols: c1_2, c2_2 399.88/291.53 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 The following rules are not usable and were removed: 399.88/291.53 *(1, z0) -> z0 399.88/291.53 *(+(z0, z1), z2) -> oplus(*(z0, z2), *(z1, z2)) 399.88/291.53 *(z0, oplus(z1, z2)) -> oplus(*(z0, z1), *(z0, z2)) 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (10) 399.88/291.53 Obligation: 399.88/291.53 Complexity Dependency Tuples Problem 399.88/291.53 399.88/291.53 Rules:none 399.88/291.53 Tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 S tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 K tuples:none 399.88/291.53 Defined Rule Symbols:none 399.88/291.53 399.88/291.53 Defined Pair Symbols: *'_2 399.88/291.53 399.88/291.53 Compound Symbols: c1_2, c2_2 399.88/291.53 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3))) 399.88/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 We considered the (Usable) Rules:none 399.88/291.53 And the Tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 The order we found is given by the following interpretation: 399.88/291.53 399.88/291.53 Polynomial interpretation : 399.88/291.53 399.88/291.53 POL(*'(x_1, x_2)) = [1] + x_1 + x_2 + x_2^2 + x_1^2 + x_1^2*x_2 + x_1*x_2^2 399.88/291.53 POL(+(x_1, x_2)) = [1] + x_1 + x_2 399.88/291.53 POL(c1(x_1, x_2)) = x_1 + x_2 399.88/291.53 POL(c2(x_1, x_2)) = x_1 + x_2 399.88/291.53 POL(oplus(x_1, x_2)) = [1] + x_1 + x_2 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (12) 399.88/291.53 Obligation: 399.88/291.53 Complexity Dependency Tuples Problem 399.88/291.53 399.88/291.53 Rules:none 399.88/291.53 Tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 S tuples:none 399.88/291.53 K tuples: 399.88/291.53 *'(+(z0, z1), z2) -> c1(*'(z0, z2), *'(z1, z2)) 399.88/291.53 *'(z0, oplus(z1, z2)) -> c2(*'(z0, z1), *'(z0, z2)) 399.88/291.53 Defined Rule Symbols:none 399.88/291.53 399.88/291.53 Defined Pair Symbols: *'_2 399.88/291.53 399.88/291.53 Compound Symbols: c1_2, c2_2 399.88/291.53 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 The set S is empty 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (14) 399.88/291.53 BOUNDS(1, 1) 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 Renamed function symbols to avoid clashes with predefined symbol. 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (16) 399.88/291.53 Obligation: 399.88/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 399.88/291.53 399.88/291.53 399.88/291.53 The TRS R consists of the following rules: 399.88/291.53 399.88/291.53 *'(x, *'(y, z)) -> *'(otimes(x, y), z) 399.88/291.53 *'(1', y) -> y 399.88/291.53 *'(+'(x, y), z) -> oplus(*'(x, z), *'(y, z)) 399.88/291.53 *'(x, oplus(y, z)) -> oplus(*'(x, y), *'(x, z)) 399.88/291.53 399.88/291.53 S is empty. 399.88/291.53 Rewrite Strategy: FULL 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (17) SlicingProof (LOWER BOUND(ID)) 399.88/291.53 Sliced the following arguments: 399.88/291.53 otimes/0 399.88/291.53 otimes/1 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (18) 399.88/291.53 Obligation: 399.88/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 399.88/291.53 399.88/291.53 399.88/291.53 The TRS R consists of the following rules: 399.88/291.53 399.88/291.53 *'(x, *'(y, z)) -> *'(otimes, z) 399.88/291.53 *'(1', y) -> y 399.88/291.53 *'(+'(x, y), z) -> oplus(*'(x, z), *'(y, z)) 399.88/291.53 *'(x, oplus(y, z)) -> oplus(*'(x, y), *'(x, z)) 399.88/291.53 399.88/291.53 S is empty. 399.88/291.53 Rewrite Strategy: FULL 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 399.88/291.53 Infered types. 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (20) 399.88/291.53 Obligation: 399.88/291.53 TRS: 399.88/291.53 Rules: 399.88/291.53 *'(x, *'(y, z)) -> *'(otimes, z) 399.88/291.53 *'(1', y) -> y 399.88/291.53 *'(+'(x, y), z) -> oplus(*'(x, z), *'(y, z)) 399.88/291.53 *'(x, oplus(y, z)) -> oplus(*'(x, y), *'(x, z)) 399.88/291.53 399.88/291.53 Types: 399.88/291.53 *' :: otimes:1':+' -> oplus -> oplus 399.88/291.53 otimes :: otimes:1':+' 399.88/291.53 1' :: otimes:1':+' 399.88/291.53 +' :: otimes:1':+' -> otimes:1':+' -> otimes:1':+' 399.88/291.53 oplus :: oplus -> oplus -> oplus 399.88/291.53 hole_oplus1_0 :: oplus 399.88/291.53 hole_otimes:1':+'2_0 :: otimes:1':+' 399.88/291.53 gen_oplus3_0 :: Nat -> oplus 399.88/291.53 gen_otimes:1':+'4_0 :: Nat -> otimes:1':+' 399.88/291.53 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (21) OrderProof (LOWER BOUND(ID)) 399.88/291.53 Heuristically decided to analyse the following defined symbols: 399.88/291.53 *' 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (22) 399.88/291.53 Obligation: 399.88/291.53 TRS: 399.88/291.53 Rules: 399.88/291.53 *'(x, *'(y, z)) -> *'(otimes, z) 399.88/291.53 *'(1', y) -> y 399.88/291.53 *'(+'(x, y), z) -> oplus(*'(x, z), *'(y, z)) 399.88/291.53 *'(x, oplus(y, z)) -> oplus(*'(x, y), *'(x, z)) 399.88/291.53 399.88/291.53 Types: 399.88/291.53 *' :: otimes:1':+' -> oplus -> oplus 399.88/291.53 otimes :: otimes:1':+' 399.88/291.53 1' :: otimes:1':+' 399.88/291.53 +' :: otimes:1':+' -> otimes:1':+' -> otimes:1':+' 399.88/291.53 oplus :: oplus -> oplus -> oplus 399.88/291.53 hole_oplus1_0 :: oplus 399.88/291.53 hole_otimes:1':+'2_0 :: otimes:1':+' 399.88/291.53 gen_oplus3_0 :: Nat -> oplus 399.88/291.53 gen_otimes:1':+'4_0 :: Nat -> otimes:1':+' 399.88/291.53 399.88/291.53 399.88/291.53 Generator Equations: 399.88/291.53 gen_oplus3_0(0) <=> hole_oplus1_0 399.88/291.53 gen_oplus3_0(+(x, 1)) <=> oplus(hole_oplus1_0, gen_oplus3_0(x)) 399.88/291.53 gen_otimes:1':+'4_0(0) <=> 1' 399.88/291.53 gen_otimes:1':+'4_0(+(x, 1)) <=> +'(1', gen_otimes:1':+'4_0(x)) 399.88/291.53 399.88/291.53 399.88/291.53 The following defined symbols remain to be analysed: 399.88/291.53 *' 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (23) RewriteLemmaProof (LOWER BOUND(ID)) 399.88/291.53 Proved the following rewrite lemma: 399.88/291.53 *'(gen_otimes:1':+'4_0(0), gen_oplus3_0(n6_0)) -> *5_0, rt in Omega(n6_0) 399.88/291.53 399.88/291.53 Induction Base: 399.88/291.53 *'(gen_otimes:1':+'4_0(0), gen_oplus3_0(0)) 399.88/291.53 399.88/291.53 Induction Step: 399.88/291.53 *'(gen_otimes:1':+'4_0(0), gen_oplus3_0(+(n6_0, 1))) ->_R^Omega(1) 399.88/291.53 oplus(*'(gen_otimes:1':+'4_0(0), hole_oplus1_0), *'(gen_otimes:1':+'4_0(0), gen_oplus3_0(n6_0))) ->_R^Omega(1) 399.88/291.53 oplus(hole_oplus1_0, *'(gen_otimes:1':+'4_0(0), gen_oplus3_0(n6_0))) ->_IH 399.88/291.53 oplus(hole_oplus1_0, *5_0) 399.88/291.53 399.88/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (24) 399.88/291.53 Obligation: 399.88/291.53 Proved the lower bound n^1 for the following obligation: 399.88/291.53 399.88/291.53 TRS: 399.88/291.53 Rules: 399.88/291.53 *'(x, *'(y, z)) -> *'(otimes, z) 399.88/291.53 *'(1', y) -> y 399.88/291.53 *'(+'(x, y), z) -> oplus(*'(x, z), *'(y, z)) 399.88/291.53 *'(x, oplus(y, z)) -> oplus(*'(x, y), *'(x, z)) 399.88/291.53 399.88/291.53 Types: 399.88/291.53 *' :: otimes:1':+' -> oplus -> oplus 399.88/291.53 otimes :: otimes:1':+' 399.88/291.53 1' :: otimes:1':+' 399.88/291.53 +' :: otimes:1':+' -> otimes:1':+' -> otimes:1':+' 399.88/291.53 oplus :: oplus -> oplus -> oplus 399.88/291.53 hole_oplus1_0 :: oplus 399.88/291.53 hole_otimes:1':+'2_0 :: otimes:1':+' 399.88/291.53 gen_oplus3_0 :: Nat -> oplus 399.88/291.53 gen_otimes:1':+'4_0 :: Nat -> otimes:1':+' 399.88/291.53 399.88/291.53 399.88/291.53 Generator Equations: 399.88/291.53 gen_oplus3_0(0) <=> hole_oplus1_0 399.88/291.53 gen_oplus3_0(+(x, 1)) <=> oplus(hole_oplus1_0, gen_oplus3_0(x)) 399.88/291.53 gen_otimes:1':+'4_0(0) <=> 1' 399.88/291.53 gen_otimes:1':+'4_0(+(x, 1)) <=> +'(1', gen_otimes:1':+'4_0(x)) 399.88/291.53 399.88/291.53 399.88/291.53 The following defined symbols remain to be analysed: 399.88/291.53 *' 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (25) LowerBoundPropagationProof (FINISHED) 399.88/291.53 Propagated lower bound. 399.88/291.53 ---------------------------------------- 399.88/291.53 399.88/291.53 (26) 399.88/291.53 BOUNDS(n^1, INF) 399.97/291.57 EOF