529.87/291.45 WORST_CASE(Omega(n^1), ?) 529.87/291.46 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 529.87/291.46 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 529.87/291.46 529.87/291.46 529.87/291.46 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 529.87/291.46 529.87/291.46 (0) CpxTRS 529.87/291.46 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 529.87/291.46 (2) CpxTRS 529.87/291.46 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 529.87/291.46 (4) typed CpxTrs 529.87/291.46 (5) OrderProof [LOWER BOUND(ID), 0 ms] 529.87/291.46 (6) typed CpxTrs 529.87/291.46 (7) RewriteLemmaProof [LOWER BOUND(ID), 222 ms] 529.87/291.46 (8) BEST 529.87/291.46 (9) proven lower bound 529.87/291.46 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 529.87/291.46 (11) BOUNDS(n^1, INF) 529.87/291.46 (12) typed CpxTrs 529.87/291.46 (13) RewriteLemmaProof [LOWER BOUND(ID), 65 ms] 529.87/291.46 (14) BOUNDS(1, INF) 529.87/291.46 529.87/291.46 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (0) 529.87/291.46 Obligation: 529.87/291.46 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 529.87/291.46 529.87/291.46 529.87/291.46 The TRS R consists of the following rules: 529.87/291.46 529.87/291.46 fib(N) -> sel(N, fib1(s(0), s(0))) 529.87/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.87/291.46 add(0, X) -> X 529.87/291.46 add(s(X), Y) -> s(add(X, Y)) 529.87/291.46 sel(0, cons(X, XS)) -> X 529.87/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.87/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.87/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.87/291.46 activate(X) -> X 529.87/291.46 529.87/291.46 S is empty. 529.87/291.46 Rewrite Strategy: INNERMOST 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 529.87/291.46 Renamed function symbols to avoid clashes with predefined symbol. 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (2) 529.87/291.46 Obligation: 529.87/291.46 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 529.87/291.46 529.87/291.46 529.87/291.46 The TRS R consists of the following rules: 529.87/291.46 529.87/291.46 fib(N) -> sel(N, fib1(s(0'), s(0'))) 529.87/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.87/291.46 add(0', X) -> X 529.87/291.46 add(s(X), Y) -> s(add(X, Y)) 529.87/291.46 sel(0', cons(X, XS)) -> X 529.87/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.87/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.87/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.87/291.46 activate(X) -> X 529.87/291.46 529.87/291.46 S is empty. 529.87/291.46 Rewrite Strategy: INNERMOST 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 529.87/291.46 Infered types. 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (4) 529.87/291.46 Obligation: 529.87/291.46 Innermost TRS: 529.87/291.46 Rules: 529.87/291.46 fib(N) -> sel(N, fib1(s(0'), s(0'))) 529.87/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.87/291.46 add(0', X) -> X 529.87/291.46 add(s(X), Y) -> s(add(X, Y)) 529.87/291.46 sel(0', cons(X, XS)) -> X 529.87/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.87/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.87/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.87/291.46 activate(X) -> X 529.87/291.46 529.87/291.46 Types: 529.87/291.46 fib :: 0':s -> 0':s 529.87/291.46 sel :: 0':s -> n__fib1:cons -> 0':s 529.87/291.46 fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 s :: 0':s -> 0':s 529.87/291.46 0' :: 0':s 529.87/291.46 cons :: 0':s -> n__fib1:cons -> n__fib1:cons 529.87/291.46 n__fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 add :: 0':s -> 0':s -> 0':s 529.87/291.46 activate :: n__fib1:cons -> n__fib1:cons 529.87/291.46 hole_0':s1_0 :: 0':s 529.87/291.46 hole_n__fib1:cons2_0 :: n__fib1:cons 529.87/291.46 gen_0':s3_0 :: Nat -> 0':s 529.87/291.46 gen_n__fib1:cons4_0 :: Nat -> n__fib1:cons 529.87/291.46 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (5) OrderProof (LOWER BOUND(ID)) 529.87/291.46 Heuristically decided to analyse the following defined symbols: 529.87/291.46 sel, add 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (6) 529.87/291.46 Obligation: 529.87/291.46 Innermost TRS: 529.87/291.46 Rules: 529.87/291.46 fib(N) -> sel(N, fib1(s(0'), s(0'))) 529.87/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.87/291.46 add(0', X) -> X 529.87/291.46 add(s(X), Y) -> s(add(X, Y)) 529.87/291.46 sel(0', cons(X, XS)) -> X 529.87/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.87/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.87/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.87/291.46 activate(X) -> X 529.87/291.46 529.87/291.46 Types: 529.87/291.46 fib :: 0':s -> 0':s 529.87/291.46 sel :: 0':s -> n__fib1:cons -> 0':s 529.87/291.46 fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 s :: 0':s -> 0':s 529.87/291.46 0' :: 0':s 529.87/291.46 cons :: 0':s -> n__fib1:cons -> n__fib1:cons 529.87/291.46 n__fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 add :: 0':s -> 0':s -> 0':s 529.87/291.46 activate :: n__fib1:cons -> n__fib1:cons 529.87/291.46 hole_0':s1_0 :: 0':s 529.87/291.46 hole_n__fib1:cons2_0 :: n__fib1:cons 529.87/291.46 gen_0':s3_0 :: Nat -> 0':s 529.87/291.46 gen_n__fib1:cons4_0 :: Nat -> n__fib1:cons 529.87/291.46 529.87/291.46 529.87/291.46 Generator Equations: 529.87/291.46 gen_0':s3_0(0) <=> 0' 529.87/291.46 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 529.87/291.46 gen_n__fib1:cons4_0(0) <=> n__fib1(0', 0') 529.87/291.46 gen_n__fib1:cons4_0(+(x, 1)) <=> cons(0', gen_n__fib1:cons4_0(x)) 529.87/291.46 529.87/291.46 529.87/291.46 The following defined symbols remain to be analysed: 529.87/291.46 sel, add 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (7) RewriteLemmaProof (LOWER BOUND(ID)) 529.87/291.46 Proved the following rewrite lemma: 529.87/291.46 sel(gen_0':s3_0(n6_0), gen_n__fib1:cons4_0(1)) -> gen_0':s3_0(0), rt in Omega(1 + n6_0) 529.87/291.46 529.87/291.46 Induction Base: 529.87/291.46 sel(gen_0':s3_0(0), gen_n__fib1:cons4_0(1)) ->_R^Omega(1) 529.87/291.46 0' 529.87/291.46 529.87/291.46 Induction Step: 529.87/291.46 sel(gen_0':s3_0(+(n6_0, 1)), gen_n__fib1:cons4_0(1)) ->_R^Omega(1) 529.87/291.46 sel(gen_0':s3_0(n6_0), activate(gen_n__fib1:cons4_0(0))) ->_R^Omega(1) 529.87/291.46 sel(gen_0':s3_0(n6_0), fib1(0', 0')) ->_R^Omega(1) 529.87/291.46 sel(gen_0':s3_0(n6_0), cons(0', n__fib1(0', add(0', 0')))) ->_R^Omega(1) 529.87/291.46 sel(gen_0':s3_0(n6_0), cons(0', n__fib1(0', 0'))) ->_IH 529.87/291.46 gen_0':s3_0(0) 529.87/291.46 529.87/291.46 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (8) 529.87/291.46 Complex Obligation (BEST) 529.87/291.46 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (9) 529.87/291.46 Obligation: 529.87/291.46 Proved the lower bound n^1 for the following obligation: 529.87/291.46 529.87/291.46 Innermost TRS: 529.87/291.46 Rules: 529.87/291.46 fib(N) -> sel(N, fib1(s(0'), s(0'))) 529.87/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.87/291.46 add(0', X) -> X 529.87/291.46 add(s(X), Y) -> s(add(X, Y)) 529.87/291.46 sel(0', cons(X, XS)) -> X 529.87/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.87/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.87/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.87/291.46 activate(X) -> X 529.87/291.46 529.87/291.46 Types: 529.87/291.46 fib :: 0':s -> 0':s 529.87/291.46 sel :: 0':s -> n__fib1:cons -> 0':s 529.87/291.46 fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 s :: 0':s -> 0':s 529.87/291.46 0' :: 0':s 529.87/291.46 cons :: 0':s -> n__fib1:cons -> n__fib1:cons 529.87/291.46 n__fib1 :: 0':s -> 0':s -> n__fib1:cons 529.87/291.46 add :: 0':s -> 0':s -> 0':s 529.87/291.46 activate :: n__fib1:cons -> n__fib1:cons 529.87/291.46 hole_0':s1_0 :: 0':s 529.87/291.46 hole_n__fib1:cons2_0 :: n__fib1:cons 529.87/291.46 gen_0':s3_0 :: Nat -> 0':s 529.87/291.46 gen_n__fib1:cons4_0 :: Nat -> n__fib1:cons 529.87/291.46 529.87/291.46 529.87/291.46 Generator Equations: 529.87/291.46 gen_0':s3_0(0) <=> 0' 529.87/291.46 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 529.87/291.46 gen_n__fib1:cons4_0(0) <=> n__fib1(0', 0') 529.87/291.46 gen_n__fib1:cons4_0(+(x, 1)) <=> cons(0', gen_n__fib1:cons4_0(x)) 529.87/291.46 529.87/291.46 529.87/291.46 The following defined symbols remain to be analysed: 529.87/291.46 sel, add 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (10) LowerBoundPropagationProof (FINISHED) 529.87/291.46 Propagated lower bound. 529.87/291.46 ---------------------------------------- 529.87/291.46 529.87/291.46 (11) 529.87/291.46 BOUNDS(n^1, INF) 529.87/291.46 529.87/291.46 ---------------------------------------- 529.95/291.46 529.95/291.46 (12) 529.95/291.46 Obligation: 529.95/291.46 Innermost TRS: 529.95/291.46 Rules: 529.95/291.46 fib(N) -> sel(N, fib1(s(0'), s(0'))) 529.95/291.46 fib1(X, Y) -> cons(X, n__fib1(Y, add(X, Y))) 529.95/291.46 add(0', X) -> X 529.95/291.46 add(s(X), Y) -> s(add(X, Y)) 529.95/291.46 sel(0', cons(X, XS)) -> X 529.95/291.46 sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) 529.95/291.46 fib1(X1, X2) -> n__fib1(X1, X2) 529.95/291.46 activate(n__fib1(X1, X2)) -> fib1(X1, X2) 529.95/291.46 activate(X) -> X 529.95/291.46 529.95/291.46 Types: 529.95/291.46 fib :: 0':s -> 0':s 529.95/291.46 sel :: 0':s -> n__fib1:cons -> 0':s 529.95/291.46 fib1 :: 0':s -> 0':s -> n__fib1:cons 529.95/291.46 s :: 0':s -> 0':s 529.95/291.46 0' :: 0':s 529.95/291.46 cons :: 0':s -> n__fib1:cons -> n__fib1:cons 529.95/291.46 n__fib1 :: 0':s -> 0':s -> n__fib1:cons 529.95/291.46 add :: 0':s -> 0':s -> 0':s 529.95/291.46 activate :: n__fib1:cons -> n__fib1:cons 529.95/291.46 hole_0':s1_0 :: 0':s 529.95/291.46 hole_n__fib1:cons2_0 :: n__fib1:cons 529.95/291.46 gen_0':s3_0 :: Nat -> 0':s 529.95/291.46 gen_n__fib1:cons4_0 :: Nat -> n__fib1:cons 529.95/291.46 529.95/291.46 529.95/291.46 Lemmas: 529.95/291.46 sel(gen_0':s3_0(n6_0), gen_n__fib1:cons4_0(1)) -> gen_0':s3_0(0), rt in Omega(1 + n6_0) 529.95/291.46 529.95/291.46 529.95/291.46 Generator Equations: 529.95/291.46 gen_0':s3_0(0) <=> 0' 529.95/291.46 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 529.95/291.46 gen_n__fib1:cons4_0(0) <=> n__fib1(0', 0') 529.95/291.46 gen_n__fib1:cons4_0(+(x, 1)) <=> cons(0', gen_n__fib1:cons4_0(x)) 529.95/291.46 529.95/291.46 529.95/291.46 The following defined symbols remain to be analysed: 529.95/291.46 add 529.95/291.46 ---------------------------------------- 529.95/291.46 529.95/291.46 (13) RewriteLemmaProof (LOWER BOUND(ID)) 529.95/291.46 Proved the following rewrite lemma: 529.95/291.46 add(gen_0':s3_0(n379_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n379_0, b)), rt in Omega(1 + n379_0) 529.95/291.46 529.95/291.46 Induction Base: 529.95/291.46 add(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 529.95/291.46 gen_0':s3_0(b) 529.95/291.46 529.95/291.46 Induction Step: 529.95/291.46 add(gen_0':s3_0(+(n379_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 529.95/291.46 s(add(gen_0':s3_0(n379_0), gen_0':s3_0(b))) ->_IH 529.95/291.46 s(gen_0':s3_0(+(b, c380_0))) 529.95/291.46 529.95/291.46 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 529.95/291.46 ---------------------------------------- 529.95/291.46 529.95/291.46 (14) 529.95/291.46 BOUNDS(1, INF) 529.98/291.51 EOF