1098.01/291.61 WORST_CASE(Omega(n^1), ?) 1098.86/291.81 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1098.86/291.81 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1098.86/291.81 1098.86/291.81 1098.86/291.81 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1098.86/291.81 1098.86/291.81 (0) CpxTRS 1098.86/291.81 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1098.86/291.81 (2) CpxTRS 1098.86/291.81 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 1098.86/291.81 (4) CpxTRS 1098.86/291.81 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1098.86/291.81 (6) typed CpxTrs 1098.86/291.81 (7) OrderProof [LOWER BOUND(ID), 0 ms] 1098.86/291.81 (8) typed CpxTrs 1098.86/291.81 (9) RewriteLemmaProof [LOWER BOUND(ID), 342 ms] 1098.86/291.81 (10) BEST 1098.86/291.81 (11) proven lower bound 1098.86/291.81 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1098.86/291.81 (13) BOUNDS(n^1, INF) 1098.86/291.81 (14) typed CpxTrs 1098.86/291.81 (15) RewriteLemmaProof [LOWER BOUND(ID), 82 ms] 1098.86/291.81 (16) typed CpxTrs 1098.86/291.81 (17) RewriteLemmaProof [LOWER BOUND(ID), 45 ms] 1098.86/291.81 (18) typed CpxTrs 1098.86/291.81 (19) RewriteLemmaProof [LOWER BOUND(ID), 54 ms] 1098.86/291.81 (20) typed CpxTrs 1098.86/291.81 (21) RewriteLemmaProof [LOWER BOUND(ID), 55 ms] 1098.86/291.81 (22) typed CpxTrs 1098.86/291.81 (23) RewriteLemmaProof [LOWER BOUND(ID), 2231 ms] 1098.86/291.81 (24) typed CpxTrs 1098.86/291.81 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (0) 1098.86/291.81 Obligation: 1098.86/291.81 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1098.86/291.81 1098.86/291.81 1098.86/291.81 The TRS R consists of the following rules: 1098.86/291.81 1098.86/291.81 fstsplit(0, x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0, x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0, m) -> true 1098.86/291.81 leq(s(n), 0) -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(pid, nil) -> nil 1098.86/291.81 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(two, head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(two, head(in_2)), st_2)), cons(fstsplit(m, app(map_f(two, head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(two, head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(three, head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(three, head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(three, head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 S is empty. 1098.86/291.81 Rewrite Strategy: INNERMOST 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1098.86/291.81 Renamed function symbols to avoid clashes with predefined symbol. 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (2) 1098.86/291.81 Obligation: 1098.86/291.81 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1098.86/291.81 1098.86/291.81 1098.86/291.81 The TRS R consists of the following rules: 1098.86/291.81 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(pid, nil) -> nil 1098.86/291.81 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(two, head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(two, head(in_2)), st_2)), cons(fstsplit(m, app(map_f(two, head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(two, head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(three, head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(three, head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(three, head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 S is empty. 1098.86/291.81 Rewrite Strategy: INNERMOST 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (3) SlicingProof (LOWER BOUND(ID)) 1098.86/291.81 Sliced the following arguments: 1098.86/291.81 map_f/0 1098.86/291.81 f/0 1098.86/291.81 f/1 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (4) 1098.86/291.81 Obligation: 1098.86/291.81 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1098.86/291.81 1098.86/291.81 1098.86/291.81 The TRS R consists of the following rules: 1098.86/291.81 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(nil) -> nil 1098.86/291.81 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 S is empty. 1098.86/291.81 Rewrite Strategy: INNERMOST 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1098.86/291.81 Infered types. 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (6) 1098.86/291.81 Obligation: 1098.86/291.81 Innermost TRS: 1098.86/291.81 Rules: 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(nil) -> nil 1098.86/291.81 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 Types: 1098.86/291.81 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 0' :: 0':s 1098.86/291.81 nil :: nil:cons:f 1098.86/291.81 s :: 0':s -> 0':s 1098.86/291.81 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 empty :: nil:cons:f -> true:false 1098.86/291.81 true :: true:false 1098.86/291.81 false :: true:false 1098.86/291.81 leq :: 0':s -> 0':s -> true:false 1098.86/291.81 length :: nil:cons:f -> 0':s 1098.86/291.81 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.81 f :: nil:cons:f 1098.86/291.81 head :: nil:cons:f -> nil:cons:f 1098.86/291.81 tail :: nil:cons:f -> nil:cons:f 1098.86/291.81 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.81 hole_0':s2_0 :: 0':s 1098.86/291.81 hole_true:false3_0 :: true:false 1098.86/291.81 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.81 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (7) OrderProof (LOWER BOUND(ID)) 1098.86/291.81 Heuristically decided to analyse the following defined symbols: 1098.86/291.81 fstsplit, sndsplit, leq, length, app, map_f, ring 1098.86/291.81 1098.86/291.81 They will be analysed ascendingly in the following order: 1098.86/291.81 fstsplit < ring 1098.86/291.81 sndsplit < ring 1098.86/291.81 leq < ring 1098.86/291.81 length < ring 1098.86/291.81 app < map_f 1098.86/291.81 app < ring 1098.86/291.81 map_f < ring 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (8) 1098.86/291.81 Obligation: 1098.86/291.81 Innermost TRS: 1098.86/291.81 Rules: 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(nil) -> nil 1098.86/291.81 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 Types: 1098.86/291.81 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 0' :: 0':s 1098.86/291.81 nil :: nil:cons:f 1098.86/291.81 s :: 0':s -> 0':s 1098.86/291.81 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 empty :: nil:cons:f -> true:false 1098.86/291.81 true :: true:false 1098.86/291.81 false :: true:false 1098.86/291.81 leq :: 0':s -> 0':s -> true:false 1098.86/291.81 length :: nil:cons:f -> 0':s 1098.86/291.81 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.81 f :: nil:cons:f 1098.86/291.81 head :: nil:cons:f -> nil:cons:f 1098.86/291.81 tail :: nil:cons:f -> nil:cons:f 1098.86/291.81 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.81 hole_0':s2_0 :: 0':s 1098.86/291.81 hole_true:false3_0 :: true:false 1098.86/291.81 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.81 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.81 1098.86/291.81 1098.86/291.81 Generator Equations: 1098.86/291.81 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.81 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.81 gen_0':s6_0(0) <=> 0' 1098.86/291.81 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.81 1098.86/291.81 1098.86/291.81 The following defined symbols remain to be analysed: 1098.86/291.81 fstsplit, sndsplit, leq, length, app, map_f, ring 1098.86/291.81 1098.86/291.81 They will be analysed ascendingly in the following order: 1098.86/291.81 fstsplit < ring 1098.86/291.81 sndsplit < ring 1098.86/291.81 leq < ring 1098.86/291.81 length < ring 1098.86/291.81 app < map_f 1098.86/291.81 app < ring 1098.86/291.81 map_f < ring 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (9) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.81 Proved the following rewrite lemma: 1098.86/291.81 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.81 1098.86/291.81 Induction Base: 1098.86/291.81 fstsplit(gen_0':s6_0(0), gen_nil:cons:f5_0(0)) ->_R^Omega(1) 1098.86/291.81 nil 1098.86/291.81 1098.86/291.81 Induction Step: 1098.86/291.81 fstsplit(gen_0':s6_0(+(n8_0, 1)), gen_nil:cons:f5_0(+(n8_0, 1))) ->_R^Omega(1) 1098.86/291.81 cons(nil, fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0))) ->_IH 1098.86/291.81 cons(nil, gen_nil:cons:f5_0(c9_0)) 1098.86/291.81 1098.86/291.81 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (10) 1098.86/291.81 Complex Obligation (BEST) 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (11) 1098.86/291.81 Obligation: 1098.86/291.81 Proved the lower bound n^1 for the following obligation: 1098.86/291.81 1098.86/291.81 Innermost TRS: 1098.86/291.81 Rules: 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(nil) -> nil 1098.86/291.81 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 Types: 1098.86/291.81 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 0' :: 0':s 1098.86/291.81 nil :: nil:cons:f 1098.86/291.81 s :: 0':s -> 0':s 1098.86/291.81 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 empty :: nil:cons:f -> true:false 1098.86/291.81 true :: true:false 1098.86/291.81 false :: true:false 1098.86/291.81 leq :: 0':s -> 0':s -> true:false 1098.86/291.81 length :: nil:cons:f -> 0':s 1098.86/291.81 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.81 f :: nil:cons:f 1098.86/291.81 head :: nil:cons:f -> nil:cons:f 1098.86/291.81 tail :: nil:cons:f -> nil:cons:f 1098.86/291.81 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.81 hole_0':s2_0 :: 0':s 1098.86/291.81 hole_true:false3_0 :: true:false 1098.86/291.81 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.81 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.81 1098.86/291.81 1098.86/291.81 Generator Equations: 1098.86/291.81 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.81 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.81 gen_0':s6_0(0) <=> 0' 1098.86/291.81 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.81 1098.86/291.81 1098.86/291.81 The following defined symbols remain to be analysed: 1098.86/291.81 fstsplit, sndsplit, leq, length, app, map_f, ring 1098.86/291.81 1098.86/291.81 They will be analysed ascendingly in the following order: 1098.86/291.81 fstsplit < ring 1098.86/291.81 sndsplit < ring 1098.86/291.81 leq < ring 1098.86/291.81 length < ring 1098.86/291.81 app < map_f 1098.86/291.81 app < ring 1098.86/291.81 map_f < ring 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (12) LowerBoundPropagationProof (FINISHED) 1098.86/291.81 Propagated lower bound. 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (13) 1098.86/291.81 BOUNDS(n^1, INF) 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (14) 1098.86/291.81 Obligation: 1098.86/291.81 Innermost TRS: 1098.86/291.81 Rules: 1098.86/291.81 fstsplit(0', x) -> nil 1098.86/291.81 fstsplit(s(n), nil) -> nil 1098.86/291.81 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.81 sndsplit(0', x) -> x 1098.86/291.81 sndsplit(s(n), nil) -> nil 1098.86/291.81 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.81 empty(nil) -> true 1098.86/291.81 empty(cons(h, t)) -> false 1098.86/291.81 leq(0', m) -> true 1098.86/291.81 leq(s(n), 0') -> false 1098.86/291.81 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.81 length(nil) -> 0' 1098.86/291.81 length(cons(h, t)) -> s(length(t)) 1098.86/291.81 app(nil, x) -> x 1098.86/291.81 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.81 map_f(nil) -> nil 1098.86/291.81 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.81 head(cons(h, t)) -> h 1098.86/291.81 tail(cons(h, t)) -> t 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.81 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.81 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.81 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.81 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.81 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.81 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.81 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.81 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.81 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.81 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.81 1098.86/291.81 Types: 1098.86/291.81 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 0' :: 0':s 1098.86/291.81 nil :: nil:cons:f 1098.86/291.81 s :: 0':s -> 0':s 1098.86/291.81 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.81 empty :: nil:cons:f -> true:false 1098.86/291.81 true :: true:false 1098.86/291.81 false :: true:false 1098.86/291.81 leq :: 0':s -> 0':s -> true:false 1098.86/291.81 length :: nil:cons:f -> 0':s 1098.86/291.81 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.81 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.81 f :: nil:cons:f 1098.86/291.81 head :: nil:cons:f -> nil:cons:f 1098.86/291.81 tail :: nil:cons:f -> nil:cons:f 1098.86/291.81 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.81 hole_0':s2_0 :: 0':s 1098.86/291.81 hole_true:false3_0 :: true:false 1098.86/291.81 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.81 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.81 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.81 1098.86/291.81 1098.86/291.81 Lemmas: 1098.86/291.81 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.81 1098.86/291.81 1098.86/291.81 Generator Equations: 1098.86/291.81 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.81 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.81 gen_0':s6_0(0) <=> 0' 1098.86/291.81 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.81 1098.86/291.81 1098.86/291.81 The following defined symbols remain to be analysed: 1098.86/291.81 sndsplit, leq, length, app, map_f, ring 1098.86/291.81 1098.86/291.81 They will be analysed ascendingly in the following order: 1098.86/291.81 sndsplit < ring 1098.86/291.81 leq < ring 1098.86/291.81 length < ring 1098.86/291.81 app < map_f 1098.86/291.81 app < ring 1098.86/291.81 map_f < ring 1098.86/291.81 1098.86/291.81 ---------------------------------------- 1098.86/291.81 1098.86/291.81 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.81 Proved the following rewrite lemma: 1098.86/291.81 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.81 1098.86/291.81 Induction Base: 1098.86/291.81 sndsplit(gen_0':s6_0(0), gen_nil:cons:f5_0(0)) ->_R^Omega(1) 1098.86/291.81 gen_nil:cons:f5_0(0) 1098.86/291.81 1098.86/291.81 Induction Step: 1098.86/291.81 sndsplit(gen_0':s6_0(+(n692_0, 1)), gen_nil:cons:f5_0(+(n692_0, 1))) ->_R^Omega(1) 1098.86/291.81 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) ->_IH 1098.86/291.81 gen_nil:cons:f5_0(0) 1098.86/291.81 1098.86/291.81 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.81 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (16) 1098.86/291.82 Obligation: 1098.86/291.82 Innermost TRS: 1098.86/291.82 Rules: 1098.86/291.82 fstsplit(0', x) -> nil 1098.86/291.82 fstsplit(s(n), nil) -> nil 1098.86/291.82 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.82 sndsplit(0', x) -> x 1098.86/291.82 sndsplit(s(n), nil) -> nil 1098.86/291.82 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.82 empty(nil) -> true 1098.86/291.82 empty(cons(h, t)) -> false 1098.86/291.82 leq(0', m) -> true 1098.86/291.82 leq(s(n), 0') -> false 1098.86/291.82 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.82 length(nil) -> 0' 1098.86/291.82 length(cons(h, t)) -> s(length(t)) 1098.86/291.82 app(nil, x) -> x 1098.86/291.82 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.82 map_f(nil) -> nil 1098.86/291.82 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.82 head(cons(h, t)) -> h 1098.86/291.82 tail(cons(h, t)) -> t 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.82 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.82 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.82 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.82 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.82 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.82 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.82 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.82 1098.86/291.82 Types: 1098.86/291.82 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 0' :: 0':s 1098.86/291.82 nil :: nil:cons:f 1098.86/291.82 s :: 0':s -> 0':s 1098.86/291.82 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 empty :: nil:cons:f -> true:false 1098.86/291.82 true :: true:false 1098.86/291.82 false :: true:false 1098.86/291.82 leq :: 0':s -> 0':s -> true:false 1098.86/291.82 length :: nil:cons:f -> 0':s 1098.86/291.82 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.82 f :: nil:cons:f 1098.86/291.82 head :: nil:cons:f -> nil:cons:f 1098.86/291.82 tail :: nil:cons:f -> nil:cons:f 1098.86/291.82 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.82 hole_0':s2_0 :: 0':s 1098.86/291.82 hole_true:false3_0 :: true:false 1098.86/291.82 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.82 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.82 1098.86/291.82 1098.86/291.82 Lemmas: 1098.86/291.82 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.82 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.82 1098.86/291.82 1098.86/291.82 Generator Equations: 1098.86/291.82 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.82 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.82 gen_0':s6_0(0) <=> 0' 1098.86/291.82 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.82 1098.86/291.82 1098.86/291.82 The following defined symbols remain to be analysed: 1098.86/291.82 leq, length, app, map_f, ring 1098.86/291.82 1098.86/291.82 They will be analysed ascendingly in the following order: 1098.86/291.82 leq < ring 1098.86/291.82 length < ring 1098.86/291.82 app < map_f 1098.86/291.82 app < ring 1098.86/291.82 map_f < ring 1098.86/291.82 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.82 Proved the following rewrite lemma: 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) -> true, rt in Omega(1 + n1459_0) 1098.86/291.82 1098.86/291.82 Induction Base: 1098.86/291.82 leq(gen_0':s6_0(0), gen_0':s6_0(0)) ->_R^Omega(1) 1098.86/291.82 true 1098.86/291.82 1098.86/291.82 Induction Step: 1098.86/291.82 leq(gen_0':s6_0(+(n1459_0, 1)), gen_0':s6_0(+(n1459_0, 1))) ->_R^Omega(1) 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) ->_IH 1098.86/291.82 true 1098.86/291.82 1098.86/291.82 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (18) 1098.86/291.82 Obligation: 1098.86/291.82 Innermost TRS: 1098.86/291.82 Rules: 1098.86/291.82 fstsplit(0', x) -> nil 1098.86/291.82 fstsplit(s(n), nil) -> nil 1098.86/291.82 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.82 sndsplit(0', x) -> x 1098.86/291.82 sndsplit(s(n), nil) -> nil 1098.86/291.82 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.82 empty(nil) -> true 1098.86/291.82 empty(cons(h, t)) -> false 1098.86/291.82 leq(0', m) -> true 1098.86/291.82 leq(s(n), 0') -> false 1098.86/291.82 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.82 length(nil) -> 0' 1098.86/291.82 length(cons(h, t)) -> s(length(t)) 1098.86/291.82 app(nil, x) -> x 1098.86/291.82 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.82 map_f(nil) -> nil 1098.86/291.82 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.82 head(cons(h, t)) -> h 1098.86/291.82 tail(cons(h, t)) -> t 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.82 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.82 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.82 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.82 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.82 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.82 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.82 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.82 1098.86/291.82 Types: 1098.86/291.82 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 0' :: 0':s 1098.86/291.82 nil :: nil:cons:f 1098.86/291.82 s :: 0':s -> 0':s 1098.86/291.82 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 empty :: nil:cons:f -> true:false 1098.86/291.82 true :: true:false 1098.86/291.82 false :: true:false 1098.86/291.82 leq :: 0':s -> 0':s -> true:false 1098.86/291.82 length :: nil:cons:f -> 0':s 1098.86/291.82 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.82 f :: nil:cons:f 1098.86/291.82 head :: nil:cons:f -> nil:cons:f 1098.86/291.82 tail :: nil:cons:f -> nil:cons:f 1098.86/291.82 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.82 hole_0':s2_0 :: 0':s 1098.86/291.82 hole_true:false3_0 :: true:false 1098.86/291.82 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.82 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.82 1098.86/291.82 1098.86/291.82 Lemmas: 1098.86/291.82 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.82 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) -> true, rt in Omega(1 + n1459_0) 1098.86/291.82 1098.86/291.82 1098.86/291.82 Generator Equations: 1098.86/291.82 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.82 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.82 gen_0':s6_0(0) <=> 0' 1098.86/291.82 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.82 1098.86/291.82 1098.86/291.82 The following defined symbols remain to be analysed: 1098.86/291.82 length, app, map_f, ring 1098.86/291.82 1098.86/291.82 They will be analysed ascendingly in the following order: 1098.86/291.82 length < ring 1098.86/291.82 app < map_f 1098.86/291.82 app < ring 1098.86/291.82 map_f < ring 1098.86/291.82 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.82 Proved the following rewrite lemma: 1098.86/291.82 length(gen_nil:cons:f5_0(n1884_0)) -> gen_0':s6_0(n1884_0), rt in Omega(1 + n1884_0) 1098.86/291.82 1098.86/291.82 Induction Base: 1098.86/291.82 length(gen_nil:cons:f5_0(0)) ->_R^Omega(1) 1098.86/291.82 0' 1098.86/291.82 1098.86/291.82 Induction Step: 1098.86/291.82 length(gen_nil:cons:f5_0(+(n1884_0, 1))) ->_R^Omega(1) 1098.86/291.82 s(length(gen_nil:cons:f5_0(n1884_0))) ->_IH 1098.86/291.82 s(gen_0':s6_0(c1885_0)) 1098.86/291.82 1098.86/291.82 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (20) 1098.86/291.82 Obligation: 1098.86/291.82 Innermost TRS: 1098.86/291.82 Rules: 1098.86/291.82 fstsplit(0', x) -> nil 1098.86/291.82 fstsplit(s(n), nil) -> nil 1098.86/291.82 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.82 sndsplit(0', x) -> x 1098.86/291.82 sndsplit(s(n), nil) -> nil 1098.86/291.82 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.82 empty(nil) -> true 1098.86/291.82 empty(cons(h, t)) -> false 1098.86/291.82 leq(0', m) -> true 1098.86/291.82 leq(s(n), 0') -> false 1098.86/291.82 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.82 length(nil) -> 0' 1098.86/291.82 length(cons(h, t)) -> s(length(t)) 1098.86/291.82 app(nil, x) -> x 1098.86/291.82 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.82 map_f(nil) -> nil 1098.86/291.82 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.82 head(cons(h, t)) -> h 1098.86/291.82 tail(cons(h, t)) -> t 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.82 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.82 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.82 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.82 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.82 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.82 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.82 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.82 1098.86/291.82 Types: 1098.86/291.82 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 0' :: 0':s 1098.86/291.82 nil :: nil:cons:f 1098.86/291.82 s :: 0':s -> 0':s 1098.86/291.82 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 empty :: nil:cons:f -> true:false 1098.86/291.82 true :: true:false 1098.86/291.82 false :: true:false 1098.86/291.82 leq :: 0':s -> 0':s -> true:false 1098.86/291.82 length :: nil:cons:f -> 0':s 1098.86/291.82 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.82 f :: nil:cons:f 1098.86/291.82 head :: nil:cons:f -> nil:cons:f 1098.86/291.82 tail :: nil:cons:f -> nil:cons:f 1098.86/291.82 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.82 hole_0':s2_0 :: 0':s 1098.86/291.82 hole_true:false3_0 :: true:false 1098.86/291.82 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.82 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.82 1098.86/291.82 1098.86/291.82 Lemmas: 1098.86/291.82 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.82 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) -> true, rt in Omega(1 + n1459_0) 1098.86/291.82 length(gen_nil:cons:f5_0(n1884_0)) -> gen_0':s6_0(n1884_0), rt in Omega(1 + n1884_0) 1098.86/291.82 1098.86/291.82 1098.86/291.82 Generator Equations: 1098.86/291.82 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.82 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.82 gen_0':s6_0(0) <=> 0' 1098.86/291.82 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.82 1098.86/291.82 1098.86/291.82 The following defined symbols remain to be analysed: 1098.86/291.82 app, map_f, ring 1098.86/291.82 1098.86/291.82 They will be analysed ascendingly in the following order: 1098.86/291.82 app < map_f 1098.86/291.82 app < ring 1098.86/291.82 map_f < ring 1098.86/291.82 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.82 Proved the following rewrite lemma: 1098.86/291.82 app(gen_nil:cons:f5_0(n2280_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2280_0, b)), rt in Omega(1 + n2280_0) 1098.86/291.82 1098.86/291.82 Induction Base: 1098.86/291.82 app(gen_nil:cons:f5_0(0), gen_nil:cons:f5_0(b)) ->_R^Omega(1) 1098.86/291.82 gen_nil:cons:f5_0(b) 1098.86/291.82 1098.86/291.82 Induction Step: 1098.86/291.82 app(gen_nil:cons:f5_0(+(n2280_0, 1)), gen_nil:cons:f5_0(b)) ->_R^Omega(1) 1098.86/291.82 cons(nil, app(gen_nil:cons:f5_0(n2280_0), gen_nil:cons:f5_0(b))) ->_IH 1098.86/291.82 cons(nil, gen_nil:cons:f5_0(+(b, c2281_0))) 1098.86/291.82 1098.86/291.82 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (22) 1098.86/291.82 Obligation: 1098.86/291.82 Innermost TRS: 1098.86/291.82 Rules: 1098.86/291.82 fstsplit(0', x) -> nil 1098.86/291.82 fstsplit(s(n), nil) -> nil 1098.86/291.82 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.82 sndsplit(0', x) -> x 1098.86/291.82 sndsplit(s(n), nil) -> nil 1098.86/291.82 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.82 empty(nil) -> true 1098.86/291.82 empty(cons(h, t)) -> false 1098.86/291.82 leq(0', m) -> true 1098.86/291.82 leq(s(n), 0') -> false 1098.86/291.82 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.82 length(nil) -> 0' 1098.86/291.82 length(cons(h, t)) -> s(length(t)) 1098.86/291.82 app(nil, x) -> x 1098.86/291.82 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.82 map_f(nil) -> nil 1098.86/291.82 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.82 head(cons(h, t)) -> h 1098.86/291.82 tail(cons(h, t)) -> t 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.82 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.82 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.82 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.82 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.82 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.82 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.82 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.82 1098.86/291.82 Types: 1098.86/291.82 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 0' :: 0':s 1098.86/291.82 nil :: nil:cons:f 1098.86/291.82 s :: 0':s -> 0':s 1098.86/291.82 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 empty :: nil:cons:f -> true:false 1098.86/291.82 true :: true:false 1098.86/291.82 false :: true:false 1098.86/291.82 leq :: 0':s -> 0':s -> true:false 1098.86/291.82 length :: nil:cons:f -> 0':s 1098.86/291.82 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.82 f :: nil:cons:f 1098.86/291.82 head :: nil:cons:f -> nil:cons:f 1098.86/291.82 tail :: nil:cons:f -> nil:cons:f 1098.86/291.82 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.82 hole_0':s2_0 :: 0':s 1098.86/291.82 hole_true:false3_0 :: true:false 1098.86/291.82 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.82 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.82 1098.86/291.82 1098.86/291.82 Lemmas: 1098.86/291.82 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.82 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) -> true, rt in Omega(1 + n1459_0) 1098.86/291.82 length(gen_nil:cons:f5_0(n1884_0)) -> gen_0':s6_0(n1884_0), rt in Omega(1 + n1884_0) 1098.86/291.82 app(gen_nil:cons:f5_0(n2280_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2280_0, b)), rt in Omega(1 + n2280_0) 1098.86/291.82 1098.86/291.82 1098.86/291.82 Generator Equations: 1098.86/291.82 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.82 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.82 gen_0':s6_0(0) <=> 0' 1098.86/291.82 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.82 1098.86/291.82 1098.86/291.82 The following defined symbols remain to be analysed: 1098.86/291.82 map_f, ring 1098.86/291.82 1098.86/291.82 They will be analysed ascendingly in the following order: 1098.86/291.82 map_f < ring 1098.86/291.82 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1098.86/291.82 Proved the following rewrite lemma: 1098.86/291.82 map_f(gen_nil:cons:f5_0(+(1, n3525_0))) -> *7_0, rt in Omega(n3525_0) 1098.86/291.82 1098.86/291.82 Induction Base: 1098.86/291.82 map_f(gen_nil:cons:f5_0(+(1, 0))) 1098.86/291.82 1098.86/291.82 Induction Step: 1098.86/291.82 map_f(gen_nil:cons:f5_0(+(1, +(n3525_0, 1)))) ->_R^Omega(1) 1098.86/291.82 app(f, map_f(gen_nil:cons:f5_0(+(1, n3525_0)))) ->_IH 1098.86/291.82 app(f, *7_0) 1098.86/291.82 1098.86/291.82 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1098.86/291.82 ---------------------------------------- 1098.86/291.82 1098.86/291.82 (24) 1098.86/291.82 Obligation: 1098.86/291.82 Innermost TRS: 1098.86/291.82 Rules: 1098.86/291.82 fstsplit(0', x) -> nil 1098.86/291.82 fstsplit(s(n), nil) -> nil 1098.86/291.82 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1098.86/291.82 sndsplit(0', x) -> x 1098.86/291.82 sndsplit(s(n), nil) -> nil 1098.86/291.82 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1098.86/291.82 empty(nil) -> true 1098.86/291.82 empty(cons(h, t)) -> false 1098.86/291.82 leq(0', m) -> true 1098.86/291.82 leq(s(n), 0') -> false 1098.86/291.82 leq(s(n), s(m)) -> leq(n, m) 1098.86/291.82 length(nil) -> 0' 1098.86/291.82 length(cons(h, t)) -> s(length(t)) 1098.86/291.82 app(nil, x) -> x 1098.86/291.82 app(cons(h, t), x) -> cons(h, app(t, x)) 1098.86/291.82 map_f(nil) -> nil 1098.86/291.82 map_f(cons(h, t)) -> app(f, map_f(t)) 1098.86/291.82 head(cons(h, t)) -> h 1098.86/291.82 tail(cons(h, t)) -> t 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1))) 1098.86/291.82 if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2))) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2))) 1098.86/291.82 if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m) 1098.86/291.82 if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2)))) 1098.86/291.82 if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2)))) 1098.86/291.82 if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3))) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3))) 1098.86/291.82 if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m) 1098.86/291.82 if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3)))) 1098.86/291.82 if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m) 1098.86/291.82 ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3)))) 1098.86/291.82 if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m) 1098.86/291.82 1098.86/291.82 Types: 1098.86/291.82 fstsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 0' :: 0':s 1098.86/291.82 nil :: nil:cons:f 1098.86/291.82 s :: 0':s -> 0':s 1098.86/291.82 cons :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 sndsplit :: 0':s -> nil:cons:f -> nil:cons:f 1098.86/291.82 empty :: nil:cons:f -> true:false 1098.86/291.82 true :: true:false 1098.86/291.82 false :: true:false 1098.86/291.82 leq :: 0':s -> 0':s -> true:false 1098.86/291.82 length :: nil:cons:f -> 0':s 1098.86/291.82 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1098.86/291.82 map_f :: nil:cons:f -> nil:cons:f 1098.86/291.82 f :: nil:cons:f 1098.86/291.82 head :: nil:cons:f -> nil:cons:f 1098.86/291.82 tail :: nil:cons:f -> nil:cons:f 1098.86/291.82 ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 hole_nil:cons:f1_0 :: nil:cons:f 1098.86/291.82 hole_0':s2_0 :: 0':s 1098.86/291.82 hole_true:false3_0 :: true:false 1098.86/291.82 hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9 1098.86/291.82 gen_nil:cons:f5_0 :: Nat -> nil:cons:f 1098.86/291.82 gen_0':s6_0 :: Nat -> 0':s 1098.86/291.82 1098.86/291.82 1098.86/291.82 Lemmas: 1098.86/291.82 fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0) 1098.86/291.82 sndsplit(gen_0':s6_0(n692_0), gen_nil:cons:f5_0(n692_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n692_0) 1098.86/291.82 leq(gen_0':s6_0(n1459_0), gen_0':s6_0(n1459_0)) -> true, rt in Omega(1 + n1459_0) 1098.86/291.82 length(gen_nil:cons:f5_0(n1884_0)) -> gen_0':s6_0(n1884_0), rt in Omega(1 + n1884_0) 1098.86/291.82 app(gen_nil:cons:f5_0(n2280_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2280_0, b)), rt in Omega(1 + n2280_0) 1098.86/291.82 map_f(gen_nil:cons:f5_0(+(1, n3525_0))) -> *7_0, rt in Omega(n3525_0) 1098.86/291.82 1098.86/291.82 1098.86/291.82 Generator Equations: 1098.86/291.82 gen_nil:cons:f5_0(0) <=> nil 1098.86/291.82 gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x)) 1098.86/291.82 gen_0':s6_0(0) <=> 0' 1098.86/291.82 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1098.86/291.82 1098.86/291.82 1098.86/291.82 The following defined symbols remain to be analysed: 1098.86/291.82 ring 1098.86/291.89 EOF