308.16/291.51 WORST_CASE(Omega(n^2), ?) 308.16/291.52 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 308.16/291.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 308.16/291.52 308.16/291.52 308.16/291.52 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 308.16/291.52 308.16/291.52 (0) CpxTRS 308.16/291.52 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 308.16/291.52 (2) CpxTRS 308.16/291.52 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 308.16/291.52 (4) typed CpxTrs 308.16/291.52 (5) OrderProof [LOWER BOUND(ID), 0 ms] 308.16/291.52 (6) typed CpxTrs 308.16/291.52 (7) RewriteLemmaProof [LOWER BOUND(ID), 285 ms] 308.16/291.52 (8) BEST 308.16/291.52 (9) proven lower bound 308.16/291.52 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 308.16/291.52 (11) BOUNDS(n^1, INF) 308.16/291.52 (12) typed CpxTrs 308.16/291.52 (13) RewriteLemmaProof [LOWER BOUND(ID), 54 ms] 308.16/291.52 (14) typed CpxTrs 308.16/291.52 (15) RewriteLemmaProof [LOWER BOUND(ID), 35 ms] 308.16/291.52 (16) typed CpxTrs 308.16/291.52 (17) RewriteLemmaProof [LOWER BOUND(ID), 789 ms] 308.16/291.52 (18) proven lower bound 308.16/291.52 (19) LowerBoundPropagationProof [FINISHED, 0 ms] 308.16/291.52 (20) BOUNDS(n^2, INF) 308.16/291.52 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (0) 308.16/291.52 Obligation: 308.16/291.52 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 308.16/291.52 308.16/291.52 308.16/291.52 The TRS R consists of the following rules: 308.16/291.52 308.16/291.52 eq(0, 0) -> true 308.16/291.52 eq(0, s(m)) -> false 308.16/291.52 eq(s(n), 0) -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0, m) -> true 308.16/291.52 le(s(n), 0) -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0, nil)) -> 0 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 S is empty. 308.16/291.52 Rewrite Strategy: FULL 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 308.16/291.52 Renamed function symbols to avoid clashes with predefined symbol. 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (2) 308.16/291.52 Obligation: 308.16/291.52 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 308.16/291.52 308.16/291.52 308.16/291.52 The TRS R consists of the following rules: 308.16/291.52 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 S is empty. 308.16/291.52 Rewrite Strategy: FULL 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 308.16/291.52 Infered types. 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (4) 308.16/291.52 Obligation: 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (5) OrderProof (LOWER BOUND(ID)) 308.16/291.52 Heuristically decided to analyse the following defined symbols: 308.16/291.52 eq, le, min, replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 eq < replace 308.16/291.52 le < min 308.16/291.52 min < sort 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (6) 308.16/291.52 Obligation: 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 eq, le, min, replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 eq < replace 308.16/291.52 le < min 308.16/291.52 min < sort 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (7) RewriteLemmaProof (LOWER BOUND(ID)) 308.16/291.52 Proved the following rewrite lemma: 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 308.16/291.52 308.16/291.52 Induction Base: 308.16/291.52 eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 308.16/291.52 true 308.16/291.52 308.16/291.52 Induction Step: 308.16/291.52 eq(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1) 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH 308.16/291.52 true 308.16/291.52 308.16/291.52 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (8) 308.16/291.52 Complex Obligation (BEST) 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (9) 308.16/291.52 Obligation: 308.16/291.52 Proved the lower bound n^1 for the following obligation: 308.16/291.52 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 eq, le, min, replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 eq < replace 308.16/291.52 le < min 308.16/291.52 min < sort 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (10) LowerBoundPropagationProof (FINISHED) 308.16/291.52 Propagated lower bound. 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (11) 308.16/291.52 BOUNDS(n^1, INF) 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (12) 308.16/291.52 Obligation: 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Lemmas: 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 le, min, replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 le < min 308.16/291.52 min < sort 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (13) RewriteLemmaProof (LOWER BOUND(ID)) 308.16/291.52 Proved the following rewrite lemma: 308.16/291.52 le(gen_0':s4_0(n518_0), gen_0':s4_0(n518_0)) -> true, rt in Omega(1 + n518_0) 308.16/291.52 308.16/291.52 Induction Base: 308.16/291.52 le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 308.16/291.52 true 308.16/291.52 308.16/291.52 Induction Step: 308.16/291.52 le(gen_0':s4_0(+(n518_0, 1)), gen_0':s4_0(+(n518_0, 1))) ->_R^Omega(1) 308.16/291.52 le(gen_0':s4_0(n518_0), gen_0':s4_0(n518_0)) ->_IH 308.16/291.52 true 308.16/291.52 308.16/291.52 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (14) 308.16/291.52 Obligation: 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Lemmas: 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 308.16/291.52 le(gen_0':s4_0(n518_0), gen_0':s4_0(n518_0)) -> true, rt in Omega(1 + n518_0) 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 min, replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 min < sort 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (15) RewriteLemmaProof (LOWER BOUND(ID)) 308.16/291.52 Proved the following rewrite lemma: 308.16/291.52 min(gen_nil:cons5_0(+(1, n823_0))) -> gen_0':s4_0(0), rt in Omega(1 + n823_0) 308.16/291.52 308.16/291.52 Induction Base: 308.16/291.52 min(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1) 308.16/291.52 0' 308.16/291.52 308.16/291.52 Induction Step: 308.16/291.52 min(gen_nil:cons5_0(+(1, +(n823_0, 1)))) ->_R^Omega(1) 308.16/291.52 if_min(le(0', 0'), cons(0', cons(0', gen_nil:cons5_0(n823_0)))) ->_L^Omega(1) 308.16/291.52 if_min(true, cons(0', cons(0', gen_nil:cons5_0(n823_0)))) ->_R^Omega(1) 308.16/291.52 min(cons(0', gen_nil:cons5_0(n823_0))) ->_IH 308.16/291.52 gen_0':s4_0(0) 308.16/291.52 308.16/291.52 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (16) 308.16/291.52 Obligation: 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Lemmas: 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 308.16/291.52 le(gen_0':s4_0(n518_0), gen_0':s4_0(n518_0)) -> true, rt in Omega(1 + n518_0) 308.16/291.52 min(gen_nil:cons5_0(+(1, n823_0))) -> gen_0':s4_0(0), rt in Omega(1 + n823_0) 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 replace, sort 308.16/291.52 308.16/291.52 They will be analysed ascendingly in the following order: 308.16/291.52 replace < sort 308.16/291.52 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (17) RewriteLemmaProof (LOWER BOUND(ID)) 308.16/291.52 Proved the following rewrite lemma: 308.16/291.52 sort(gen_nil:cons5_0(+(1, n1492_0))) -> *6_0, rt in Omega(n1492_0 + n1492_0^2) 308.16/291.52 308.16/291.52 Induction Base: 308.16/291.52 sort(gen_nil:cons5_0(+(1, 0))) 308.16/291.52 308.16/291.52 Induction Step: 308.16/291.52 sort(gen_nil:cons5_0(+(1, +(n1492_0, 1)))) ->_R^Omega(1) 308.16/291.52 cons(min(cons(0', gen_nil:cons5_0(+(1, n1492_0)))), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1492_0)))), 0', gen_nil:cons5_0(+(1, n1492_0))))) ->_L^Omega(2 + n1492_0) 308.16/291.52 cons(gen_0':s4_0(0), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1492_0)))), 0', gen_nil:cons5_0(+(1, n1492_0))))) ->_L^Omega(2 + n1492_0) 308.16/291.52 cons(gen_0':s4_0(0), sort(replace(gen_0':s4_0(0), 0', gen_nil:cons5_0(+(1, n1492_0))))) ->_R^Omega(1) 308.16/291.52 cons(gen_0':s4_0(0), sort(if_replace(eq(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1492_0))))) ->_L^Omega(1) 308.16/291.52 cons(gen_0':s4_0(0), sort(if_replace(true, gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1492_0))))) ->_R^Omega(1) 308.16/291.52 cons(gen_0':s4_0(0), sort(cons(0', gen_nil:cons5_0(n1492_0)))) ->_IH 308.16/291.52 cons(gen_0':s4_0(0), *6_0) 308.16/291.52 308.16/291.52 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (18) 308.16/291.52 Obligation: 308.16/291.52 Proved the lower bound n^2 for the following obligation: 308.16/291.52 308.16/291.52 TRS: 308.16/291.52 Rules: 308.16/291.52 eq(0', 0') -> true 308.16/291.52 eq(0', s(m)) -> false 308.16/291.52 eq(s(n), 0') -> false 308.16/291.52 eq(s(n), s(m)) -> eq(n, m) 308.16/291.52 le(0', m) -> true 308.16/291.52 le(s(n), 0') -> false 308.16/291.52 le(s(n), s(m)) -> le(n, m) 308.16/291.52 min(cons(0', nil)) -> 0' 308.16/291.52 min(cons(s(n), nil)) -> s(n) 308.16/291.52 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 308.16/291.52 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 308.16/291.52 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 308.16/291.52 replace(n, m, nil) -> nil 308.16/291.52 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 308.16/291.52 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 308.16/291.52 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 308.16/291.52 sort(nil) -> nil 308.16/291.52 sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 308.16/291.52 308.16/291.52 Types: 308.16/291.52 eq :: 0':s -> 0':s -> true:false 308.16/291.52 0' :: 0':s 308.16/291.52 true :: true:false 308.16/291.52 s :: 0':s -> 0':s 308.16/291.52 false :: true:false 308.16/291.52 le :: 0':s -> 0':s -> true:false 308.16/291.52 min :: nil:cons -> 0':s 308.16/291.52 cons :: 0':s -> nil:cons -> nil:cons 308.16/291.52 nil :: nil:cons 308.16/291.52 if_min :: true:false -> nil:cons -> 0':s 308.16/291.52 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 308.16/291.52 sort :: nil:cons -> nil:cons 308.16/291.52 hole_true:false1_0 :: true:false 308.16/291.52 hole_0':s2_0 :: 0':s 308.16/291.52 hole_nil:cons3_0 :: nil:cons 308.16/291.52 gen_0':s4_0 :: Nat -> 0':s 308.16/291.52 gen_nil:cons5_0 :: Nat -> nil:cons 308.16/291.52 308.16/291.52 308.16/291.52 Lemmas: 308.16/291.52 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 308.16/291.52 le(gen_0':s4_0(n518_0), gen_0':s4_0(n518_0)) -> true, rt in Omega(1 + n518_0) 308.16/291.52 min(gen_nil:cons5_0(+(1, n823_0))) -> gen_0':s4_0(0), rt in Omega(1 + n823_0) 308.16/291.52 308.16/291.52 308.16/291.52 Generator Equations: 308.16/291.52 gen_0':s4_0(0) <=> 0' 308.16/291.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 308.16/291.52 gen_nil:cons5_0(0) <=> nil 308.16/291.52 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 308.16/291.52 308.16/291.52 308.16/291.52 The following defined symbols remain to be analysed: 308.16/291.52 sort 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (19) LowerBoundPropagationProof (FINISHED) 308.16/291.52 Propagated lower bound. 308.16/291.52 ---------------------------------------- 308.16/291.52 308.16/291.52 (20) 308.16/291.52 BOUNDS(n^2, INF) 308.22/291.56 EOF