1149.55/291.99 WORST_CASE(Omega(n^1), O(n^2)) 1149.55/292.01 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1149.55/292.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1149.55/292.01 1149.55/292.01 1149.55/292.01 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.55/292.01 1149.55/292.01 (0) CpxTRS 1149.55/292.01 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 1 ms] 1149.55/292.01 (2) CpxWeightedTrs 1149.55/292.01 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1149.55/292.01 (4) CpxTypedWeightedTrs 1149.55/292.01 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1149.55/292.01 (6) CpxTypedWeightedCompleteTrs 1149.55/292.01 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 2 ms] 1149.55/292.01 (8) CpxRNTS 1149.55/292.01 (9) CompleteCoflocoProof [FINISHED, 1283 ms] 1149.55/292.01 (10) BOUNDS(1, n^2) 1149.55/292.01 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1149.55/292.01 (12) TRS for Loop Detection 1149.55/292.01 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1149.55/292.01 (14) BEST 1149.55/292.01 (15) proven lower bound 1149.55/292.01 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1149.55/292.01 (17) BOUNDS(n^1, INF) 1149.55/292.01 (18) TRS for Loop Detection 1149.55/292.01 1149.55/292.01 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (0) 1149.55/292.01 Obligation: 1149.55/292.01 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.55/292.01 1149.55/292.01 1149.55/292.01 The TRS R consists of the following rules: 1149.55/292.01 1149.55/292.01 fstsplit(0, x) -> nil 1149.55/292.01 fstsplit(s(n), nil) -> nil 1149.55/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1149.55/292.01 sndsplit(0, x) -> x 1149.55/292.01 sndsplit(s(n), nil) -> nil 1149.55/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1149.55/292.01 empty(nil) -> true 1149.55/292.01 empty(cons(h, t)) -> false 1149.55/292.01 leq(0, m) -> true 1149.55/292.01 leq(s(n), 0) -> false 1149.55/292.01 leq(s(n), s(m)) -> leq(n, m) 1149.55/292.01 length(nil) -> 0 1149.55/292.01 length(cons(h, t)) -> s(length(t)) 1149.55/292.01 app(nil, x) -> x 1149.55/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) 1149.55/292.01 map_f(pid, nil) -> nil 1149.55/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1149.55/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) 1149.55/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) 1149.55/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) 1149.55/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) 1149.55/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) 1149.55/292.01 1149.55/292.01 S is empty. 1149.55/292.01 Rewrite Strategy: INNERMOST 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1149.55/292.01 Transformed relative TRS to weighted TRS 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (2) 1149.55/292.01 Obligation: 1149.55/292.01 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1149.55/292.01 1149.55/292.01 1149.55/292.01 The TRS R consists of the following rules: 1149.55/292.01 1149.55/292.01 fstsplit(0, x) -> nil [1] 1149.55/292.01 fstsplit(s(n), nil) -> nil [1] 1149.55/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) [1] 1149.55/292.01 sndsplit(0, x) -> x [1] 1149.55/292.01 sndsplit(s(n), nil) -> nil [1] 1149.55/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) [1] 1149.55/292.01 empty(nil) -> true [1] 1149.55/292.01 empty(cons(h, t)) -> false [1] 1149.55/292.01 leq(0, m) -> true [1] 1149.55/292.01 leq(s(n), 0) -> false [1] 1149.55/292.01 leq(s(n), s(m)) -> leq(n, m) [1] 1149.55/292.01 length(nil) -> 0 [1] 1149.55/292.01 length(cons(h, t)) -> s(length(t)) [1] 1149.55/292.01 app(nil, x) -> x [1] 1149.55/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) [1] 1149.55/292.01 map_f(pid, nil) -> nil [1] 1149.55/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) [1] 1149.55/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) [1] 1149.55/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) [1] 1149.55/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) [1] 1149.55/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) [1] 1149.55/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) [1] 1149.55/292.01 1149.55/292.01 Rewrite Strategy: INNERMOST 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1149.55/292.01 Infered types. 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (4) 1149.55/292.01 Obligation: 1149.55/292.01 Runtime Complexity Weighted TRS with Types. 1149.55/292.01 The TRS R consists of the following rules: 1149.55/292.01 1149.55/292.01 fstsplit(0, x) -> nil [1] 1149.55/292.01 fstsplit(s(n), nil) -> nil [1] 1149.55/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) [1] 1149.55/292.01 sndsplit(0, x) -> x [1] 1149.55/292.01 sndsplit(s(n), nil) -> nil [1] 1149.55/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) [1] 1149.55/292.01 empty(nil) -> true [1] 1149.55/292.01 empty(cons(h, t)) -> false [1] 1149.55/292.01 leq(0, m) -> true [1] 1149.55/292.01 leq(s(n), 0) -> false [1] 1149.55/292.01 leq(s(n), s(m)) -> leq(n, m) [1] 1149.55/292.01 length(nil) -> 0 [1] 1149.55/292.01 length(cons(h, t)) -> s(length(t)) [1] 1149.55/292.01 app(nil, x) -> x [1] 1149.55/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) [1] 1149.55/292.01 map_f(pid, nil) -> nil [1] 1149.55/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) [1] 1149.55/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) [1] 1149.55/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) [1] 1149.55/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) [1] 1149.55/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) [1] 1149.55/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) [1] 1149.55/292.01 1149.55/292.01 The TRS has the following type information: 1149.55/292.01 fstsplit :: 0:s -> nil:cons:f -> nil:cons:f 1149.55/292.01 0 :: 0:s 1149.55/292.01 nil :: nil:cons:f 1149.55/292.01 s :: 0:s -> 0:s 1149.55/292.01 cons :: a -> nil:cons:f -> nil:cons:f 1149.55/292.01 sndsplit :: 0:s -> nil:cons:f -> nil:cons:f 1149.55/292.01 empty :: nil:cons:f -> true:false 1149.55/292.01 true :: true:false 1149.55/292.01 false :: true:false 1149.55/292.01 leq :: 0:s -> 0:s -> true:false 1149.55/292.01 length :: nil:cons:f -> 0:s 1149.55/292.01 app :: nil:cons:f -> nil:cons:f -> nil:cons:f 1149.55/292.01 map_f :: self -> nil:cons:f -> nil:cons:f 1149.55/292.01 f :: self -> a -> nil:cons:f 1149.55/292.01 process :: nil:cons:f -> 0:s -> process:if1:if2:if3 1149.55/292.01 if1 :: nil:cons:f -> 0:s -> true:false -> process:if1:if2:if3 1149.55/292.01 if2 :: nil:cons:f -> 0:s -> true:false -> process:if1:if2:if3 1149.55/292.01 if3 :: nil:cons:f -> 0:s -> true:false -> process:if1:if2:if3 1149.55/292.01 self :: self 1149.55/292.01 1149.55/292.01 Rewrite Strategy: INNERMOST 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (5) CompletionProof (UPPER BOUND(ID)) 1149.55/292.01 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1149.55/292.01 1149.55/292.01 fstsplit(v0, v1) -> null_fstsplit [0] 1149.55/292.01 sndsplit(v0, v1) -> null_sndsplit [0] 1149.55/292.01 empty(v0) -> null_empty [0] 1149.55/292.01 length(v0) -> null_length [0] 1149.55/292.01 app(v0, v1) -> null_app [0] 1149.55/292.01 map_f(v0, v1) -> null_map_f [0] 1149.55/292.01 if2(v0, v1, v2) -> null_if2 [0] 1149.55/292.01 if3(v0, v1, v2) -> null_if3 [0] 1149.55/292.01 leq(v0, v1) -> null_leq [0] 1149.55/292.01 if1(v0, v1, v2) -> null_if1 [0] 1149.55/292.01 1149.55/292.01 And the following fresh constants: null_fstsplit, null_sndsplit, null_empty, null_length, null_app, null_map_f, null_if2, null_if3, null_leq, null_if1, const 1149.55/292.01 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (6) 1149.55/292.01 Obligation: 1149.55/292.01 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1149.55/292.01 1149.55/292.01 Runtime Complexity Weighted TRS with Types. 1149.55/292.01 The TRS R consists of the following rules: 1149.55/292.01 1149.55/292.01 fstsplit(0, x) -> nil [1] 1149.55/292.01 fstsplit(s(n), nil) -> nil [1] 1149.55/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) [1] 1149.55/292.01 sndsplit(0, x) -> x [1] 1149.55/292.01 sndsplit(s(n), nil) -> nil [1] 1149.55/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) [1] 1149.55/292.01 empty(nil) -> true [1] 1149.55/292.01 empty(cons(h, t)) -> false [1] 1149.55/292.01 leq(0, m) -> true [1] 1149.55/292.01 leq(s(n), 0) -> false [1] 1149.55/292.01 leq(s(n), s(m)) -> leq(n, m) [1] 1149.55/292.01 length(nil) -> 0 [1] 1149.55/292.01 length(cons(h, t)) -> s(length(t)) [1] 1149.55/292.01 app(nil, x) -> x [1] 1149.55/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) [1] 1149.55/292.01 map_f(pid, nil) -> nil [1] 1149.55/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) [1] 1149.55/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) [1] 1149.55/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) [1] 1149.55/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) [1] 1149.55/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) [1] 1149.55/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) [1] 1149.55/292.01 fstsplit(v0, v1) -> null_fstsplit [0] 1149.55/292.01 sndsplit(v0, v1) -> null_sndsplit [0] 1149.55/292.01 empty(v0) -> null_empty [0] 1149.55/292.01 length(v0) -> null_length [0] 1149.55/292.01 app(v0, v1) -> null_app [0] 1149.55/292.01 map_f(v0, v1) -> null_map_f [0] 1149.55/292.01 if2(v0, v1, v2) -> null_if2 [0] 1149.55/292.01 if3(v0, v1, v2) -> null_if3 [0] 1149.55/292.01 leq(v0, v1) -> null_leq [0] 1149.55/292.01 if1(v0, v1, v2) -> null_if1 [0] 1149.55/292.01 1149.55/292.01 The TRS has the following type information: 1149.55/292.01 fstsplit :: 0:s:null_length -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 0 :: 0:s:null_length 1149.55/292.01 nil :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 s :: 0:s:null_length -> 0:s:null_length 1149.55/292.01 cons :: a -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 sndsplit :: 0:s:null_length -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 empty :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> true:false:null_empty:null_leq 1149.55/292.01 true :: true:false:null_empty:null_leq 1149.55/292.01 false :: true:false:null_empty:null_leq 1149.55/292.01 leq :: 0:s:null_length -> 0:s:null_length -> true:false:null_empty:null_leq 1149.55/292.01 length :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> 0:s:null_length 1149.55/292.01 app :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 map_f :: self -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 f :: self -> a -> nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 process :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> 0:s:null_length -> null_if2:null_if3:null_if1 1149.55/292.01 if1 :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> 0:s:null_length -> true:false:null_empty:null_leq -> null_if2:null_if3:null_if1 1149.55/292.01 if2 :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> 0:s:null_length -> true:false:null_empty:null_leq -> null_if2:null_if3:null_if1 1149.55/292.01 if3 :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f -> 0:s:null_length -> true:false:null_empty:null_leq -> null_if2:null_if3:null_if1 1149.55/292.01 self :: self 1149.55/292.01 null_fstsplit :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 null_sndsplit :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 null_empty :: true:false:null_empty:null_leq 1149.55/292.01 null_length :: 0:s:null_length 1149.55/292.01 null_app :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 null_map_f :: nil:cons:f:null_fstsplit:null_sndsplit:null_app:null_map_f 1149.55/292.01 null_if2 :: null_if2:null_if3:null_if1 1149.55/292.01 null_if3 :: null_if2:null_if3:null_if1 1149.55/292.01 null_leq :: true:false:null_empty:null_leq 1149.55/292.01 null_if1 :: null_if2:null_if3:null_if1 1149.55/292.01 const :: a 1149.55/292.01 1149.55/292.01 Rewrite Strategy: INNERMOST 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1149.55/292.01 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1149.55/292.01 The constant constructors are abstracted as follows: 1149.55/292.01 1149.55/292.01 0 => 0 1149.55/292.01 nil => 0 1149.55/292.01 true => 2 1149.55/292.01 false => 1 1149.55/292.01 self => 0 1149.55/292.01 null_fstsplit => 0 1149.55/292.01 null_sndsplit => 0 1149.55/292.01 null_empty => 0 1149.55/292.01 null_length => 0 1149.55/292.01 null_app => 0 1149.55/292.01 null_map_f => 0 1149.55/292.01 null_if2 => 0 1149.55/292.01 null_if3 => 0 1149.55/292.01 null_leq => 0 1149.55/292.01 null_if1 => 0 1149.55/292.01 const => 0 1149.55/292.01 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (8) 1149.55/292.01 Obligation: 1149.55/292.01 Complexity RNTS consisting of the following rules: 1149.55/292.01 1149.55/292.01 app(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 1149.55/292.01 app(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1149.55/292.01 app(z, z') -{ 1 }-> 1 + h + app(t, x) :|: z = 1 + h + t, z' = x, x >= 0, h >= 0, t >= 0 1149.55/292.01 empty(z) -{ 1 }-> 2 :|: z = 0 1149.55/292.01 empty(z) -{ 1 }-> 1 :|: z = 1 + h + t, h >= 0, t >= 0 1149.55/292.01 empty(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1149.55/292.01 fstsplit(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = 0 1149.55/292.01 fstsplit(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0 1149.55/292.01 fstsplit(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1149.55/292.01 fstsplit(z, z') -{ 1 }-> 1 + h + fstsplit(n, t) :|: z' = 1 + h + t, n >= 0, h >= 0, t >= 0, z = 1 + n 1149.55/292.01 if1(z, z', z'') -{ 1 }-> if3(store, m, empty(fstsplit(m, app(map_f(0, 0), store)))) :|: z = store, z' = m, store >= 0, z'' = 1, m >= 0 1149.55/292.01 if1(z, z', z'') -{ 1 }-> if2(store, m, empty(fstsplit(m, store))) :|: z = store, z' = m, z'' = 2, store >= 0, m >= 0 1149.55/292.01 if1(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1149.55/292.01 if2(z, z', z'') -{ 1 }-> process(app(map_f(0, 0), sndsplit(m, store)), m) :|: z = store, z' = m, store >= 0, z'' = 1, m >= 0 1149.55/292.01 if2(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1149.55/292.01 if3(z, z', z'') -{ 1 }-> process(sndsplit(m, app(map_f(0, 0), store)), m) :|: z = store, z' = m, store >= 0, z'' = 1, m >= 0 1149.55/292.01 if3(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1149.55/292.01 length(z) -{ 1 }-> 0 :|: z = 0 1149.55/292.01 length(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1149.55/292.01 length(z) -{ 1 }-> 1 + length(t) :|: z = 1 + h + t, h >= 0, t >= 0 1149.55/292.01 leq(z, z') -{ 1 }-> leq(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0 1149.55/292.01 leq(z, z') -{ 1 }-> 2 :|: z' = m, z = 0, m >= 0 1149.55/292.01 leq(z, z') -{ 1 }-> 1 :|: n >= 0, z = 1 + n, z' = 0 1149.55/292.01 leq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1149.55/292.01 map_f(z, z') -{ 1 }-> app(1 + pid + h, map_f(pid, t)) :|: z' = 1 + h + t, z = pid, h >= 0, t >= 0, pid >= 0 1149.55/292.01 map_f(z, z') -{ 1 }-> 0 :|: z = pid, pid >= 0, z' = 0 1149.55/292.01 map_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1149.55/292.01 process(z, z') -{ 1 }-> if1(store, m, leq(m, length(store))) :|: z = store, z' = m, store >= 0, m >= 0 1149.55/292.01 sndsplit(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 1149.55/292.01 sndsplit(z, z') -{ 1 }-> sndsplit(n, t) :|: z' = 1 + h + t, n >= 0, h >= 0, t >= 0, z = 1 + n 1149.55/292.01 sndsplit(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0 1149.55/292.01 sndsplit(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1149.55/292.01 1149.55/292.01 Only complete derivations are relevant for the runtime complexity. 1149.55/292.01 1149.55/292.01 ---------------------------------------- 1149.55/292.01 1149.55/292.01 (9) CompleteCoflocoProof (FINISHED) 1149.55/292.01 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1149.55/292.01 1149.55/292.01 eq(start(V1, V, V31),0,[fstsplit(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[sndsplit(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[empty(V1, Out)],[V1 >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[leq(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[length(V1, Out)],[V1 >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[app(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[process(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[if1(V1, V, V31, Out)],[V1 >= 0,V >= 0,V31 >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[if2(V1, V, V31, Out)],[V1 >= 0,V >= 0,V31 >= 0]). 1149.55/292.01 eq(start(V1, V, V31),0,[if3(V1, V, V31, Out)],[V1 >= 0,V >= 0,V31 >= 0]). 1149.55/292.01 eq(fstsplit(V1, V, Out),1,[],[Out = 0,V = V2,V2 >= 0,V1 = 0]). 1149.55/292.01 eq(fstsplit(V1, V, Out),1,[],[Out = 0,V3 >= 0,V1 = 1 + V3,V = 0]). 1149.55/292.01 eq(fstsplit(V1, V, Out),1,[fstsplit(V5, V4, Ret1)],[Out = 1 + Ret1 + V6,V = 1 + V4 + V6,V5 >= 0,V6 >= 0,V4 >= 0,V1 = 1 + V5]). 1149.55/292.01 eq(sndsplit(V1, V, Out),1,[],[Out = V7,V = V7,V7 >= 0,V1 = 0]). 1149.55/292.01 eq(sndsplit(V1, V, Out),1,[],[Out = 0,V8 >= 0,V1 = 1 + V8,V = 0]). 1149.55/292.01 eq(sndsplit(V1, V, Out),1,[sndsplit(V11, V10, Ret)],[Out = Ret,V = 1 + V10 + V9,V11 >= 0,V9 >= 0,V10 >= 0,V1 = 1 + V11]). 1149.55/292.01 eq(empty(V1, Out),1,[],[Out = 2,V1 = 0]). 1149.55/292.01 eq(empty(V1, Out),1,[],[Out = 1,V1 = 1 + V12 + V13,V12 >= 0,V13 >= 0]). 1149.55/292.01 eq(leq(V1, V, Out),1,[],[Out = 2,V = V14,V1 = 0,V14 >= 0]). 1149.55/292.01 eq(leq(V1, V, Out),1,[],[Out = 1,V15 >= 0,V1 = 1 + V15,V = 0]). 1149.55/292.01 eq(leq(V1, V, Out),1,[leq(V17, V16, Ret2)],[Out = Ret2,V17 >= 0,V = 1 + V16,V1 = 1 + V17,V16 >= 0]). 1149.55/292.01 eq(length(V1, Out),1,[],[Out = 0,V1 = 0]). 1149.55/292.01 eq(length(V1, Out),1,[length(V19, Ret11)],[Out = 1 + Ret11,V1 = 1 + V18 + V19,V18 >= 0,V19 >= 0]). 1149.55/292.01 eq(app(V1, V, Out),1,[],[Out = V20,V = V20,V20 >= 0,V1 = 0]). 1149.55/292.01 eq(app(V1, V, Out),1,[app(V23, V21, Ret12)],[Out = 1 + Ret12 + V22,V1 = 1 + V22 + V23,V = V21,V21 >= 0,V22 >= 0,V23 >= 0]). 1149.55/292.01 eq(fun(V1, V, Out),1,[],[Out = 0,V1 = V24,V24 >= 0,V = 0]). 1149.55/292.01 eq(fun(V1, V, Out),1,[fun(V27, V26, Ret13),app(1 + V27 + V25, Ret13, Ret3)],[Out = Ret3,V = 1 + V25 + V26,V1 = V27,V25 >= 0,V26 >= 0,V27 >= 0]). 1149.55/292.01 eq(process(V1, V, Out),1,[length(V28, Ret21),leq(V29, Ret21, Ret22),if1(V28, V29, Ret22, Ret4)],[Out = Ret4,V1 = V28,V = V29,V28 >= 0,V29 >= 0]). 1149.55/292.01 eq(if1(V1, V, V31, Out),1,[fstsplit(V32, V30, Ret20),empty(Ret20, Ret23),if2(V30, V32, Ret23, Ret5)],[Out = Ret5,V1 = V30,V = V32,V31 = 2,V30 >= 0,V32 >= 0]). 1149.55/292.01 eq(if1(V1, V, V31, Out),1,[fun(0, 0, Ret2010),app(Ret2010, V34, Ret201),fstsplit(V33, Ret201, Ret202),empty(Ret202, Ret24),if3(V34, V33, Ret24, Ret6)],[Out = Ret6,V1 = V34,V = V33,V34 >= 0,V31 = 1,V33 >= 0]). 1149.55/292.01 eq(if2(V1, V, V31, Out),1,[fun(0, 0, Ret00),sndsplit(V35, V36, Ret01),app(Ret00, Ret01, Ret0),process(Ret0, V35, Ret7)],[Out = Ret7,V1 = V36,V = V35,V36 >= 0,V31 = 1,V35 >= 0]). 1149.55/292.01 eq(if3(V1, V, V31, Out),1,[fun(0, 0, Ret010),app(Ret010, V38, Ret011),sndsplit(V37, Ret011, Ret02),process(Ret02, V37, Ret8)],[Out = Ret8,V1 = V38,V = V37,V38 >= 0,V31 = 1,V37 >= 0]). 1149.55/292.01 eq(fstsplit(V1, V, Out),0,[],[Out = 0,V40 >= 0,V39 >= 0,V1 = V40,V = V39]). 1149.55/292.01 eq(sndsplit(V1, V, Out),0,[],[Out = 0,V42 >= 0,V41 >= 0,V1 = V42,V = V41]). 1149.55/292.01 eq(empty(V1, Out),0,[],[Out = 0,V43 >= 0,V1 = V43]). 1149.55/292.01 eq(length(V1, Out),0,[],[Out = 0,V44 >= 0,V1 = V44]). 1149.55/292.01 eq(app(V1, V, Out),0,[],[Out = 0,V45 >= 0,V46 >= 0,V1 = V45,V = V46]). 1149.55/292.01 eq(fun(V1, V, Out),0,[],[Out = 0,V47 >= 0,V48 >= 0,V1 = V47,V = V48]). 1149.55/292.01 eq(if2(V1, V, V31, Out),0,[],[Out = 0,V50 >= 0,V31 = V51,V49 >= 0,V1 = V50,V = V49,V51 >= 0]). 1149.55/292.01 eq(if3(V1, V, V31, Out),0,[],[Out = 0,V52 >= 0,V31 = V54,V53 >= 0,V1 = V52,V = V53,V54 >= 0]). 1149.55/292.01 eq(leq(V1, V, Out),0,[],[Out = 0,V55 >= 0,V56 >= 0,V1 = V55,V = V56]). 1149.55/292.01 eq(if1(V1, V, V31, Out),0,[],[Out = 0,V57 >= 0,V31 = V59,V58 >= 0,V1 = V57,V = V58,V59 >= 0]). 1149.55/292.01 input_output_vars(fstsplit(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(sndsplit(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(empty(V1,Out),[V1],[Out]). 1149.55/292.01 input_output_vars(leq(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(length(V1,Out),[V1],[Out]). 1149.55/292.01 input_output_vars(app(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(fun(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(process(V1,V,Out),[V1,V],[Out]). 1149.55/292.01 input_output_vars(if1(V1,V,V31,Out),[V1,V,V31],[Out]). 1149.55/292.01 input_output_vars(if2(V1,V,V31,Out),[V1,V,V31],[Out]). 1149.55/292.01 input_output_vars(if3(V1,V,V31,Out),[V1,V,V31],[Out]). 1149.55/292.01 1149.55/292.01 1149.55/292.01 CoFloCo proof output: 1149.55/292.01 Preprocessing Cost Relations 1149.55/292.01 ===================================== 1149.55/292.01 1149.55/292.01 #### Computed strongly connected components 1149.55/292.01 0. recursive : [app/3] 1149.55/292.01 1. non_recursive : [empty/2] 1149.55/292.01 2. recursive : [fstsplit/3] 1149.55/292.01 3. recursive [non_tail] : [fun/3] 1149.55/292.01 4. recursive : [length/2] 1149.55/292.01 5. recursive : [leq/3] 1149.55/292.01 6. recursive : [sndsplit/3] 1149.55/292.01 7. recursive : [if1/4,if2/4,if3/4,process/3] 1149.55/292.01 8. non_recursive : [start/3] 1149.55/292.01 1149.55/292.01 #### Obtained direct recursion through partial evaluation 1149.55/292.01 0. SCC is partially evaluated into app/3 1149.90/292.01 1. SCC is partially evaluated into empty/2 1149.90/292.01 2. SCC is partially evaluated into fstsplit/3 1149.90/292.01 3. SCC is partially evaluated into fun/3 1149.90/292.01 4. SCC is partially evaluated into length/2 1149.90/292.01 5. SCC is partially evaluated into leq/3 1149.90/292.01 6. SCC is partially evaluated into sndsplit/3 1149.90/292.01 7. SCC is partially evaluated into process/3 1149.90/292.01 8. SCC is partially evaluated into start/3 1149.90/292.01 1149.90/292.01 Control-Flow Refinement of Cost Relations 1149.90/292.01 ===================================== 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations app/3 1149.90/292.01 * CE 21 is refined into CE [45] 1149.90/292.01 * CE 19 is refined into CE [46] 1149.90/292.01 * CE 20 is refined into CE [47] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of app/3 1149.90/292.01 * CEs [47] --> Loop 25 1149.90/292.01 * CEs [45] --> Loop 26 1149.90/292.01 * CEs [46] --> Loop 27 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR app(V1,V,Out) 1149.90/292.01 * RF of phase [25]: [V1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR app(V1,V,Out) 1149.90/292.01 * Partial RF of phase [25]: 1149.90/292.01 - RF of loop [25:1]: 1149.90/292.01 V1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations empty/2 1149.90/292.01 * CE 27 is refined into CE [48] 1149.90/292.01 * CE 28 is refined into CE [49] 1149.90/292.01 * CE 26 is refined into CE [50] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of empty/2 1149.90/292.01 * CEs [48] --> Loop 28 1149.90/292.01 * CEs [49] --> Loop 29 1149.90/292.01 * CEs [50] --> Loop 30 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR empty(V1,Out) 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR empty(V1,Out) 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations fstsplit/3 1149.90/292.01 * CE 23 is refined into CE [51] 1149.90/292.01 * CE 22 is refined into CE [52] 1149.90/292.01 * CE 25 is refined into CE [53] 1149.90/292.01 * CE 24 is refined into CE [54] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of fstsplit/3 1149.90/292.01 * CEs [54] --> Loop 31 1149.90/292.01 * CEs [51] --> Loop 32 1149.90/292.01 * CEs [52,53] --> Loop 33 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR fstsplit(V1,V,Out) 1149.90/292.01 * RF of phase [31]: [V,V1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR fstsplit(V1,V,Out) 1149.90/292.01 * Partial RF of phase [31]: 1149.90/292.01 - RF of loop [31:1]: 1149.90/292.01 V 1149.90/292.01 V1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations fun/3 1149.90/292.01 * CE 16 is refined into CE [55] 1149.90/292.01 * CE 18 is refined into CE [56] 1149.90/292.01 * CE 17 is refined into CE [57,58,59] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of fun/3 1149.90/292.01 * CEs [58] --> Loop 34 1149.90/292.01 * CEs [59] --> Loop 35 1149.90/292.01 * CEs [57] --> Loop 36 1149.90/292.01 * CEs [55,56] --> Loop 37 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR fun(V1,V,Out) 1149.90/292.01 * RF of phase [34,35,36]: [V] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR fun(V1,V,Out) 1149.90/292.01 * Partial RF of phase [34,35,36]: 1149.90/292.01 - RF of loop [34:1,35:1,36:1]: 1149.90/292.01 V 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations length/2 1149.90/292.01 * CE 42 is refined into CE [60] 1149.90/292.01 * CE 44 is refined into CE [61] 1149.90/292.01 * CE 43 is refined into CE [62] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of length/2 1149.90/292.01 * CEs [62] --> Loop 38 1149.90/292.01 * CEs [60,61] --> Loop 39 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR length(V1,Out) 1149.90/292.01 * RF of phase [38]: [V1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR length(V1,Out) 1149.90/292.01 * Partial RF of phase [38]: 1149.90/292.01 - RF of loop [38:1]: 1149.90/292.01 V1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations leq/3 1149.90/292.01 * CE 41 is refined into CE [63] 1149.90/292.01 * CE 39 is refined into CE [64] 1149.90/292.01 * CE 38 is refined into CE [65] 1149.90/292.01 * CE 40 is refined into CE [66] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of leq/3 1149.90/292.01 * CEs [66] --> Loop 40 1149.90/292.01 * CEs [63] --> Loop 41 1149.90/292.01 * CEs [64] --> Loop 42 1149.90/292.01 * CEs [65] --> Loop 43 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR leq(V1,V,Out) 1149.90/292.01 * RF of phase [40]: [V,V1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR leq(V1,V,Out) 1149.90/292.01 * Partial RF of phase [40]: 1149.90/292.01 - RF of loop [40:1]: 1149.90/292.01 V 1149.90/292.01 V1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations sndsplit/3 1149.90/292.01 * CE 30 is refined into CE [67] 1149.90/292.01 * CE 32 is refined into CE [68] 1149.90/292.01 * CE 29 is refined into CE [69] 1149.90/292.01 * CE 31 is refined into CE [70] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of sndsplit/3 1149.90/292.01 * CEs [70] --> Loop 44 1149.90/292.01 * CEs [67,68] --> Loop 45 1149.90/292.01 * CEs [69] --> Loop 46 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR sndsplit(V1,V,Out) 1149.90/292.01 * RF of phase [44]: [V,V1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR sndsplit(V1,V,Out) 1149.90/292.01 * Partial RF of phase [44]: 1149.90/292.01 - RF of loop [44:1]: 1149.90/292.01 V 1149.90/292.01 V1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations process/3 1149.90/292.01 * CE 33 is refined into CE [71,72,73,74,75,76,77] 1149.90/292.01 * CE 35 is refined into CE [78,79,80,81,82,83,84,85,86,87,88,89] 1149.90/292.01 * CE 37 is refined into CE [90,91,92,93,94,95,96,97] 1149.90/292.01 * CE 34 is refined into CE [98,99,100,101,102,103] 1149.90/292.01 * CE 36 is refined into CE [104,105,106,107] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of process/3 1149.90/292.01 * CEs [99,102,106] --> Loop 47 1149.90/292.01 * CEs [98,100,101,103,104,105,107] --> Loop 48 1149.90/292.01 * CEs [71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97] --> Loop 49 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR process(V1,V,Out) 1149.90/292.01 * RF of phase [47]: [V1,V1-V+1] 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR process(V1,V,Out) 1149.90/292.01 * Partial RF of phase [47]: 1149.90/292.01 - RF of loop [47:1]: 1149.90/292.01 V1 1149.90/292.01 V1-V+1 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Specialization of cost equations start/3 1149.90/292.01 * CE 4 is refined into CE [108,109,110,111] 1149.90/292.01 * CE 5 is refined into CE [112,113,114,115] 1149.90/292.01 * CE 1 is refined into CE [116] 1149.90/292.01 * CE 2 is refined into CE [117,118,119] 1149.90/292.01 * CE 3 is refined into CE [120,121,122,123,124,125] 1149.90/292.01 * CE 6 is refined into CE [126,127,128,129,130,131] 1149.90/292.01 * CE 7 is refined into CE [132,133,134,135,136] 1149.90/292.01 * CE 8 is refined into CE [137,138] 1149.90/292.01 * CE 9 is refined into CE [139,140,141] 1149.90/292.01 * CE 10 is refined into CE [142,143,144] 1149.90/292.01 * CE 11 is refined into CE [145,146,147,148,149] 1149.90/292.01 * CE 12 is refined into CE [150,151] 1149.90/292.01 * CE 13 is refined into CE [152,153,154,155] 1149.90/292.01 * CE 14 is refined into CE [156,157] 1149.90/292.01 * CE 15 is refined into CE [158] 1149.90/292.01 1149.90/292.01 1149.90/292.01 ### Cost equations --> "Loop" of start/3 1149.90/292.01 * CEs [108,109,110,111,112,113,114,115] --> Loop 50 1149.90/292.01 * CEs [146] --> Loop 51 1149.90/292.01 * CEs [117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136] --> Loop 52 1149.90/292.01 * CEs [116,137,138,139,140,141,142,143,144,145,147,148,149,150,151,152,153,154,155,156,157,158] --> Loop 53 1149.90/292.01 1149.90/292.01 ### Ranking functions of CR start(V1,V,V31) 1149.90/292.01 1149.90/292.01 #### Partial ranking functions of CR start(V1,V,V31) 1149.90/292.01 1149.90/292.01 1149.90/292.01 Computing Bounds 1149.90/292.01 ===================================== 1149.90/292.01 1149.90/292.01 #### Cost of chains of app(V1,V,Out): 1149.90/292.01 * Chain [[25],27]: 1*it(25)+1 1149.90/292.01 Such that:it(25) =< -V+Out 1149.90/292.01 1149.90/292.01 with precondition: [V+V1=Out,V1>=1,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [[25],26]: 1*it(25)+0 1149.90/292.01 Such that:it(25) =< Out 1149.90/292.01 1149.90/292.01 with precondition: [V>=0,Out>=1,V1>=Out] 1149.90/292.01 1149.90/292.01 * Chain [27]: 1 1149.90/292.01 with precondition: [V1=0,V=Out,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [26]: 0 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of empty(V1,Out): 1149.90/292.01 * Chain [30]: 1 1149.90/292.01 with precondition: [V1=0,Out=2] 1149.90/292.01 1149.90/292.01 * Chain [29]: 0 1149.90/292.01 with precondition: [Out=0,V1>=0] 1149.90/292.01 1149.90/292.01 * Chain [28]: 1 1149.90/292.01 with precondition: [Out=1,V1>=1] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of fstsplit(V1,V,Out): 1149.90/292.01 * Chain [[31],33]: 1*it(31)+1 1149.90/292.01 Such that:it(31) =< V1 1149.90/292.01 1149.90/292.01 with precondition: [V1>=1,Out>=1,V>=Out] 1149.90/292.01 1149.90/292.01 * Chain [[31],32]: 1*it(31)+1 1149.90/292.01 Such that:it(31) =< V1 1149.90/292.01 1149.90/292.01 with precondition: [V=Out,V1>=2,V>=1] 1149.90/292.01 1149.90/292.01 * Chain [33]: 1 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [32]: 1 1149.90/292.01 with precondition: [V=0,Out=0,V1>=1] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of fun(V1,V,Out): 1149.90/292.01 * Chain [[34,35,36],37]: 4*it(34)+1*s(7)+1*s(8)+1 1149.90/292.01 Such that:aux(2) =< V1+V 1149.90/292.01 aux(6) =< V 1149.90/292.01 it(34) =< aux(6) 1149.90/292.01 aux(3) =< aux(2) 1149.90/292.01 s(7) =< it(34)*aux(2) 1149.90/292.01 s(8) =< it(34)*aux(3) 1149.90/292.01 1149.90/292.01 with precondition: [V1>=0,V>=1,Out>=0] 1149.90/292.01 1149.90/292.01 * Chain [37]: 1 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of length(V1,Out): 1149.90/292.01 * Chain [[38],39]: 1*it(38)+1 1149.90/292.01 Such that:it(38) =< V1 1149.90/292.01 1149.90/292.01 with precondition: [Out>=1,V1>=Out] 1149.90/292.01 1149.90/292.01 * Chain [39]: 1 1149.90/292.01 with precondition: [Out=0,V1>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of leq(V1,V,Out): 1149.90/292.01 * Chain [[40],43]: 1*it(40)+1 1149.90/292.01 Such that:it(40) =< V1 1149.90/292.01 1149.90/292.01 with precondition: [Out=2,V1>=1,V>=V1] 1149.90/292.01 1149.90/292.01 * Chain [[40],42]: 1*it(40)+1 1149.90/292.01 Such that:it(40) =< V 1149.90/292.01 1149.90/292.01 with precondition: [Out=1,V>=1,V1>=V+1] 1149.90/292.01 1149.90/292.01 * Chain [[40],41]: 1*it(40)+0 1149.90/292.01 Such that:it(40) =< V 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V1>=1,V>=1] 1149.90/292.01 1149.90/292.01 * Chain [43]: 1 1149.90/292.01 with precondition: [V1=0,Out=2,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [42]: 1 1149.90/292.01 with precondition: [V=0,Out=1,V1>=1] 1149.90/292.01 1149.90/292.01 * Chain [41]: 0 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of sndsplit(V1,V,Out): 1149.90/292.01 * Chain [[44],46]: 1*it(44)+1 1149.90/292.01 Such that:it(44) =< V1 1149.90/292.01 1149.90/292.01 with precondition: [V1>=1,Out>=0,V>=Out+V1] 1149.90/292.01 1149.90/292.01 * Chain [[44],45]: 1*it(44)+1 1149.90/292.01 Such that:it(44) =< V 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V1>=1,V>=1] 1149.90/292.01 1149.90/292.01 * Chain [46]: 1 1149.90/292.01 with precondition: [V1=0,V=Out,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [45]: 1 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of process(V1,V,Out): 1149.90/292.01 * Chain [[47],49]: 45*it(47)+19*s(18)+2*s(71)+8 1149.90/292.01 Such that:aux(18) =< V 1149.90/292.01 aux(27) =< V1 1149.90/292.01 it(47) =< aux(27) 1149.90/292.01 s(18) =< aux(18) 1149.90/292.01 s(73) =< it(47)*aux(27) 1149.90/292.01 s(71) =< s(73) 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V>=1,V1>=V] 1149.90/292.01 1149.90/292.01 * Chain [[47],48,49]: 34*it(47)+37*s(18)+2*s(71)+20 1149.90/292.01 Such that:aux(37) =< V 1149.90/292.01 aux(38) =< V1 1149.90/292.01 it(47) =< aux(38) 1149.90/292.01 s(18) =< aux(37) 1149.90/292.01 s(73) =< it(47)*aux(38) 1149.90/292.01 s(71) =< s(73) 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V>=1,V1>=V+1] 1149.90/292.01 1149.90/292.01 * Chain [49]: 22*s(12)+19*s(18)+8 1149.90/292.01 Such that:aux(17) =< V1 1149.90/292.01 aux(18) =< V 1149.90/292.01 s(12) =< aux(17) 1149.90/292.01 s(18) =< aux(18) 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [48,49]: 37*s(18)+11*s(76)+20 1149.90/292.01 Such that:aux(35) =< V1 1149.90/292.01 aux(37) =< V 1149.90/292.01 s(18) =< aux(37) 1149.90/292.01 s(76) =< aux(35) 1149.90/292.01 1149.90/292.01 with precondition: [Out=0,V1>=1,V>=1] 1149.90/292.01 1149.90/292.01 1149.90/292.01 #### Cost of chains of start(V1,V,V31): 1149.90/292.01 * Chain [53]: 119*s(126)+119*s(127)+1*s(139)+1*s(140)+4*s(146)+20 1149.90/292.01 Such that:s(135) =< V1+V 1149.90/292.01 aux(41) =< V1 1149.90/292.01 aux(42) =< V 1149.90/292.01 s(126) =< aux(41) 1149.90/292.01 s(127) =< aux(42) 1149.90/292.01 s(145) =< s(126)*aux(41) 1149.90/292.01 s(146) =< s(145) 1149.90/292.01 s(138) =< s(135) 1149.90/292.01 s(139) =< s(127)*s(135) 1149.90/292.01 s(140) =< s(127)*s(138) 1149.90/292.01 1149.90/292.01 with precondition: [V1>=0] 1149.90/292.01 1149.90/292.01 * Chain [52]: 1134*s(148)+228*s(149)+336*s(162)+12*s(164)+8*s(183)+29 1149.90/292.01 Such that:aux(53) =< V1 1149.90/292.01 aux(54) =< V1-V 1149.90/292.01 aux(55) =< V 1149.90/292.01 s(149) =< aux(53) 1149.90/292.01 s(148) =< aux(55) 1149.90/292.01 s(182) =< s(149)*aux(53) 1149.90/292.01 s(183) =< s(182) 1149.90/292.01 s(162) =< aux(54) 1149.90/292.01 s(163) =< s(162)*aux(54) 1149.90/292.01 s(164) =< s(163) 1149.90/292.01 1149.90/292.01 with precondition: [V31=1,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 * Chain [51]: 1 1149.90/292.01 with precondition: [V=0,V1>=1] 1149.90/292.01 1149.90/292.01 * Chain [50]: 462*s(252)+2*s(253)+112*s(275)+4*s(277)+27 1149.90/292.01 Such that:s(272) =< V1-V 1149.90/292.01 aux(60) =< V1 1149.90/292.01 aux(61) =< V 1149.90/292.01 s(253) =< aux(60) 1149.90/292.01 s(252) =< aux(61) 1149.90/292.01 s(275) =< s(272) 1149.90/292.01 s(276) =< s(275)*s(272) 1149.90/292.01 s(277) =< s(276) 1149.90/292.01 1149.90/292.01 with precondition: [V31=2,V1>=0,V>=0] 1149.90/292.01 1149.90/292.01 1149.90/292.01 Closed-form bounds of start(V1,V,V31): 1149.90/292.01 ------------------------------------- 1149.90/292.01 * Chain [53] with precondition: [V1>=0] 1149.90/292.01 - Upper bound: 119*V1+20+4*V1*V1+nat(V)*119+nat(V)*2*nat(V1+V) 1149.90/292.01 - Complexity: n^2 1149.90/292.01 * Chain [52] with precondition: [V31=1,V1>=0,V>=0] 1149.90/292.01 - Upper bound: 228*V1+29+8*V1*V1+1134*V+nat(V1-V)*336+nat(V1-V)*12*nat(V1-V) 1149.90/292.01 - Complexity: n^2 1149.90/292.01 * Chain [51] with precondition: [V=0,V1>=1] 1149.90/292.01 - Upper bound: 1 1149.90/292.01 - Complexity: constant 1149.90/292.01 * Chain [50] with precondition: [V31=2,V1>=0,V>=0] 1149.90/292.01 - Upper bound: 2*V1+462*V+27+nat(V1-V)*112+nat(V1-V)*4*nat(V1-V) 1149.90/292.01 - Complexity: n^2 1149.90/292.01 1149.90/292.01 ### Maximum cost of start(V1,V,V31): 2*V1+19+nat(V)*119+max([4*V1*V1+117*V1+max([nat(V)*2*nat(V1+V),109*V1+9+4*V1*V1+nat(V)*1015+nat(V1-V)*336+nat(V1-V)*12*nat(V1-V)]),nat(V)*343+7+nat(V1-V)*112+nat(V1-V)*4*nat(V1-V)])+1 1149.90/292.01 Asymptotic class: n^2 1149.90/292.01 * Total analysis performed in 1103 ms. 1149.90/292.01 1149.90/292.01 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (10) 1149.90/292.01 BOUNDS(1, n^2) 1149.90/292.01 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1149.90/292.01 Transformed a relative TRS into a decreasing-loop problem. 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (12) 1149.90/292.01 Obligation: 1149.90/292.01 Analyzing the following TRS for decreasing loops: 1149.90/292.01 1149.90/292.01 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.90/292.01 1149.90/292.01 1149.90/292.01 The TRS R consists of the following rules: 1149.90/292.01 1149.90/292.01 fstsplit(0, x) -> nil 1149.90/292.01 fstsplit(s(n), nil) -> nil 1149.90/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1149.90/292.01 sndsplit(0, x) -> x 1149.90/292.01 sndsplit(s(n), nil) -> nil 1149.90/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1149.90/292.01 empty(nil) -> true 1149.90/292.01 empty(cons(h, t)) -> false 1149.90/292.01 leq(0, m) -> true 1149.90/292.01 leq(s(n), 0) -> false 1149.90/292.01 leq(s(n), s(m)) -> leq(n, m) 1149.90/292.01 length(nil) -> 0 1149.90/292.01 length(cons(h, t)) -> s(length(t)) 1149.90/292.01 app(nil, x) -> x 1149.90/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) 1149.90/292.01 map_f(pid, nil) -> nil 1149.90/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1149.90/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) 1149.90/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) 1149.90/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) 1149.90/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) 1149.90/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) 1149.90/292.01 1149.90/292.01 S is empty. 1149.90/292.01 Rewrite Strategy: INNERMOST 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (13) DecreasingLoopProof (LOWER BOUND(ID)) 1149.90/292.01 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1149.90/292.01 1149.90/292.01 The rewrite sequence 1149.90/292.01 1149.90/292.01 map_f(pid, cons(h, t)) ->^+ app(f(pid, h), map_f(pid, t)) 1149.90/292.01 1149.90/292.01 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 1149.90/292.01 1149.90/292.01 The pumping substitution is [t / cons(h, t)]. 1149.90/292.01 1149.90/292.01 The result substitution is [ ]. 1149.90/292.01 1149.90/292.01 1149.90/292.01 1149.90/292.01 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (14) 1149.90/292.01 Complex Obligation (BEST) 1149.90/292.01 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (15) 1149.90/292.01 Obligation: 1149.90/292.01 Proved the lower bound n^1 for the following obligation: 1149.90/292.01 1149.90/292.01 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.90/292.01 1149.90/292.01 1149.90/292.01 The TRS R consists of the following rules: 1149.90/292.01 1149.90/292.01 fstsplit(0, x) -> nil 1149.90/292.01 fstsplit(s(n), nil) -> nil 1149.90/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1149.90/292.01 sndsplit(0, x) -> x 1149.90/292.01 sndsplit(s(n), nil) -> nil 1149.90/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1149.90/292.01 empty(nil) -> true 1149.90/292.01 empty(cons(h, t)) -> false 1149.90/292.01 leq(0, m) -> true 1149.90/292.01 leq(s(n), 0) -> false 1149.90/292.01 leq(s(n), s(m)) -> leq(n, m) 1149.90/292.01 length(nil) -> 0 1149.90/292.01 length(cons(h, t)) -> s(length(t)) 1149.90/292.01 app(nil, x) -> x 1149.90/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) 1149.90/292.01 map_f(pid, nil) -> nil 1149.90/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1149.90/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) 1149.90/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) 1149.90/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) 1149.90/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) 1149.90/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) 1149.90/292.01 1149.90/292.01 S is empty. 1149.90/292.01 Rewrite Strategy: INNERMOST 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (16) LowerBoundPropagationProof (FINISHED) 1149.90/292.01 Propagated lower bound. 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (17) 1149.90/292.01 BOUNDS(n^1, INF) 1149.90/292.01 1149.90/292.01 ---------------------------------------- 1149.90/292.01 1149.90/292.01 (18) 1149.90/292.01 Obligation: 1149.90/292.01 Analyzing the following TRS for decreasing loops: 1149.90/292.01 1149.90/292.01 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.90/292.01 1149.90/292.01 1149.90/292.01 The TRS R consists of the following rules: 1149.90/292.01 1149.90/292.01 fstsplit(0, x) -> nil 1149.90/292.01 fstsplit(s(n), nil) -> nil 1149.90/292.01 fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) 1149.90/292.01 sndsplit(0, x) -> x 1149.90/292.01 sndsplit(s(n), nil) -> nil 1149.90/292.01 sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) 1149.90/292.01 empty(nil) -> true 1149.90/292.01 empty(cons(h, t)) -> false 1149.90/292.01 leq(0, m) -> true 1149.90/292.01 leq(s(n), 0) -> false 1149.90/292.01 leq(s(n), s(m)) -> leq(n, m) 1149.90/292.01 length(nil) -> 0 1149.90/292.01 length(cons(h, t)) -> s(length(t)) 1149.90/292.01 app(nil, x) -> x 1149.90/292.01 app(cons(h, t), x) -> cons(h, app(t, x)) 1149.90/292.01 map_f(pid, nil) -> nil 1149.90/292.01 map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) 1149.90/292.01 process(store, m) -> if1(store, m, leq(m, length(store))) 1149.90/292.01 if1(store, m, true) -> if2(store, m, empty(fstsplit(m, store))) 1149.90/292.01 if1(store, m, false) -> if3(store, m, empty(fstsplit(m, app(map_f(self, nil), store)))) 1149.90/292.01 if2(store, m, false) -> process(app(map_f(self, nil), sndsplit(m, store)), m) 1149.90/292.01 if3(store, m, false) -> process(sndsplit(m, app(map_f(self, nil), store)), m) 1149.90/292.01 1149.90/292.01 S is empty. 1149.90/292.01 Rewrite Strategy: INNERMOST 1150.03/292.09 EOF