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