1005.99/291.49 WORST_CASE(Omega(n^1), ?) 1005.99/291.50 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1005.99/291.50 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1005.99/291.50 1005.99/291.50 1005.99/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1005.99/291.50 1005.99/291.50 (0) CpxTRS 1005.99/291.50 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1005.99/291.50 (2) CpxTRS 1005.99/291.50 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1005.99/291.50 (4) typed CpxTrs 1005.99/291.50 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1005.99/291.50 (6) typed CpxTrs 1005.99/291.50 (7) RewriteLemmaProof [LOWER BOUND(ID), 25.3 s] 1005.99/291.50 (8) BEST 1005.99/291.50 (9) proven lower bound 1005.99/291.50 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1005.99/291.50 (11) BOUNDS(n^1, INF) 1005.99/291.50 (12) typed CpxTrs 1005.99/291.50 (13) RewriteLemmaProof [LOWER BOUND(ID), 36 ms] 1005.99/291.50 (14) BOUNDS(1, INF) 1005.99/291.50 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (0) 1005.99/291.50 Obligation: 1005.99/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1005.99/291.50 1005.99/291.50 1005.99/291.50 The TRS R consists of the following rules: 1005.99/291.50 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0) -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0, s(y)) -> cons(0, int(s(0), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 S is empty. 1005.99/291.50 Rewrite Strategy: FULL 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1005.99/291.50 Renamed function symbols to avoid clashes with predefined symbol. 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (2) 1005.99/291.50 Obligation: 1005.99/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1005.99/291.50 1005.99/291.50 1005.99/291.50 The TRS R consists of the following rules: 1005.99/291.50 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0') -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0', s(y)) -> cons(0', int(s(0'), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 S is empty. 1005.99/291.50 Rewrite Strategy: FULL 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1005.99/291.50 Infered types. 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (4) 1005.99/291.50 Obligation: 1005.99/291.50 TRS: 1005.99/291.50 Rules: 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0') -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0', s(y)) -> cons(0', int(s(0'), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 Types: 1005.99/291.50 intlist :: nil:cons -> nil:cons 1005.99/291.50 nil :: nil:cons 1005.99/291.50 int :: s:0' -> s:0' -> nil:cons 1005.99/291.50 s :: s:0' -> s:0' 1005.99/291.50 0' :: s:0' 1005.99/291.50 cons :: s:0' -> nil:cons -> nil:cons 1005.99/291.50 hole_nil:cons1_0 :: nil:cons 1005.99/291.50 hole_s:0'2_0 :: s:0' 1005.99/291.50 gen_nil:cons3_0 :: Nat -> nil:cons 1005.99/291.50 gen_s:0'4_0 :: Nat -> s:0' 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (5) OrderProof (LOWER BOUND(ID)) 1005.99/291.50 Heuristically decided to analyse the following defined symbols: 1005.99/291.50 intlist, int 1005.99/291.50 1005.99/291.50 They will be analysed ascendingly in the following order: 1005.99/291.50 intlist < int 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (6) 1005.99/291.50 Obligation: 1005.99/291.50 TRS: 1005.99/291.50 Rules: 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0') -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0', s(y)) -> cons(0', int(s(0'), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 Types: 1005.99/291.50 intlist :: nil:cons -> nil:cons 1005.99/291.50 nil :: nil:cons 1005.99/291.50 int :: s:0' -> s:0' -> nil:cons 1005.99/291.50 s :: s:0' -> s:0' 1005.99/291.50 0' :: s:0' 1005.99/291.50 cons :: s:0' -> nil:cons -> nil:cons 1005.99/291.50 hole_nil:cons1_0 :: nil:cons 1005.99/291.50 hole_s:0'2_0 :: s:0' 1005.99/291.50 gen_nil:cons3_0 :: Nat -> nil:cons 1005.99/291.50 gen_s:0'4_0 :: Nat -> s:0' 1005.99/291.50 1005.99/291.50 1005.99/291.50 Generator Equations: 1005.99/291.50 gen_nil:cons3_0(0) <=> nil 1005.99/291.50 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 1005.99/291.50 gen_s:0'4_0(0) <=> 0' 1005.99/291.50 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 1005.99/291.50 1005.99/291.50 1005.99/291.50 The following defined symbols remain to be analysed: 1005.99/291.50 intlist, int 1005.99/291.50 1005.99/291.50 They will be analysed ascendingly in the following order: 1005.99/291.50 intlist < int 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1005.99/291.50 Proved the following rewrite lemma: 1005.99/291.50 intlist(gen_nil:cons3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 1005.99/291.50 1005.99/291.50 Induction Base: 1005.99/291.50 intlist(gen_nil:cons3_0(+(1, 0))) 1005.99/291.50 1005.99/291.50 Induction Step: 1005.99/291.50 intlist(gen_nil:cons3_0(+(1, +(n6_0, 1)))) ->_R^Omega(1) 1005.99/291.50 cons(s(0'), intlist(gen_nil:cons3_0(+(1, n6_0)))) ->_IH 1005.99/291.50 cons(s(0'), *5_0) 1005.99/291.50 1005.99/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (8) 1005.99/291.50 Complex Obligation (BEST) 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (9) 1005.99/291.50 Obligation: 1005.99/291.50 Proved the lower bound n^1 for the following obligation: 1005.99/291.50 1005.99/291.50 TRS: 1005.99/291.50 Rules: 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0') -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0', s(y)) -> cons(0', int(s(0'), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 Types: 1005.99/291.50 intlist :: nil:cons -> nil:cons 1005.99/291.50 nil :: nil:cons 1005.99/291.50 int :: s:0' -> s:0' -> nil:cons 1005.99/291.50 s :: s:0' -> s:0' 1005.99/291.50 0' :: s:0' 1005.99/291.50 cons :: s:0' -> nil:cons -> nil:cons 1005.99/291.50 hole_nil:cons1_0 :: nil:cons 1005.99/291.50 hole_s:0'2_0 :: s:0' 1005.99/291.50 gen_nil:cons3_0 :: Nat -> nil:cons 1005.99/291.50 gen_s:0'4_0 :: Nat -> s:0' 1005.99/291.50 1005.99/291.50 1005.99/291.50 Generator Equations: 1005.99/291.50 gen_nil:cons3_0(0) <=> nil 1005.99/291.50 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 1005.99/291.50 gen_s:0'4_0(0) <=> 0' 1005.99/291.50 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 1005.99/291.50 1005.99/291.50 1005.99/291.50 The following defined symbols remain to be analysed: 1005.99/291.50 intlist, int 1005.99/291.50 1005.99/291.50 They will be analysed ascendingly in the following order: 1005.99/291.50 intlist < int 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (10) LowerBoundPropagationProof (FINISHED) 1005.99/291.50 Propagated lower bound. 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (11) 1005.99/291.50 BOUNDS(n^1, INF) 1005.99/291.50 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (12) 1005.99/291.50 Obligation: 1005.99/291.50 TRS: 1005.99/291.50 Rules: 1005.99/291.50 intlist(nil) -> nil 1005.99/291.50 int(s(x), 0') -> nil 1005.99/291.50 int(x, x) -> cons(x, nil) 1005.99/291.50 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 1005.99/291.50 int(s(x), s(y)) -> intlist(int(x, y)) 1005.99/291.50 int(0', s(y)) -> cons(0', int(s(0'), s(y))) 1005.99/291.50 intlist(cons(x, nil)) -> cons(s(x), nil) 1005.99/291.50 1005.99/291.50 Types: 1005.99/291.50 intlist :: nil:cons -> nil:cons 1005.99/291.50 nil :: nil:cons 1005.99/291.50 int :: s:0' -> s:0' -> nil:cons 1005.99/291.50 s :: s:0' -> s:0' 1005.99/291.50 0' :: s:0' 1005.99/291.50 cons :: s:0' -> nil:cons -> nil:cons 1005.99/291.50 hole_nil:cons1_0 :: nil:cons 1005.99/291.50 hole_s:0'2_0 :: s:0' 1005.99/291.50 gen_nil:cons3_0 :: Nat -> nil:cons 1005.99/291.50 gen_s:0'4_0 :: Nat -> s:0' 1005.99/291.50 1005.99/291.50 1005.99/291.50 Lemmas: 1005.99/291.50 intlist(gen_nil:cons3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 1005.99/291.50 1005.99/291.50 1005.99/291.50 Generator Equations: 1005.99/291.50 gen_nil:cons3_0(0) <=> nil 1005.99/291.50 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 1005.99/291.50 gen_s:0'4_0(0) <=> 0' 1005.99/291.50 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 1005.99/291.50 1005.99/291.50 1005.99/291.50 The following defined symbols remain to be analysed: 1005.99/291.50 int 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1005.99/291.50 Proved the following rewrite lemma: 1005.99/291.50 int(gen_s:0'4_0(+(1, n389747_0)), gen_s:0'4_0(n389747_0)) -> gen_nil:cons3_0(0), rt in Omega(1 + n389747_0) 1005.99/291.50 1005.99/291.50 Induction Base: 1005.99/291.50 int(gen_s:0'4_0(+(1, 0)), gen_s:0'4_0(0)) ->_R^Omega(1) 1005.99/291.50 nil 1005.99/291.50 1005.99/291.50 Induction Step: 1005.99/291.50 int(gen_s:0'4_0(+(1, +(n389747_0, 1))), gen_s:0'4_0(+(n389747_0, 1))) ->_R^Omega(1) 1005.99/291.50 intlist(int(gen_s:0'4_0(+(1, n389747_0)), gen_s:0'4_0(n389747_0))) ->_IH 1005.99/291.50 intlist(gen_nil:cons3_0(0)) ->_R^Omega(1) 1005.99/291.50 nil 1005.99/291.50 1005.99/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1005.99/291.50 ---------------------------------------- 1005.99/291.50 1005.99/291.50 (14) 1005.99/291.50 BOUNDS(1, INF) 1006.26/291.56 EOF