306.16/291.48 WORST_CASE(Omega(n^2), ?) 306.16/291.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 306.16/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 306.16/291.49 306.16/291.49 306.16/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 306.16/291.49 306.16/291.49 (0) CpxTRS 306.16/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 306.16/291.49 (2) CpxTRS 306.16/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 306.16/291.49 (4) typed CpxTrs 306.16/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 306.16/291.49 (6) typed CpxTrs 306.16/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 292 ms] 306.16/291.49 (8) BEST 306.16/291.49 (9) proven lower bound 306.16/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 306.16/291.49 (11) BOUNDS(n^1, INF) 306.16/291.49 (12) typed CpxTrs 306.16/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 105 ms] 306.16/291.49 (14) typed CpxTrs 306.16/291.49 (15) RewriteLemmaProof [LOWER BOUND(ID), 34 ms] 306.16/291.49 (16) typed CpxTrs 306.16/291.49 (17) RewriteLemmaProof [LOWER BOUND(ID), 7 ms] 306.16/291.49 (18) typed CpxTrs 306.16/291.49 (19) RewriteLemmaProof [LOWER BOUND(ID), 537 ms] 306.16/291.49 (20) BEST 306.16/291.49 (21) proven lower bound 306.16/291.49 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 306.16/291.49 (23) BOUNDS(n^2, INF) 306.16/291.49 (24) typed CpxTrs 306.16/291.49 (25) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 306.16/291.49 (26) typed CpxTrs 306.16/291.49 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (0) 306.16/291.49 Obligation: 306.16/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 306.16/291.49 306.16/291.49 306.16/291.49 The TRS R consists of the following rules: 306.16/291.49 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0))), k(n(s(x), s(y)), s(s(0))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0, y) -> 0 306.16/291.49 n(x, 0) -> 0 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0, y) -> y 306.16/291.49 m(x, 0) -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0, s(y)) -> 0 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0, y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0) -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0) -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0) -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0) -> true 306.16/291.49 gt(0, y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 S is empty. 306.16/291.49 Rewrite Strategy: FULL 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 306.16/291.49 Renamed function symbols to avoid clashes with predefined symbol. 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (2) 306.16/291.49 Obligation: 306.16/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 306.16/291.49 306.16/291.49 306.16/291.49 The TRS R consists of the following rules: 306.16/291.49 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 S is empty. 306.16/291.49 Rewrite Strategy: FULL 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 306.16/291.49 Infered types. 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (4) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (5) OrderProof (LOWER BOUND(ID)) 306.16/291.49 Heuristically decided to analyse the following defined symbols: 306.16/291.49 g, f, k, minus, m, n, p, gt, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 k < g 306.16/291.49 minus < g 306.16/291.49 m < g 306.16/291.49 n < g 306.16/291.49 f = h 306.16/291.49 minus < k 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (6) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 minus, g, f, k, m, n, p, gt, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 k < g 306.16/291.49 minus < g 306.16/291.49 m < g 306.16/291.49 n < g 306.16/291.49 f = h 306.16/291.49 minus < k 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 minus(gen_s:0':true:false2_0(0), gen_s:0':true:false2_0(0)) ->_R^Omega(1) 306.16/291.49 gen_s:0':true:false2_0(0) 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 minus(gen_s:0':true:false2_0(+(n4_0, 1)), gen_s:0':true:false2_0(+(n4_0, 1))) ->_R^Omega(1) 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) ->_IH 306.16/291.49 gen_s:0':true:false2_0(0) 306.16/291.49 306.16/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (8) 306.16/291.49 Complex Obligation (BEST) 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (9) 306.16/291.49 Obligation: 306.16/291.49 Proved the lower bound n^1 for the following obligation: 306.16/291.49 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 minus, g, f, k, m, n, p, gt, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 k < g 306.16/291.49 minus < g 306.16/291.49 m < g 306.16/291.49 n < g 306.16/291.49 f = h 306.16/291.49 minus < k 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (10) LowerBoundPropagationProof (FINISHED) 306.16/291.49 Propagated lower bound. 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (11) 306.16/291.49 BOUNDS(n^1, INF) 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (12) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 k, g, f, m, n, p, gt, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 k < g 306.16/291.49 m < g 306.16/291.49 n < g 306.16/291.49 f = h 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (13) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 m(gen_s:0':true:false2_0(0), gen_s:0':true:false2_0(0)) ->_R^Omega(1) 306.16/291.49 gen_s:0':true:false2_0(0) 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 m(gen_s:0':true:false2_0(+(n472_0, 1)), gen_s:0':true:false2_0(+(n472_0, 1))) ->_R^Omega(1) 306.16/291.49 s(m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0))) ->_IH 306.16/291.49 s(gen_s:0':true:false2_0(c473_0)) 306.16/291.49 306.16/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (14) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 n, g, f, p, gt, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 n < g 306.16/291.49 f = h 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (15) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 n(gen_s:0':true:false2_0(0), gen_s:0':true:false2_0(0)) ->_R^Omega(1) 306.16/291.49 0' 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 n(gen_s:0':true:false2_0(+(n1010_0, 1)), gen_s:0':true:false2_0(+(n1010_0, 1))) ->_R^Omega(1) 306.16/291.49 s(n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0))) ->_IH 306.16/291.49 s(gen_s:0':true:false2_0(c1011_0)) 306.16/291.49 306.16/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (16) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 gt, g, f, p, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 f = h 306.16/291.49 gt < p 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (17) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) -> true, rt in Omega(1 + n1446_0) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, 0)), gen_s:0':true:false2_0(0)) ->_R^Omega(1) 306.16/291.49 true 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, +(n1446_0, 1))), gen_s:0':true:false2_0(+(n1446_0, 1))) ->_R^Omega(1) 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) ->_IH 306.16/291.49 true 306.16/291.49 306.16/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (18) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) -> true, rt in Omega(1 + n1446_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 p, g, f, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 f = h 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (19) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 p(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))) -> *3_0, rt in Omega(n1825_0 + n1825_0^2) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 p(gen_s:0':true:false2_0(+(2, 0)), gen_s:0':true:false2_0(+(1, 0))) 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 p(gen_s:0':true:false2_0(+(2, +(n1825_0, 1))), gen_s:0':true:false2_0(+(1, +(n1825_0, 1)))) ->_R^Omega(1) 306.16/291.49 s(s(p(if(gt(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))), gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))), if(not(gt(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0)))), id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_L^Omega(2 + n1825_0) 306.16/291.49 s(s(p(if(true, gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))), if(not(gt(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0)))), id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(not(gt(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0)))), id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_L^Omega(2 + n1825_0) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(not(true), id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(if(true, false, true), id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(false, id(gen_s:0':true:false2_0(+(2, n1825_0))), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(false, gen_s:0':true:false2_0(+(2, n1825_0)), id(gen_s:0':true:false2_0(+(1, n1825_0))))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), if(false, gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0)))))) ->_R^Omega(1) 306.16/291.49 s(s(p(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))))) ->_IH 306.16/291.49 s(s(*3_0)) 306.16/291.49 306.16/291.49 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (20) 306.16/291.49 Complex Obligation (BEST) 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (21) 306.16/291.49 Obligation: 306.16/291.49 Proved the lower bound n^2 for the following obligation: 306.16/291.49 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) -> true, rt in Omega(1 + n1446_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 p, g, f, h 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 f = h 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (22) LowerBoundPropagationProof (FINISHED) 306.16/291.49 Propagated lower bound. 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (23) 306.16/291.49 BOUNDS(n^2, INF) 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (24) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) -> true, rt in Omega(1 + n1446_0) 306.16/291.49 p(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))) -> *3_0, rt in Omega(n1825_0 + n1825_0^2) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 h, g, f 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 f = h 306.16/291.49 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (25) RewriteLemmaProof (LOWER BOUND(ID)) 306.16/291.49 Proved the following rewrite lemma: 306.16/291.49 h(gen_s:0':true:false2_0(*(2, n11616_0))) -> false, rt in Omega(1 + n11616_0) 306.16/291.49 306.16/291.49 Induction Base: 306.16/291.49 h(gen_s:0':true:false2_0(*(2, 0))) ->_R^Omega(1) 306.16/291.49 false 306.16/291.49 306.16/291.49 Induction Step: 306.16/291.49 h(gen_s:0':true:false2_0(*(2, +(n11616_0, 1)))) ->_R^Omega(1) 306.16/291.49 f(gen_s:0':true:false2_0(+(1, *(2, n11616_0)))) ->_R^Omega(1) 306.16/291.49 h(gen_s:0':true:false2_0(*(2, n11616_0))) ->_IH 306.16/291.49 false 306.16/291.49 306.16/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 306.16/291.49 ---------------------------------------- 306.16/291.49 306.16/291.49 (26) 306.16/291.49 Obligation: 306.16/291.49 TRS: 306.16/291.49 Rules: 306.16/291.49 g(s(x), s(y)) -> if(and(f(s(x)), f(s(y))), t(g(k(minus(m(x, y), n(x, y)), s(s(0'))), k(n(s(x), s(y)), s(s(0'))))), g(minus(m(x, y), n(x, y)), n(s(x), s(y)))) 306.16/291.49 n(0', y) -> 0' 306.16/291.49 n(x, 0') -> 0' 306.16/291.49 n(s(x), s(y)) -> s(n(x, y)) 306.16/291.49 m(0', y) -> y 306.16/291.49 m(x, 0') -> x 306.16/291.49 m(s(x), s(y)) -> s(m(x, y)) 306.16/291.49 k(0', s(y)) -> 0' 306.16/291.49 k(s(x), s(y)) -> s(k(minus(x, y), s(y))) 306.16/291.49 t(x) -> p(x, x) 306.16/291.49 p(s(x), s(y)) -> s(s(p(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 306.16/291.49 p(s(x), x) -> p(if(gt(x, x), id(x), id(x)), s(x)) 306.16/291.49 p(0', y) -> y 306.16/291.49 p(id(x), s(y)) -> s(p(x, if(gt(s(y), y), y, s(y)))) 306.16/291.49 minus(x, 0') -> x 306.16/291.49 minus(s(x), s(y)) -> minus(x, y) 306.16/291.49 id(x) -> x 306.16/291.49 if(true, x, y) -> x 306.16/291.49 if(false, x, y) -> y 306.16/291.49 not(x) -> if(x, false, true) 306.16/291.49 and(x, false) -> false 306.16/291.49 and(true, true) -> true 306.16/291.49 f(0') -> true 306.16/291.49 f(s(x)) -> h(x) 306.16/291.49 h(0') -> false 306.16/291.49 h(s(x)) -> f(x) 306.16/291.49 gt(s(x), 0') -> true 306.16/291.49 gt(0', y) -> false 306.16/291.49 gt(s(x), s(y)) -> gt(x, y) 306.16/291.49 306.16/291.49 Types: 306.16/291.49 g :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 s :: s:0':true:false -> s:0':true:false 306.16/291.49 if :: s:0':true:false -> s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 and :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 f :: s:0':true:false -> s:0':true:false 306.16/291.49 t :: s:0':true:false -> s:0':true:false 306.16/291.49 k :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 minus :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 m :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 n :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 0' :: s:0':true:false 306.16/291.49 p :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 gt :: s:0':true:false -> s:0':true:false -> s:0':true:false 306.16/291.49 not :: s:0':true:false -> s:0':true:false 306.16/291.49 id :: s:0':true:false -> s:0':true:false 306.16/291.49 true :: s:0':true:false 306.16/291.49 false :: s:0':true:false 306.16/291.49 h :: s:0':true:false -> s:0':true:false 306.16/291.49 hole_s:0':true:false1_0 :: s:0':true:false 306.16/291.49 gen_s:0':true:false2_0 :: Nat -> s:0':true:false 306.16/291.49 306.16/291.49 306.16/291.49 Lemmas: 306.16/291.49 minus(gen_s:0':true:false2_0(n4_0), gen_s:0':true:false2_0(n4_0)) -> gen_s:0':true:false2_0(0), rt in Omega(1 + n4_0) 306.16/291.49 m(gen_s:0':true:false2_0(n472_0), gen_s:0':true:false2_0(n472_0)) -> gen_s:0':true:false2_0(n472_0), rt in Omega(1 + n472_0) 306.16/291.49 n(gen_s:0':true:false2_0(n1010_0), gen_s:0':true:false2_0(n1010_0)) -> gen_s:0':true:false2_0(n1010_0), rt in Omega(1 + n1010_0) 306.16/291.49 gt(gen_s:0':true:false2_0(+(1, n1446_0)), gen_s:0':true:false2_0(n1446_0)) -> true, rt in Omega(1 + n1446_0) 306.16/291.49 p(gen_s:0':true:false2_0(+(2, n1825_0)), gen_s:0':true:false2_0(+(1, n1825_0))) -> *3_0, rt in Omega(n1825_0 + n1825_0^2) 306.16/291.49 h(gen_s:0':true:false2_0(*(2, n11616_0))) -> false, rt in Omega(1 + n11616_0) 306.16/291.49 306.16/291.49 306.16/291.49 Generator Equations: 306.16/291.49 gen_s:0':true:false2_0(0) <=> 0' 306.16/291.49 gen_s:0':true:false2_0(+(x, 1)) <=> s(gen_s:0':true:false2_0(x)) 306.16/291.49 306.16/291.49 306.16/291.49 The following defined symbols remain to be analysed: 306.16/291.49 f, g 306.16/291.49 306.16/291.49 They will be analysed ascendingly in the following order: 306.16/291.49 f < g 306.16/291.49 f = h 306.16/291.52 EOF