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