5.55/2.15 WORST_CASE(Omega(n^1), O(n^1)) 5.55/2.16 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.55/2.16 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.55/2.16 5.55/2.16 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 5.55/2.16 5.55/2.16 (0) CpxTRS 5.55/2.16 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 5.55/2.16 (2) CpxTRS 5.55/2.16 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 5.55/2.16 (4) CpxTRS 5.55/2.16 (5) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms] 5.55/2.16 (6) BOUNDS(1, n^1) 5.55/2.16 (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 5.55/2.16 (8) CpxTRS 5.55/2.16 (9) SlicingProof [LOWER BOUND(ID), 0 ms] 5.55/2.16 (10) CpxTRS 5.55/2.16 (11) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 5.55/2.16 (12) typed CpxTrs 5.55/2.16 (13) OrderProof [LOWER BOUND(ID), 0 ms] 5.55/2.16 (14) typed CpxTrs 5.55/2.16 (15) RewriteLemmaProof [LOWER BOUND(ID), 283 ms] 5.55/2.16 (16) proven lower bound 5.55/2.16 (17) LowerBoundPropagationProof [FINISHED, 0 ms] 5.55/2.16 (18) BOUNDS(n^1, INF) 5.55/2.16 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (0) 5.55/2.16 Obligation: 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 5.55/2.16 5.55/2.16 5.55/2.16 The TRS R consists of the following rules: 5.55/2.16 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(x, y), z) -> .(x, ++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 S is empty. 5.55/2.16 Rewrite Strategy: FULL 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 5.55/2.16 The TRS does not nest defined symbols. 5.55/2.16 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (2) 5.55/2.16 Obligation: 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 5.55/2.16 5.55/2.16 5.55/2.16 The TRS R consists of the following rules: 5.55/2.16 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(x, y), z) -> .(x, ++(y, z)) 5.55/2.16 5.55/2.16 S is empty. 5.55/2.16 Rewrite Strategy: FULL 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 5.55/2.16 transformed relative TRS to TRS 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (4) 5.55/2.16 Obligation: 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 5.55/2.16 5.55/2.16 5.55/2.16 The TRS R consists of the following rules: 5.55/2.16 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(x, y), z) -> .(x, ++(y, z)) 5.55/2.16 5.55/2.16 S is empty. 5.55/2.16 Rewrite Strategy: FULL 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (5) CpxTrsMatchBoundsTAProof (FINISHED) 5.55/2.16 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 1. 5.55/2.16 5.55/2.16 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 5.55/2.16 final states : [1] 5.55/2.16 transitions: 5.55/2.16 nil0() -> 0 5.55/2.16 .0(0, 0) -> 0 5.55/2.16 ++0(0, 0) -> 1 5.55/2.16 ++1(0, 0) -> 2 5.55/2.16 .1(0, 2) -> 1 5.55/2.16 .1(0, 2) -> 2 5.55/2.16 0 -> 1 5.55/2.16 0 -> 2 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (6) 5.55/2.16 BOUNDS(1, n^1) 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (7) RenamingProof (BOTH BOUNDS(ID, ID)) 5.55/2.16 Renamed function symbols to avoid clashes with predefined symbol. 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (8) 5.55/2.16 Obligation: 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 5.55/2.16 5.55/2.16 5.55/2.16 The TRS R consists of the following rules: 5.55/2.16 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(x, y), z) -> .(x, ++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 S is empty. 5.55/2.16 Rewrite Strategy: FULL 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (9) SlicingProof (LOWER BOUND(ID)) 5.55/2.16 Sliced the following arguments: 5.55/2.16 ./0 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (10) 5.55/2.16 Obligation: 5.55/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 5.55/2.16 5.55/2.16 5.55/2.16 The TRS R consists of the following rules: 5.55/2.16 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(y), z) -> .(++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 S is empty. 5.55/2.16 Rewrite Strategy: FULL 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (11) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 5.55/2.16 Infered types. 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (12) 5.55/2.16 Obligation: 5.55/2.16 TRS: 5.55/2.16 Rules: 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(y), z) -> .(++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 Types: 5.55/2.16 ++ :: nil:. -> nil:. -> nil:. 5.55/2.16 nil :: nil:. 5.55/2.16 . :: nil:. -> nil:. 5.55/2.16 hole_nil:.1_0 :: nil:. 5.55/2.16 gen_nil:.2_0 :: Nat -> nil:. 5.55/2.16 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (13) OrderProof (LOWER BOUND(ID)) 5.55/2.16 Heuristically decided to analyse the following defined symbols: 5.55/2.16 ++ 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (14) 5.55/2.16 Obligation: 5.55/2.16 TRS: 5.55/2.16 Rules: 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(y), z) -> .(++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 Types: 5.55/2.16 ++ :: nil:. -> nil:. -> nil:. 5.55/2.16 nil :: nil:. 5.55/2.16 . :: nil:. -> nil:. 5.55/2.16 hole_nil:.1_0 :: nil:. 5.55/2.16 gen_nil:.2_0 :: Nat -> nil:. 5.55/2.16 5.55/2.16 5.55/2.16 Generator Equations: 5.55/2.16 gen_nil:.2_0(0) <=> nil 5.55/2.16 gen_nil:.2_0(+(x, 1)) <=> .(gen_nil:.2_0(x)) 5.55/2.16 5.55/2.16 5.55/2.16 The following defined symbols remain to be analysed: 5.55/2.16 ++ 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (15) RewriteLemmaProof (LOWER BOUND(ID)) 5.55/2.16 Proved the following rewrite lemma: 5.55/2.16 ++(gen_nil:.2_0(n4_0), gen_nil:.2_0(b)) -> gen_nil:.2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 5.55/2.16 5.55/2.16 Induction Base: 5.55/2.16 ++(gen_nil:.2_0(0), gen_nil:.2_0(b)) ->_R^Omega(1) 5.55/2.16 gen_nil:.2_0(b) 5.55/2.16 5.55/2.16 Induction Step: 5.55/2.16 ++(gen_nil:.2_0(+(n4_0, 1)), gen_nil:.2_0(b)) ->_R^Omega(1) 5.55/2.16 .(++(gen_nil:.2_0(n4_0), gen_nil:.2_0(b))) ->_IH 5.55/2.16 .(gen_nil:.2_0(+(b, c5_0))) 5.55/2.16 5.55/2.16 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (16) 5.55/2.16 Obligation: 5.55/2.16 Proved the lower bound n^1 for the following obligation: 5.55/2.16 5.55/2.16 TRS: 5.55/2.16 Rules: 5.55/2.16 ++(nil, y) -> y 5.55/2.16 ++(x, nil) -> x 5.55/2.16 ++(.(y), z) -> .(++(y, z)) 5.55/2.16 ++(++(x, y), z) -> ++(x, ++(y, z)) 5.55/2.16 5.55/2.16 Types: 5.55/2.16 ++ :: nil:. -> nil:. -> nil:. 5.55/2.16 nil :: nil:. 5.55/2.16 . :: nil:. -> nil:. 5.55/2.16 hole_nil:.1_0 :: nil:. 5.55/2.16 gen_nil:.2_0 :: Nat -> nil:. 5.55/2.16 5.55/2.16 5.55/2.16 Generator Equations: 5.55/2.16 gen_nil:.2_0(0) <=> nil 5.55/2.16 gen_nil:.2_0(+(x, 1)) <=> .(gen_nil:.2_0(x)) 5.55/2.16 5.55/2.16 5.55/2.16 The following defined symbols remain to be analysed: 5.55/2.16 ++ 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (17) LowerBoundPropagationProof (FINISHED) 5.55/2.16 Propagated lower bound. 5.55/2.16 ---------------------------------------- 5.55/2.16 5.55/2.16 (18) 5.55/2.16 BOUNDS(n^1, INF) 5.86/2.21 EOF