1137.27/291.54 WORST_CASE(Omega(n^1), ?) 1137.68/291.58 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1137.68/291.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1137.68/291.58 1137.68/291.58 1137.68/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.68/291.58 1137.68/291.58 (0) CpxTRS 1137.68/291.58 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1137.68/291.58 (2) CpxTRS 1137.68/291.58 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1137.68/291.58 (4) typed CpxTrs 1137.68/291.58 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1137.68/291.58 (6) typed CpxTrs 1137.68/291.58 (7) RewriteLemmaProof [LOWER BOUND(ID), 528 ms] 1137.68/291.58 (8) BEST 1137.68/291.58 (9) proven lower bound 1137.68/291.58 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1137.68/291.58 (11) BOUNDS(n^1, INF) 1137.68/291.58 (12) typed CpxTrs 1137.68/291.58 1137.68/291.58 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (0) 1137.68/291.58 Obligation: 1137.68/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.68/291.58 1137.68/291.58 1137.68/291.58 The TRS R consists of the following rules: 1137.68/291.58 1137.68/291.58 a__fact(X) -> a__if(a__zero(mark(X)), s(0), prod(X, fact(p(X)))) 1137.68/291.58 a__add(0, X) -> mark(X) 1137.68/291.58 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.58 a__prod(0, X) -> 0 1137.68/291.58 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.58 a__if(true, X, Y) -> mark(X) 1137.68/291.58 a__if(false, X, Y) -> mark(Y) 1137.68/291.58 a__zero(0) -> true 1137.68/291.58 a__zero(s(X)) -> false 1137.68/291.58 a__p(s(X)) -> mark(X) 1137.68/291.58 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.58 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.58 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.58 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.58 mark(p(X)) -> a__p(mark(X)) 1137.68/291.58 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.58 mark(s(X)) -> s(mark(X)) 1137.68/291.58 mark(0) -> 0 1137.68/291.58 mark(true) -> true 1137.68/291.58 mark(false) -> false 1137.68/291.58 a__fact(X) -> fact(X) 1137.68/291.58 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.58 a__zero(X) -> zero(X) 1137.68/291.58 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.58 a__p(X) -> p(X) 1137.68/291.58 a__add(X1, X2) -> add(X1, X2) 1137.68/291.58 1137.68/291.58 S is empty. 1137.68/291.58 Rewrite Strategy: INNERMOST 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1137.68/291.58 Renamed function symbols to avoid clashes with predefined symbol. 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (2) 1137.68/291.58 Obligation: 1137.68/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.68/291.58 1137.68/291.58 1137.68/291.58 The TRS R consists of the following rules: 1137.68/291.58 1137.68/291.58 a__fact(X) -> a__if(a__zero(mark(X)), s(0'), prod(X, fact(p(X)))) 1137.68/291.58 a__add(0', X) -> mark(X) 1137.68/291.58 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.58 a__prod(0', X) -> 0' 1137.68/291.58 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.58 a__if(true, X, Y) -> mark(X) 1137.68/291.58 a__if(false, X, Y) -> mark(Y) 1137.68/291.58 a__zero(0') -> true 1137.68/291.58 a__zero(s(X)) -> false 1137.68/291.58 a__p(s(X)) -> mark(X) 1137.68/291.58 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.58 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.58 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.58 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.58 mark(p(X)) -> a__p(mark(X)) 1137.68/291.58 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.58 mark(s(X)) -> s(mark(X)) 1137.68/291.58 mark(0') -> 0' 1137.68/291.58 mark(true) -> true 1137.68/291.58 mark(false) -> false 1137.68/291.58 a__fact(X) -> fact(X) 1137.68/291.58 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.58 a__zero(X) -> zero(X) 1137.68/291.58 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.58 a__p(X) -> p(X) 1137.68/291.58 a__add(X1, X2) -> add(X1, X2) 1137.68/291.58 1137.68/291.58 S is empty. 1137.68/291.58 Rewrite Strategy: INNERMOST 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1137.68/291.58 Infered types. 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (4) 1137.68/291.58 Obligation: 1137.68/291.58 Innermost TRS: 1137.68/291.58 Rules: 1137.68/291.58 a__fact(X) -> a__if(a__zero(mark(X)), s(0'), prod(X, fact(p(X)))) 1137.68/291.58 a__add(0', X) -> mark(X) 1137.68/291.58 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.58 a__prod(0', X) -> 0' 1137.68/291.58 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.58 a__if(true, X, Y) -> mark(X) 1137.68/291.58 a__if(false, X, Y) -> mark(Y) 1137.68/291.58 a__zero(0') -> true 1137.68/291.58 a__zero(s(X)) -> false 1137.68/291.58 a__p(s(X)) -> mark(X) 1137.68/291.58 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.58 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.58 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.58 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.58 mark(p(X)) -> a__p(mark(X)) 1137.68/291.58 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.58 mark(s(X)) -> s(mark(X)) 1137.68/291.58 mark(0') -> 0' 1137.68/291.58 mark(true) -> true 1137.68/291.58 mark(false) -> false 1137.68/291.58 a__fact(X) -> fact(X) 1137.68/291.58 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.58 a__zero(X) -> zero(X) 1137.68/291.58 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.58 a__p(X) -> p(X) 1137.68/291.58 a__add(X1, X2) -> add(X1, X2) 1137.68/291.58 1137.68/291.58 Types: 1137.68/291.58 a__fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 mark :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 s :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 0' :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 true :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 false :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 hole_0':s:p:fact:prod:true:false:if:zero:add1_0 :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 gen_0':s:p:fact:prod:true:false:if:zero:add2_0 :: Nat -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (5) OrderProof (LOWER BOUND(ID)) 1137.68/291.58 Heuristically decided to analyse the following defined symbols: 1137.68/291.58 a__fact, a__if, mark, a__add, a__prod, a__p 1137.68/291.58 1137.68/291.58 They will be analysed ascendingly in the following order: 1137.68/291.58 a__fact = a__if 1137.68/291.58 a__fact = mark 1137.68/291.58 a__fact = a__add 1137.68/291.58 a__fact = a__prod 1137.68/291.58 a__fact = a__p 1137.68/291.58 a__if = mark 1137.68/291.58 a__if = a__add 1137.68/291.58 a__if = a__prod 1137.68/291.58 a__if = a__p 1137.68/291.58 mark = a__add 1137.68/291.58 mark = a__prod 1137.68/291.58 mark = a__p 1137.68/291.58 a__add = a__prod 1137.68/291.58 a__add = a__p 1137.68/291.58 a__prod = a__p 1137.68/291.58 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (6) 1137.68/291.58 Obligation: 1137.68/291.58 Innermost TRS: 1137.68/291.58 Rules: 1137.68/291.58 a__fact(X) -> a__if(a__zero(mark(X)), s(0'), prod(X, fact(p(X)))) 1137.68/291.58 a__add(0', X) -> mark(X) 1137.68/291.58 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.58 a__prod(0', X) -> 0' 1137.68/291.58 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.58 a__if(true, X, Y) -> mark(X) 1137.68/291.58 a__if(false, X, Y) -> mark(Y) 1137.68/291.58 a__zero(0') -> true 1137.68/291.58 a__zero(s(X)) -> false 1137.68/291.58 a__p(s(X)) -> mark(X) 1137.68/291.58 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.58 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.58 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.58 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.58 mark(p(X)) -> a__p(mark(X)) 1137.68/291.58 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.58 mark(s(X)) -> s(mark(X)) 1137.68/291.58 mark(0') -> 0' 1137.68/291.58 mark(true) -> true 1137.68/291.58 mark(false) -> false 1137.68/291.58 a__fact(X) -> fact(X) 1137.68/291.58 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.58 a__zero(X) -> zero(X) 1137.68/291.58 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.58 a__p(X) -> p(X) 1137.68/291.58 a__add(X1, X2) -> add(X1, X2) 1137.68/291.58 1137.68/291.58 Types: 1137.68/291.58 a__fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 mark :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 s :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 0' :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 true :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 false :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 a__p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 hole_0':s:p:fact:prod:true:false:if:zero:add1_0 :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 gen_0':s:p:fact:prod:true:false:if:zero:add2_0 :: Nat -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.58 1137.68/291.58 1137.68/291.58 Generator Equations: 1137.68/291.58 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(0) <=> 0' 1137.68/291.58 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(+(x, 1)) <=> s(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(x)) 1137.68/291.58 1137.68/291.58 1137.68/291.58 The following defined symbols remain to be analysed: 1137.68/291.58 a__if, a__fact, mark, a__add, a__prod, a__p 1137.68/291.58 1137.68/291.58 They will be analysed ascendingly in the following order: 1137.68/291.58 a__fact = a__if 1137.68/291.58 a__fact = mark 1137.68/291.58 a__fact = a__add 1137.68/291.58 a__fact = a__prod 1137.68/291.58 a__fact = a__p 1137.68/291.58 a__if = mark 1137.68/291.58 a__if = a__add 1137.68/291.58 a__if = a__prod 1137.68/291.58 a__if = a__p 1137.68/291.58 mark = a__add 1137.68/291.58 mark = a__prod 1137.68/291.58 mark = a__p 1137.68/291.58 a__add = a__prod 1137.68/291.58 a__add = a__p 1137.68/291.58 a__prod = a__p 1137.68/291.58 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1137.68/291.58 Proved the following rewrite lemma: 1137.68/291.58 mark(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(n26_0)) -> gen_0':s:p:fact:prod:true:false:if:zero:add2_0(n26_0), rt in Omega(1 + n26_0) 1137.68/291.58 1137.68/291.58 Induction Base: 1137.68/291.58 mark(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(0)) ->_R^Omega(1) 1137.68/291.58 0' 1137.68/291.58 1137.68/291.58 Induction Step: 1137.68/291.58 mark(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(+(n26_0, 1))) ->_R^Omega(1) 1137.68/291.58 s(mark(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(n26_0))) ->_IH 1137.68/291.58 s(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(c27_0)) 1137.68/291.58 1137.68/291.58 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (8) 1137.68/291.58 Complex Obligation (BEST) 1137.68/291.58 1137.68/291.58 ---------------------------------------- 1137.68/291.58 1137.68/291.58 (9) 1137.68/291.58 Obligation: 1137.68/291.58 Proved the lower bound n^1 for the following obligation: 1137.68/291.58 1137.68/291.58 Innermost TRS: 1137.68/291.58 Rules: 1137.68/291.58 a__fact(X) -> a__if(a__zero(mark(X)), s(0'), prod(X, fact(p(X)))) 1137.68/291.58 a__add(0', X) -> mark(X) 1137.68/291.58 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.58 a__prod(0', X) -> 0' 1137.68/291.58 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.58 a__if(true, X, Y) -> mark(X) 1137.68/291.58 a__if(false, X, Y) -> mark(Y) 1137.68/291.58 a__zero(0') -> true 1137.68/291.58 a__zero(s(X)) -> false 1137.68/291.58 a__p(s(X)) -> mark(X) 1137.68/291.58 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.58 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.58 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.59 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.59 mark(p(X)) -> a__p(mark(X)) 1137.68/291.59 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.59 mark(s(X)) -> s(mark(X)) 1137.68/291.59 mark(0') -> 0' 1137.68/291.59 mark(true) -> true 1137.68/291.59 mark(false) -> false 1137.68/291.59 a__fact(X) -> fact(X) 1137.68/291.59 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.59 a__zero(X) -> zero(X) 1137.68/291.59 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.59 a__p(X) -> p(X) 1137.68/291.59 a__add(X1, X2) -> add(X1, X2) 1137.68/291.59 1137.68/291.59 Types: 1137.68/291.59 a__fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 mark :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 s :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 0' :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 true :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 false :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 hole_0':s:p:fact:prod:true:false:if:zero:add1_0 :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0 :: Nat -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 1137.68/291.59 1137.68/291.59 Generator Equations: 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(0) <=> 0' 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(+(x, 1)) <=> s(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(x)) 1137.68/291.59 1137.68/291.59 1137.68/291.59 The following defined symbols remain to be analysed: 1137.68/291.59 mark, a__fact, a__add, a__prod, a__p 1137.68/291.59 1137.68/291.59 They will be analysed ascendingly in the following order: 1137.68/291.59 a__fact = a__if 1137.68/291.59 a__fact = mark 1137.68/291.59 a__fact = a__add 1137.68/291.59 a__fact = a__prod 1137.68/291.59 a__fact = a__p 1137.68/291.59 a__if = mark 1137.68/291.59 a__if = a__add 1137.68/291.59 a__if = a__prod 1137.68/291.59 a__if = a__p 1137.68/291.59 mark = a__add 1137.68/291.59 mark = a__prod 1137.68/291.59 mark = a__p 1137.68/291.59 a__add = a__prod 1137.68/291.59 a__add = a__p 1137.68/291.59 a__prod = a__p 1137.68/291.59 1137.68/291.59 ---------------------------------------- 1137.68/291.59 1137.68/291.59 (10) LowerBoundPropagationProof (FINISHED) 1137.68/291.59 Propagated lower bound. 1137.68/291.59 ---------------------------------------- 1137.68/291.59 1137.68/291.59 (11) 1137.68/291.59 BOUNDS(n^1, INF) 1137.68/291.59 1137.68/291.59 ---------------------------------------- 1137.68/291.59 1137.68/291.59 (12) 1137.68/291.59 Obligation: 1137.68/291.59 Innermost TRS: 1137.68/291.59 Rules: 1137.68/291.59 a__fact(X) -> a__if(a__zero(mark(X)), s(0'), prod(X, fact(p(X)))) 1137.68/291.59 a__add(0', X) -> mark(X) 1137.68/291.59 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 1137.68/291.59 a__prod(0', X) -> 0' 1137.68/291.59 a__prod(s(X), Y) -> a__add(mark(Y), a__prod(mark(X), mark(Y))) 1137.68/291.59 a__if(true, X, Y) -> mark(X) 1137.68/291.59 a__if(false, X, Y) -> mark(Y) 1137.68/291.59 a__zero(0') -> true 1137.68/291.59 a__zero(s(X)) -> false 1137.68/291.59 a__p(s(X)) -> mark(X) 1137.68/291.59 mark(fact(X)) -> a__fact(mark(X)) 1137.68/291.59 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1137.68/291.59 mark(zero(X)) -> a__zero(mark(X)) 1137.68/291.59 mark(prod(X1, X2)) -> a__prod(mark(X1), mark(X2)) 1137.68/291.59 mark(p(X)) -> a__p(mark(X)) 1137.68/291.59 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 1137.68/291.59 mark(s(X)) -> s(mark(X)) 1137.68/291.59 mark(0') -> 0' 1137.68/291.59 mark(true) -> true 1137.68/291.59 mark(false) -> false 1137.68/291.59 a__fact(X) -> fact(X) 1137.68/291.59 a__if(X1, X2, X3) -> if(X1, X2, X3) 1137.68/291.59 a__zero(X) -> zero(X) 1137.68/291.59 a__prod(X1, X2) -> prod(X1, X2) 1137.68/291.59 a__p(X) -> p(X) 1137.68/291.59 a__add(X1, X2) -> add(X1, X2) 1137.68/291.59 1137.68/291.59 Types: 1137.68/291.59 a__fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 mark :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 s :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 0' :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 fact :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__prod :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 true :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 false :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 a__p :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 if :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 zero :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 add :: 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 hole_0':s:p:fact:prod:true:false:if:zero:add1_0 :: 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0 :: Nat -> 0':s:p:fact:prod:true:false:if:zero:add 1137.68/291.59 1137.68/291.59 1137.68/291.59 Lemmas: 1137.68/291.59 mark(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(n26_0)) -> gen_0':s:p:fact:prod:true:false:if:zero:add2_0(n26_0), rt in Omega(1 + n26_0) 1137.68/291.59 1137.68/291.59 1137.68/291.59 Generator Equations: 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(0) <=> 0' 1137.68/291.59 gen_0':s:p:fact:prod:true:false:if:zero:add2_0(+(x, 1)) <=> s(gen_0':s:p:fact:prod:true:false:if:zero:add2_0(x)) 1137.68/291.59 1137.68/291.59 1137.68/291.59 The following defined symbols remain to be analysed: 1137.68/291.59 a__fact, a__if, a__add, a__prod, a__p 1137.68/291.59 1137.68/291.59 They will be analysed ascendingly in the following order: 1137.68/291.59 a__fact = a__if 1137.68/291.59 a__fact = mark 1137.68/291.59 a__fact = a__add 1137.68/291.59 a__fact = a__prod 1137.68/291.59 a__fact = a__p 1137.68/291.59 a__if = mark 1137.68/291.59 a__if = a__add 1137.68/291.59 a__if = a__prod 1137.68/291.59 a__if = a__p 1137.68/291.59 mark = a__add 1137.68/291.59 mark = a__prod 1137.68/291.59 mark = a__p 1137.68/291.59 a__add = a__prod 1137.68/291.59 a__add = a__p 1137.68/291.59 a__prod = a__p 1137.89/291.66 EOF