21.49/7.39 WORST_CASE(Omega(n^1), O(n^1)) 21.49/7.39 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 21.49/7.39 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.49/7.39 21.49/7.39 21.49/7.39 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.49/7.39 21.49/7.39 (0) CpxTRS 21.49/7.39 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 21.49/7.39 (2) CpxTRS 21.49/7.39 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 21.49/7.39 (4) CpxTRS 21.49/7.39 (5) CpxTrsMatchBoundsTAProof [FINISHED, 135 ms] 21.49/7.39 (6) BOUNDS(1, n^1) 21.49/7.39 (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 21.49/7.39 (8) CpxTRS 21.49/7.39 (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 21.49/7.39 (10) typed CpxTrs 21.49/7.39 (11) OrderProof [LOWER BOUND(ID), 0 ms] 21.49/7.39 (12) typed CpxTrs 21.49/7.39 (13) RewriteLemmaProof [LOWER BOUND(ID), 512 ms] 21.49/7.39 (14) BEST 21.49/7.39 (15) proven lower bound 21.49/7.39 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 21.49/7.39 (17) BOUNDS(n^1, INF) 21.49/7.39 (18) typed CpxTrs 21.49/7.39 21.49/7.39 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (0) 21.49/7.39 Obligation: 21.49/7.39 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.49/7.39 21.49/7.39 21.49/7.39 The TRS R consists of the following rules: 21.49/7.39 21.49/7.39 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.39 active(b) -> mark(a) 21.49/7.39 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.39 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.39 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.39 proper(a) -> ok(a) 21.49/7.39 proper(b) -> ok(b) 21.49/7.39 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.39 top(mark(X)) -> top(proper(X)) 21.49/7.39 top(ok(X)) -> top(active(X)) 21.49/7.39 21.49/7.39 S is empty. 21.49/7.39 Rewrite Strategy: FULL 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 21.49/7.39 The following defined symbols can occur below the 0th argument of top: proper, active 21.49/7.39 The following defined symbols can occur below the 0th argument of proper: proper, active 21.49/7.39 The following defined symbols can occur below the 0th argument of active: proper, active 21.49/7.39 21.49/7.39 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 21.49/7.39 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.39 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.39 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.39 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (2) 21.49/7.39 Obligation: 21.49/7.39 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 21.49/7.39 21.49/7.39 21.49/7.39 The TRS R consists of the following rules: 21.49/7.39 21.49/7.39 active(b) -> mark(a) 21.49/7.39 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.39 proper(a) -> ok(a) 21.49/7.39 proper(b) -> ok(b) 21.49/7.39 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.39 top(mark(X)) -> top(proper(X)) 21.49/7.39 top(ok(X)) -> top(active(X)) 21.49/7.39 21.49/7.39 S is empty. 21.49/7.39 Rewrite Strategy: FULL 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 21.49/7.39 transformed relative TRS to TRS 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (4) 21.49/7.39 Obligation: 21.49/7.39 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 21.49/7.39 21.49/7.39 21.49/7.39 The TRS R consists of the following rules: 21.49/7.39 21.49/7.39 active(b) -> mark(a) 21.49/7.39 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.39 proper(a) -> ok(a) 21.49/7.39 proper(b) -> ok(b) 21.49/7.39 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.39 top(mark(X)) -> top(proper(X)) 21.49/7.39 top(ok(X)) -> top(active(X)) 21.49/7.39 21.49/7.39 S is empty. 21.49/7.39 Rewrite Strategy: FULL 21.49/7.39 ---------------------------------------- 21.49/7.39 21.49/7.39 (5) CpxTrsMatchBoundsTAProof (FINISHED) 21.49/7.39 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 4. 21.49/7.39 21.49/7.39 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 21.49/7.39 final states : [1, 2, 3, 4] 21.49/7.39 transitions: 21.49/7.39 b0() -> 0 21.49/7.39 mark0(0) -> 0 21.49/7.39 a0() -> 0 21.49/7.39 ok0(0) -> 0 21.49/7.39 active0(0) -> 1 21.49/7.39 f0(0, 0, 0) -> 2 21.49/7.39 proper0(0) -> 3 21.49/7.39 top0(0) -> 4 21.49/7.39 a1() -> 5 21.49/7.39 mark1(5) -> 1 21.49/7.39 f1(0, 0, 0) -> 6 21.49/7.39 mark1(6) -> 2 21.49/7.39 a1() -> 7 21.49/7.39 ok1(7) -> 3 21.49/7.39 b1() -> 8 21.49/7.39 ok1(8) -> 3 21.49/7.39 f1(0, 0, 0) -> 9 21.49/7.39 ok1(9) -> 2 21.49/7.39 proper1(0) -> 10 21.49/7.39 top1(10) -> 4 21.49/7.39 active1(0) -> 11 21.49/7.39 top1(11) -> 4 21.49/7.39 mark1(5) -> 11 21.49/7.39 mark1(6) -> 6 21.49/7.39 mark1(6) -> 9 21.49/7.39 ok1(7) -> 10 21.49/7.39 ok1(8) -> 10 21.49/7.39 ok1(9) -> 6 21.49/7.39 ok1(9) -> 9 21.49/7.39 proper2(5) -> 12 21.49/7.39 top2(12) -> 4 21.49/7.39 active2(7) -> 13 21.49/7.39 top2(13) -> 4 21.49/7.39 active2(8) -> 13 21.49/7.39 a2() -> 14 21.49/7.39 mark2(14) -> 13 21.49/7.39 a2() -> 15 21.49/7.39 ok2(15) -> 12 21.49/7.39 proper3(14) -> 16 21.49/7.39 top3(16) -> 4 21.49/7.40 active3(15) -> 17 21.49/7.40 top3(17) -> 4 21.49/7.40 a3() -> 18 21.49/7.40 ok3(18) -> 16 21.49/7.40 active4(18) -> 19 21.49/7.40 top4(19) -> 4 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (6) 21.49/7.40 BOUNDS(1, n^1) 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (7) RenamingProof (BOTH BOUNDS(ID, ID)) 21.49/7.40 Renamed function symbols to avoid clashes with predefined symbol. 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (8) 21.49/7.40 Obligation: 21.49/7.40 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 21.49/7.40 21.49/7.40 21.49/7.40 The TRS R consists of the following rules: 21.49/7.40 21.49/7.40 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.40 active(b) -> mark(a) 21.49/7.40 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.40 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.40 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.40 proper(a) -> ok(a) 21.49/7.40 proper(b) -> ok(b) 21.49/7.40 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.40 top(mark(X)) -> top(proper(X)) 21.49/7.40 top(ok(X)) -> top(active(X)) 21.49/7.40 21.49/7.40 S is empty. 21.49/7.40 Rewrite Strategy: FULL 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 21.49/7.40 Infered types. 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (10) 21.49/7.40 Obligation: 21.49/7.40 TRS: 21.49/7.40 Rules: 21.49/7.40 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.40 active(b) -> mark(a) 21.49/7.40 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.40 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.40 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.40 proper(a) -> ok(a) 21.49/7.40 proper(b) -> ok(b) 21.49/7.40 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.40 top(mark(X)) -> top(proper(X)) 21.49/7.40 top(ok(X)) -> top(active(X)) 21.49/7.40 21.49/7.40 Types: 21.49/7.40 active :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 f :: a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok 21.49/7.40 a :: a:b:mark:ok 21.49/7.40 mark :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 b :: a:b:mark:ok 21.49/7.40 proper :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 ok :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 top :: a:b:mark:ok -> top 21.49/7.40 hole_a:b:mark:ok1_0 :: a:b:mark:ok 21.49/7.40 hole_top2_0 :: top 21.49/7.40 gen_a:b:mark:ok3_0 :: Nat -> a:b:mark:ok 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (11) OrderProof (LOWER BOUND(ID)) 21.49/7.40 Heuristically decided to analyse the following defined symbols: 21.49/7.40 active, f, proper, top 21.49/7.40 21.49/7.40 They will be analysed ascendingly in the following order: 21.49/7.40 f < active 21.49/7.40 active < top 21.49/7.40 f < proper 21.49/7.40 proper < top 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (12) 21.49/7.40 Obligation: 21.49/7.40 TRS: 21.49/7.40 Rules: 21.49/7.40 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.40 active(b) -> mark(a) 21.49/7.40 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.40 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.40 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.40 proper(a) -> ok(a) 21.49/7.40 proper(b) -> ok(b) 21.49/7.40 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.40 top(mark(X)) -> top(proper(X)) 21.49/7.40 top(ok(X)) -> top(active(X)) 21.49/7.40 21.49/7.40 Types: 21.49/7.40 active :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 f :: a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok 21.49/7.40 a :: a:b:mark:ok 21.49/7.40 mark :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 b :: a:b:mark:ok 21.49/7.40 proper :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 ok :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 top :: a:b:mark:ok -> top 21.49/7.40 hole_a:b:mark:ok1_0 :: a:b:mark:ok 21.49/7.40 hole_top2_0 :: top 21.49/7.40 gen_a:b:mark:ok3_0 :: Nat -> a:b:mark:ok 21.49/7.40 21.49/7.40 21.49/7.40 Generator Equations: 21.49/7.40 gen_a:b:mark:ok3_0(0) <=> a 21.49/7.40 gen_a:b:mark:ok3_0(+(x, 1)) <=> mark(gen_a:b:mark:ok3_0(x)) 21.49/7.40 21.49/7.40 21.49/7.40 The following defined symbols remain to be analysed: 21.49/7.40 f, active, proper, top 21.49/7.40 21.49/7.40 They will be analysed ascendingly in the following order: 21.49/7.40 f < active 21.49/7.40 active < top 21.49/7.40 f < proper 21.49/7.40 proper < top 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (13) RewriteLemmaProof (LOWER BOUND(ID)) 21.49/7.40 Proved the following rewrite lemma: 21.49/7.40 f(gen_a:b:mark:ok3_0(a), gen_a:b:mark:ok3_0(+(1, n5_0)), gen_a:b:mark:ok3_0(c)) -> *4_0, rt in Omega(n5_0) 21.49/7.40 21.49/7.40 Induction Base: 21.49/7.40 f(gen_a:b:mark:ok3_0(a), gen_a:b:mark:ok3_0(+(1, 0)), gen_a:b:mark:ok3_0(c)) 21.49/7.40 21.49/7.40 Induction Step: 21.49/7.40 f(gen_a:b:mark:ok3_0(a), gen_a:b:mark:ok3_0(+(1, +(n5_0, 1))), gen_a:b:mark:ok3_0(c)) ->_R^Omega(1) 21.49/7.40 mark(f(gen_a:b:mark:ok3_0(a), gen_a:b:mark:ok3_0(+(1, n5_0)), gen_a:b:mark:ok3_0(c))) ->_IH 21.49/7.40 mark(*4_0) 21.49/7.40 21.49/7.40 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (14) 21.49/7.40 Complex Obligation (BEST) 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (15) 21.49/7.40 Obligation: 21.49/7.40 Proved the lower bound n^1 for the following obligation: 21.49/7.40 21.49/7.40 TRS: 21.49/7.40 Rules: 21.49/7.40 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.40 active(b) -> mark(a) 21.49/7.40 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.40 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.40 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.40 proper(a) -> ok(a) 21.49/7.40 proper(b) -> ok(b) 21.49/7.40 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.40 top(mark(X)) -> top(proper(X)) 21.49/7.40 top(ok(X)) -> top(active(X)) 21.49/7.40 21.49/7.40 Types: 21.49/7.40 active :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 f :: a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok 21.49/7.40 a :: a:b:mark:ok 21.49/7.40 mark :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 b :: a:b:mark:ok 21.49/7.40 proper :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 ok :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 top :: a:b:mark:ok -> top 21.49/7.40 hole_a:b:mark:ok1_0 :: a:b:mark:ok 21.49/7.40 hole_top2_0 :: top 21.49/7.40 gen_a:b:mark:ok3_0 :: Nat -> a:b:mark:ok 21.49/7.40 21.49/7.40 21.49/7.40 Generator Equations: 21.49/7.40 gen_a:b:mark:ok3_0(0) <=> a 21.49/7.40 gen_a:b:mark:ok3_0(+(x, 1)) <=> mark(gen_a:b:mark:ok3_0(x)) 21.49/7.40 21.49/7.40 21.49/7.40 The following defined symbols remain to be analysed: 21.49/7.40 f, active, proper, top 21.49/7.40 21.49/7.40 They will be analysed ascendingly in the following order: 21.49/7.40 f < active 21.49/7.40 active < top 21.49/7.40 f < proper 21.49/7.40 proper < top 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (16) LowerBoundPropagationProof (FINISHED) 21.49/7.40 Propagated lower bound. 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (17) 21.49/7.40 BOUNDS(n^1, INF) 21.49/7.40 21.49/7.40 ---------------------------------------- 21.49/7.40 21.49/7.40 (18) 21.49/7.40 Obligation: 21.49/7.40 TRS: 21.49/7.40 Rules: 21.49/7.40 active(f(a, X, X)) -> mark(f(X, b, b)) 21.49/7.40 active(b) -> mark(a) 21.49/7.40 active(f(X1, X2, X3)) -> f(X1, active(X2), X3) 21.49/7.40 f(X1, mark(X2), X3) -> mark(f(X1, X2, X3)) 21.49/7.40 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 21.49/7.40 proper(a) -> ok(a) 21.49/7.40 proper(b) -> ok(b) 21.49/7.40 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 21.49/7.40 top(mark(X)) -> top(proper(X)) 21.49/7.40 top(ok(X)) -> top(active(X)) 21.49/7.40 21.49/7.40 Types: 21.49/7.40 active :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 f :: a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok -> a:b:mark:ok 21.49/7.40 a :: a:b:mark:ok 21.49/7.40 mark :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 b :: a:b:mark:ok 21.49/7.40 proper :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 ok :: a:b:mark:ok -> a:b:mark:ok 21.49/7.40 top :: a:b:mark:ok -> top 21.49/7.40 hole_a:b:mark:ok1_0 :: a:b:mark:ok 21.49/7.40 hole_top2_0 :: top 21.49/7.40 gen_a:b:mark:ok3_0 :: Nat -> a:b:mark:ok 21.49/7.40 21.49/7.40 21.49/7.40 Lemmas: 21.49/7.40 f(gen_a:b:mark:ok3_0(a), gen_a:b:mark:ok3_0(+(1, n5_0)), gen_a:b:mark:ok3_0(c)) -> *4_0, rt in Omega(n5_0) 21.49/7.40 21.49/7.40 21.49/7.40 Generator Equations: 21.49/7.40 gen_a:b:mark:ok3_0(0) <=> a 21.49/7.40 gen_a:b:mark:ok3_0(+(x, 1)) <=> mark(gen_a:b:mark:ok3_0(x)) 21.49/7.40 21.49/7.40 21.49/7.40 The following defined symbols remain to be analysed: 21.49/7.40 active, proper, top 21.49/7.40 21.49/7.40 They will be analysed ascendingly in the following order: 21.49/7.40 active < top 21.49/7.40 proper < top 21.77/7.44 EOF