8.43/2.96 WORST_CASE(Omega(n^1), O(n^1)) 8.43/2.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.43/2.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.43/2.97 8.43/2.97 8.43/2.97 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.43/2.97 8.43/2.97 (0) CpxTRS 8.43/2.97 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 8.43/2.97 (2) CpxTRS 8.43/2.97 (3) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 8.43/2.97 (4) BOUNDS(1, n^1) 8.43/2.97 (5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 8.43/2.97 (6) CpxTRS 8.43/2.97 (7) SlicingProof [LOWER BOUND(ID), 0 ms] 8.43/2.97 (8) CpxTRS 8.43/2.97 (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 8.43/2.97 (10) typed CpxTrs 8.43/2.97 (11) OrderProof [LOWER BOUND(ID), 0 ms] 8.43/2.97 (12) typed CpxTrs 8.43/2.97 (13) RewriteLemmaProof [LOWER BOUND(ID), 605 ms] 8.43/2.97 (14) proven lower bound 8.43/2.97 (15) LowerBoundPropagationProof [FINISHED, 0 ms] 8.43/2.97 (16) BOUNDS(n^1, INF) 8.43/2.97 8.43/2.97 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (0) 8.43/2.97 Obligation: 8.43/2.97 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.43/2.97 8.43/2.97 8.43/2.97 The TRS R consists of the following rules: 8.43/2.97 8.43/2.97 a__f(f(X)) -> a__c(f(g(f(X)))) 8.43/2.97 a__c(X) -> d(X) 8.43/2.97 a__h(X) -> a__c(d(X)) 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c(X)) -> a__c(X) 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g(X)) -> g(X) 8.43/2.97 mark(d(X)) -> d(X) 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c(X) -> c(X) 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 S is empty. 8.43/2.97 Rewrite Strategy: FULL 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 8.43/2.97 transformed relative TRS to TRS 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (2) 8.43/2.97 Obligation: 8.43/2.97 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 8.43/2.97 8.43/2.97 8.43/2.97 The TRS R consists of the following rules: 8.43/2.97 8.43/2.97 a__f(f(X)) -> a__c(f(g(f(X)))) 8.43/2.97 a__c(X) -> d(X) 8.43/2.97 a__h(X) -> a__c(d(X)) 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c(X)) -> a__c(X) 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g(X)) -> g(X) 8.43/2.97 mark(d(X)) -> d(X) 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c(X) -> c(X) 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 S is empty. 8.43/2.97 Rewrite Strategy: FULL 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (3) CpxTrsMatchBoundsProof (FINISHED) 8.43/2.97 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3. 8.43/2.97 The certificate found is represented by the following graph. 8.43/2.97 8.43/2.97 "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 8.43/2.97 {(1,2,[a__f_1|0, a__c_1|0, a__h_1|0, mark_1|0, f_1|1, d_1|1, c_1|1, h_1|1, a__c_1|1, g_1|1, d_1|2, c_1|2]), (1,3,[a__c_1|1, d_1|2, c_1|2]), (1,6,[a__c_1|1, d_1|2, c_1|2]), (1,7,[a__f_1|1, f_1|2]), (1,8,[a__h_1|1, h_1|2]), (1,9,[a__c_1|2, d_1|3, c_1|3]), (1,10,[a__c_1|2, d_1|3, c_1|3]), (2,2,[f_1|0, g_1|0, d_1|0, c_1|0, h_1|0]), (3,4,[f_1|1]), (4,5,[g_1|1]), (5,2,[f_1|1]), (6,2,[d_1|1]), (7,2,[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]), (7,7,[a__f_1|1, f_1|2]), (7,8,[a__h_1|1, h_1|2]), (7,9,[a__c_1|2, d_1|3, c_1|3]), (7,10,[a__c_1|2, d_1|3, c_1|3]), (8,2,[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]), (8,7,[a__f_1|1, f_1|2]), (8,8,[a__h_1|1, h_1|2]), (8,9,[a__c_1|2, d_1|3, c_1|3]), (8,10,[a__c_1|2, d_1|3, c_1|3]), (9,8,[d_1|2]), (10,11,[f_1|2]), (11,12,[g_1|2]), (12,7,[f_1|2])}" 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (4) 8.43/2.97 BOUNDS(1, n^1) 8.43/2.97 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (5) RenamingProof (BOTH BOUNDS(ID, ID)) 8.43/2.97 Renamed function symbols to avoid clashes with predefined symbol. 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (6) 8.43/2.97 Obligation: 8.43/2.97 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 8.43/2.97 8.43/2.97 8.43/2.97 The TRS R consists of the following rules: 8.43/2.97 8.43/2.97 a__f(f(X)) -> a__c(f(g(f(X)))) 8.43/2.97 a__c(X) -> d(X) 8.43/2.97 a__h(X) -> a__c(d(X)) 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c(X)) -> a__c(X) 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g(X)) -> g(X) 8.43/2.97 mark(d(X)) -> d(X) 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c(X) -> c(X) 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 S is empty. 8.43/2.97 Rewrite Strategy: FULL 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (7) SlicingProof (LOWER BOUND(ID)) 8.43/2.97 Sliced the following arguments: 8.43/2.97 a__c/0 8.43/2.97 g/0 8.43/2.97 d/0 8.43/2.97 c/0 8.43/2.97 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (8) 8.43/2.97 Obligation: 8.43/2.97 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 8.43/2.97 8.43/2.97 8.43/2.97 The TRS R consists of the following rules: 8.43/2.97 8.43/2.97 a__f(f(X)) -> a__c 8.43/2.97 a__c -> d 8.43/2.97 a__h(X) -> a__c 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c) -> a__c 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g) -> g 8.43/2.97 mark(d) -> d 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c -> c 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 S is empty. 8.43/2.97 Rewrite Strategy: FULL 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 8.43/2.97 Infered types. 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (10) 8.43/2.97 Obligation: 8.43/2.97 TRS: 8.43/2.97 Rules: 8.43/2.97 a__f(f(X)) -> a__c 8.43/2.97 a__c -> d 8.43/2.97 a__h(X) -> a__c 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c) -> a__c 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g) -> g 8.43/2.97 mark(d) -> d 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c -> c 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 Types: 8.43/2.97 a__f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 a__c :: f:d:c:h:g 8.43/2.97 d :: f:d:c:h:g 8.43/2.97 a__h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 mark :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 c :: f:d:c:h:g 8.43/2.97 h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 g :: f:d:c:h:g 8.43/2.97 hole_f:d:c:h:g1_0 :: f:d:c:h:g 8.43/2.97 gen_f:d:c:h:g2_0 :: Nat -> f:d:c:h:g 8.43/2.97 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (11) OrderProof (LOWER BOUND(ID)) 8.43/2.97 Heuristically decided to analyse the following defined symbols: 8.43/2.97 mark 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (12) 8.43/2.97 Obligation: 8.43/2.97 TRS: 8.43/2.97 Rules: 8.43/2.97 a__f(f(X)) -> a__c 8.43/2.97 a__c -> d 8.43/2.97 a__h(X) -> a__c 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c) -> a__c 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g) -> g 8.43/2.97 mark(d) -> d 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c -> c 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 Types: 8.43/2.97 a__f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 a__c :: f:d:c:h:g 8.43/2.97 d :: f:d:c:h:g 8.43/2.97 a__h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 mark :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 c :: f:d:c:h:g 8.43/2.97 h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 g :: f:d:c:h:g 8.43/2.97 hole_f:d:c:h:g1_0 :: f:d:c:h:g 8.43/2.97 gen_f:d:c:h:g2_0 :: Nat -> f:d:c:h:g 8.43/2.97 8.43/2.97 8.43/2.97 Generator Equations: 8.43/2.97 gen_f:d:c:h:g2_0(0) <=> d 8.43/2.97 gen_f:d:c:h:g2_0(+(x, 1)) <=> f(gen_f:d:c:h:g2_0(x)) 8.43/2.97 8.43/2.97 8.43/2.97 The following defined symbols remain to be analysed: 8.43/2.97 mark 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (13) RewriteLemmaProof (LOWER BOUND(ID)) 8.43/2.97 Proved the following rewrite lemma: 8.43/2.97 mark(gen_f:d:c:h:g2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) 8.43/2.97 8.43/2.97 Induction Base: 8.43/2.97 mark(gen_f:d:c:h:g2_0(+(1, 0))) 8.43/2.97 8.43/2.97 Induction Step: 8.43/2.97 mark(gen_f:d:c:h:g2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1) 8.43/2.97 a__f(mark(gen_f:d:c:h:g2_0(+(1, n4_0)))) ->_IH 8.43/2.97 a__f(*3_0) 8.43/2.97 8.43/2.97 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (14) 8.43/2.97 Obligation: 8.43/2.97 Proved the lower bound n^1 for the following obligation: 8.43/2.97 8.43/2.97 TRS: 8.43/2.97 Rules: 8.43/2.97 a__f(f(X)) -> a__c 8.43/2.97 a__c -> d 8.43/2.97 a__h(X) -> a__c 8.43/2.97 mark(f(X)) -> a__f(mark(X)) 8.43/2.97 mark(c) -> a__c 8.43/2.97 mark(h(X)) -> a__h(mark(X)) 8.43/2.97 mark(g) -> g 8.43/2.97 mark(d) -> d 8.43/2.97 a__f(X) -> f(X) 8.43/2.97 a__c -> c 8.43/2.97 a__h(X) -> h(X) 8.43/2.97 8.43/2.97 Types: 8.43/2.97 a__f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 f :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 a__c :: f:d:c:h:g 8.43/2.97 d :: f:d:c:h:g 8.43/2.97 a__h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 mark :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 c :: f:d:c:h:g 8.43/2.97 h :: f:d:c:h:g -> f:d:c:h:g 8.43/2.97 g :: f:d:c:h:g 8.43/2.97 hole_f:d:c:h:g1_0 :: f:d:c:h:g 8.43/2.97 gen_f:d:c:h:g2_0 :: Nat -> f:d:c:h:g 8.43/2.97 8.43/2.97 8.43/2.97 Generator Equations: 8.43/2.97 gen_f:d:c:h:g2_0(0) <=> d 8.43/2.97 gen_f:d:c:h:g2_0(+(x, 1)) <=> f(gen_f:d:c:h:g2_0(x)) 8.43/2.97 8.43/2.97 8.43/2.97 The following defined symbols remain to be analysed: 8.43/2.97 mark 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (15) LowerBoundPropagationProof (FINISHED) 8.43/2.97 Propagated lower bound. 8.43/2.97 ---------------------------------------- 8.43/2.97 8.43/2.97 (16) 8.43/2.97 BOUNDS(n^1, INF) 8.67/3.04 EOF