320.93/291.50 WORST_CASE(Omega(n^2), ?) 320.93/291.51 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 320.93/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 320.93/291.51 320.93/291.51 320.93/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 320.93/291.51 320.93/291.51 (0) CpxTRS 320.93/291.51 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 320.93/291.51 (2) CpxTRS 320.93/291.51 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 320.93/291.51 (4) CpxTRS 320.93/291.51 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 320.93/291.51 (6) typed CpxTrs 320.93/291.51 (7) OrderProof [LOWER BOUND(ID), 0 ms] 320.93/291.51 (8) typed CpxTrs 320.93/291.51 (9) RewriteLemmaProof [LOWER BOUND(ID), 257 ms] 320.93/291.51 (10) BEST 320.93/291.51 (11) proven lower bound 320.93/291.51 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 320.93/291.51 (13) BOUNDS(n^1, INF) 320.93/291.51 (14) typed CpxTrs 320.93/291.51 (15) RewriteLemmaProof [LOWER BOUND(ID), 608 ms] 320.93/291.51 (16) typed CpxTrs 320.93/291.51 (17) RewriteLemmaProof [LOWER BOUND(ID), 261 ms] 320.93/291.51 (18) BEST 320.93/291.51 (19) proven lower bound 320.93/291.51 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 320.93/291.51 (21) BOUNDS(n^2, INF) 320.93/291.51 (22) typed CpxTrs 320.93/291.51 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (0) 320.93/291.51 Obligation: 320.93/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 320.93/291.51 320.93/291.51 320.93/291.51 The TRS R consists of the following rules: 320.93/291.51 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0) -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0) -> 0 320.93/291.51 p(s(0)) -> 0 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, x, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, x, y) -> cons(0, nil) 320.93/291.51 if1(false, x, y) -> cons(0, int(s(0), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 S is empty. 320.93/291.51 Rewrite Strategy: FULL 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 320.93/291.51 Renamed function symbols to avoid clashes with predefined symbol. 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (2) 320.93/291.51 Obligation: 320.93/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 320.93/291.51 320.93/291.51 320.93/291.51 The TRS R consists of the following rules: 320.93/291.51 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, x, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, x, y) -> cons(0', nil) 320.93/291.51 if1(false, x, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 S is empty. 320.93/291.51 Rewrite Strategy: FULL 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (3) SlicingProof (LOWER BOUND(ID)) 320.93/291.51 Sliced the following arguments: 320.93/291.51 if1/1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (4) 320.93/291.51 Obligation: 320.93/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 320.93/291.51 320.93/291.51 320.93/291.51 The TRS R consists of the following rules: 320.93/291.51 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 S is empty. 320.93/291.51 Rewrite Strategy: FULL 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 320.93/291.51 Infered types. 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (6) 320.93/291.51 Obligation: 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (7) OrderProof (LOWER BOUND(ID)) 320.93/291.51 Heuristically decided to analyse the following defined symbols: 320.93/291.51 p, intlist, int, if1 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 p < int 320.93/291.51 intlist < int 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (8) 320.93/291.51 Obligation: 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 p, intlist, int, if1 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 p < int 320.93/291.51 intlist < int 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (9) RewriteLemmaProof (LOWER BOUND(ID)) 320.93/291.51 Proved the following rewrite lemma: 320.93/291.51 p(gen_0':s5_0(+(1, n7_0))) -> gen_0':s5_0(n7_0), rt in Omega(1 + n7_0) 320.93/291.51 320.93/291.51 Induction Base: 320.93/291.51 p(gen_0':s5_0(+(1, 0))) ->_R^Omega(1) 320.93/291.51 0' 320.93/291.51 320.93/291.51 Induction Step: 320.93/291.51 p(gen_0':s5_0(+(1, +(n7_0, 1)))) ->_R^Omega(1) 320.93/291.51 s(p(s(gen_0':s5_0(n7_0)))) ->_IH 320.93/291.51 s(gen_0':s5_0(c8_0)) 320.93/291.51 320.93/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (10) 320.93/291.51 Complex Obligation (BEST) 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (11) 320.93/291.51 Obligation: 320.93/291.51 Proved the lower bound n^1 for the following obligation: 320.93/291.51 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 p, intlist, int, if1 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 p < int 320.93/291.51 intlist < int 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (12) LowerBoundPropagationProof (FINISHED) 320.93/291.51 Propagated lower bound. 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (13) 320.93/291.51 BOUNDS(n^1, INF) 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (14) 320.93/291.51 Obligation: 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Lemmas: 320.93/291.51 p(gen_0':s5_0(+(1, n7_0))) -> gen_0':s5_0(n7_0), rt in Omega(1 + n7_0) 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 intlist, int, if1 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 intlist < int 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (15) RewriteLemmaProof (LOWER BOUND(ID)) 320.93/291.51 Proved the following rewrite lemma: 320.93/291.51 intlist(gen_nil:cons4_0(n312_0)) -> *6_0, rt in Omega(n312_0) 320.93/291.51 320.93/291.51 Induction Base: 320.93/291.51 intlist(gen_nil:cons4_0(0)) 320.93/291.51 320.93/291.51 Induction Step: 320.93/291.51 intlist(gen_nil:cons4_0(+(n312_0, 1))) ->_R^Omega(1) 320.93/291.51 if_intlist(empty(gen_nil:cons4_0(+(n312_0, 1))), gen_nil:cons4_0(+(n312_0, 1))) ->_R^Omega(1) 320.93/291.51 if_intlist(false, gen_nil:cons4_0(+(1, n312_0))) ->_R^Omega(1) 320.93/291.51 cons(s(head(gen_nil:cons4_0(+(1, n312_0)))), intlist(tail(gen_nil:cons4_0(+(1, n312_0))))) ->_R^Omega(1) 320.93/291.51 cons(s(0'), intlist(tail(gen_nil:cons4_0(+(1, n312_0))))) ->_R^Omega(1) 320.93/291.51 cons(s(0'), intlist(gen_nil:cons4_0(n312_0))) ->_IH 320.93/291.51 cons(s(0'), *6_0) 320.93/291.51 320.93/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (16) 320.93/291.51 Obligation: 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Lemmas: 320.93/291.51 p(gen_0':s5_0(+(1, n7_0))) -> gen_0':s5_0(n7_0), rt in Omega(1 + n7_0) 320.93/291.51 intlist(gen_nil:cons4_0(n312_0)) -> *6_0, rt in Omega(n312_0) 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 if1, int 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (17) RewriteLemmaProof (LOWER BOUND(ID)) 320.93/291.51 Proved the following rewrite lemma: 320.93/291.51 int(gen_0':s5_0(+(1, n5442_0)), gen_0':s5_0(n5442_0)) -> gen_nil:cons4_0(0), rt in Omega(1 + n5442_0 + n5442_0^2) 320.93/291.51 320.93/291.51 Induction Base: 320.93/291.51 int(gen_0':s5_0(+(1, 0)), gen_0':s5_0(0)) ->_R^Omega(1) 320.93/291.51 if_int(zero(gen_0':s5_0(+(1, 0))), zero(gen_0':s5_0(0)), gen_0':s5_0(+(1, 0)), gen_0':s5_0(0)) ->_R^Omega(1) 320.93/291.51 if_int(false, zero(gen_0':s5_0(0)), gen_0':s5_0(1), gen_0':s5_0(0)) ->_R^Omega(1) 320.93/291.51 if_int(false, true, gen_0':s5_0(1), gen_0':s5_0(0)) ->_R^Omega(1) 320.93/291.51 if2(true, gen_0':s5_0(1), gen_0':s5_0(0)) ->_R^Omega(1) 320.93/291.51 nil 320.93/291.51 320.93/291.51 Induction Step: 320.93/291.51 int(gen_0':s5_0(+(1, +(n5442_0, 1))), gen_0':s5_0(+(n5442_0, 1))) ->_R^Omega(1) 320.93/291.51 if_int(zero(gen_0':s5_0(+(1, +(n5442_0, 1)))), zero(gen_0':s5_0(+(n5442_0, 1))), gen_0':s5_0(+(1, +(n5442_0, 1))), gen_0':s5_0(+(n5442_0, 1))) ->_R^Omega(1) 320.93/291.51 if_int(false, zero(gen_0':s5_0(+(1, n5442_0))), gen_0':s5_0(+(2, n5442_0)), gen_0':s5_0(+(1, n5442_0))) ->_R^Omega(1) 320.93/291.51 if_int(false, false, gen_0':s5_0(+(2, n5442_0)), gen_0':s5_0(+(1, n5442_0))) ->_R^Omega(1) 320.93/291.51 if2(false, gen_0':s5_0(+(2, n5442_0)), gen_0':s5_0(+(1, n5442_0))) ->_R^Omega(1) 320.93/291.51 intlist(int(p(gen_0':s5_0(+(2, n5442_0))), p(gen_0':s5_0(+(1, n5442_0))))) ->_L^Omega(2 + n5442_0) 320.93/291.51 intlist(int(gen_0':s5_0(+(1, n5442_0)), p(gen_0':s5_0(+(1, n5442_0))))) ->_L^Omega(1 + n5442_0) 320.93/291.51 intlist(int(gen_0':s5_0(+(1, n5442_0)), gen_0':s5_0(n5442_0))) ->_IH 320.93/291.51 intlist(gen_nil:cons4_0(0)) ->_R^Omega(1) 320.93/291.51 if_intlist(empty(gen_nil:cons4_0(0)), gen_nil:cons4_0(0)) ->_R^Omega(1) 320.93/291.51 if_intlist(true, gen_nil:cons4_0(0)) ->_R^Omega(1) 320.93/291.51 nil 320.93/291.51 320.93/291.51 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (18) 320.93/291.51 Complex Obligation (BEST) 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (19) 320.93/291.51 Obligation: 320.93/291.51 Proved the lower bound n^2 for the following obligation: 320.93/291.51 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Lemmas: 320.93/291.51 p(gen_0':s5_0(+(1, n7_0))) -> gen_0':s5_0(n7_0), rt in Omega(1 + n7_0) 320.93/291.51 intlist(gen_nil:cons4_0(n312_0)) -> *6_0, rt in Omega(n312_0) 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 int 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 int = if1 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (20) LowerBoundPropagationProof (FINISHED) 320.93/291.51 Propagated lower bound. 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (21) 320.93/291.51 BOUNDS(n^2, INF) 320.93/291.51 320.93/291.51 ---------------------------------------- 320.93/291.51 320.93/291.51 (22) 320.93/291.51 Obligation: 320.93/291.51 TRS: 320.93/291.51 Rules: 320.93/291.51 empty(nil) -> true 320.93/291.51 empty(cons(x, y)) -> false 320.93/291.51 tail(nil) -> nil 320.93/291.51 tail(cons(x, y)) -> y 320.93/291.51 head(cons(x, y)) -> x 320.93/291.51 zero(0') -> true 320.93/291.51 zero(s(x)) -> false 320.93/291.51 p(0') -> 0' 320.93/291.51 p(s(0')) -> 0' 320.93/291.51 p(s(s(x))) -> s(p(s(x))) 320.93/291.51 intlist(x) -> if_intlist(empty(x), x) 320.93/291.51 if_intlist(true, x) -> nil 320.93/291.51 if_intlist(false, x) -> cons(s(head(x)), intlist(tail(x))) 320.93/291.51 int(x, y) -> if_int(zero(x), zero(y), x, y) 320.93/291.51 if_int(true, b, x, y) -> if1(b, y) 320.93/291.51 if_int(false, b, x, y) -> if2(b, x, y) 320.93/291.51 if1(true, y) -> cons(0', nil) 320.93/291.51 if1(false, y) -> cons(0', int(s(0'), y)) 320.93/291.51 if2(true, x, y) -> nil 320.93/291.51 if2(false, x, y) -> intlist(int(p(x), p(y))) 320.93/291.51 320.93/291.51 Types: 320.93/291.51 empty :: nil:cons -> true:false 320.93/291.51 nil :: nil:cons 320.93/291.51 true :: true:false 320.93/291.51 cons :: 0':s -> nil:cons -> nil:cons 320.93/291.51 false :: true:false 320.93/291.51 tail :: nil:cons -> nil:cons 320.93/291.51 head :: nil:cons -> 0':s 320.93/291.51 zero :: 0':s -> true:false 320.93/291.51 0' :: 0':s 320.93/291.51 s :: 0':s -> 0':s 320.93/291.51 p :: 0':s -> 0':s 320.93/291.51 intlist :: nil:cons -> nil:cons 320.93/291.51 if_intlist :: true:false -> nil:cons -> nil:cons 320.93/291.51 int :: 0':s -> 0':s -> nil:cons 320.93/291.51 if_int :: true:false -> true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 if1 :: true:false -> 0':s -> nil:cons 320.93/291.51 if2 :: true:false -> 0':s -> 0':s -> nil:cons 320.93/291.51 hole_true:false1_0 :: true:false 320.93/291.51 hole_nil:cons2_0 :: nil:cons 320.93/291.51 hole_0':s3_0 :: 0':s 320.93/291.51 gen_nil:cons4_0 :: Nat -> nil:cons 320.93/291.51 gen_0':s5_0 :: Nat -> 0':s 320.93/291.51 320.93/291.51 320.93/291.51 Lemmas: 320.93/291.51 p(gen_0':s5_0(+(1, n7_0))) -> gen_0':s5_0(n7_0), rt in Omega(1 + n7_0) 320.93/291.51 intlist(gen_nil:cons4_0(n312_0)) -> *6_0, rt in Omega(n312_0) 320.93/291.51 int(gen_0':s5_0(+(1, n5442_0)), gen_0':s5_0(n5442_0)) -> gen_nil:cons4_0(0), rt in Omega(1 + n5442_0 + n5442_0^2) 320.93/291.51 320.93/291.51 320.93/291.51 Generator Equations: 320.93/291.51 gen_nil:cons4_0(0) <=> nil 320.93/291.51 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 320.93/291.51 gen_0':s5_0(0) <=> 0' 320.93/291.51 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 320.93/291.51 320.93/291.51 320.93/291.51 The following defined symbols remain to be analysed: 320.93/291.51 if1 320.93/291.51 320.93/291.51 They will be analysed ascendingly in the following order: 320.93/291.51 int = if1 321.05/291.56 EOF