308.99/291.60 WORST_CASE(Omega(n^1), ?) 309.27/291.70 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 309.27/291.70 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 309.27/291.70 309.27/291.70 309.27/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.27/291.70 309.27/291.70 (0) CpxTRS 309.27/291.70 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 309.27/291.70 (2) CpxTRS 309.27/291.70 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 309.27/291.70 (4) typed CpxTrs 309.27/291.70 (5) OrderProof [LOWER BOUND(ID), 0 ms] 309.27/291.70 (6) typed CpxTrs 309.27/291.70 (7) RewriteLemmaProof [LOWER BOUND(ID), 345 ms] 309.27/291.70 (8) BEST 309.27/291.70 (9) proven lower bound 309.27/291.70 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 309.27/291.70 (11) BOUNDS(n^1, INF) 309.27/291.70 (12) typed CpxTrs 309.27/291.70 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (0) 309.27/291.70 Obligation: 309.27/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.27/291.70 309.27/291.70 309.27/291.70 The TRS R consists of the following rules: 309.27/291.70 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0) -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0) -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0 -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 S is empty. 309.27/291.70 Rewrite Strategy: FULL 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 309.27/291.70 Renamed function symbols to avoid clashes with predefined symbol. 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (2) 309.27/291.70 Obligation: 309.27/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.27/291.70 309.27/291.70 309.27/291.70 The TRS R consists of the following rules: 309.27/291.70 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0' 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0') -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0') -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0' -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0' 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 S is empty. 309.27/291.70 Rewrite Strategy: FULL 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 309.27/291.70 Infered types. 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (4) 309.27/291.70 Obligation: 309.27/291.70 TRS: 309.27/291.70 Rules: 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0' 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0') -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0') -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0' -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0' 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 Types: 309.27/291.70 U11 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 tt :: tt 309.27/291.70 U12 :: tt -> tt 309.27/291.70 isNat :: n__0:n__plus:n__s:n__x -> tt 309.27/291.70 activate :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U21 :: tt -> tt 309.27/291.70 U31 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 U32 :: tt -> tt 309.27/291.70 U41 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U51 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U52 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U61 :: tt -> n__0:n__plus:n__s:n__x 309.27/291.70 0' :: n__0:n__plus:n__s:n__x 309.27/291.70 U71 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U72 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__0 :: n__0:n__plus:n__s:n__x 309.27/291.70 n__plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 hole_tt1_3 :: tt 309.27/291.70 hole_n__0:n__plus:n__s:n__x2_3 :: n__0:n__plus:n__s:n__x 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3 :: Nat -> n__0:n__plus:n__s:n__x 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (5) OrderProof (LOWER BOUND(ID)) 309.27/291.70 Heuristically decided to analyse the following defined symbols: 309.27/291.70 isNat, activate, U41, plus, x 309.27/291.70 309.27/291.70 They will be analysed ascendingly in the following order: 309.27/291.70 isNat = activate 309.27/291.70 isNat = U41 309.27/291.70 isNat = plus 309.27/291.70 isNat = x 309.27/291.70 activate = U41 309.27/291.70 activate = plus 309.27/291.70 activate = x 309.27/291.70 U41 = plus 309.27/291.70 U41 = x 309.27/291.70 plus = x 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (6) 309.27/291.70 Obligation: 309.27/291.70 TRS: 309.27/291.70 Rules: 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0' 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0') -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0') -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0' -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0' 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 Types: 309.27/291.70 U11 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 tt :: tt 309.27/291.70 U12 :: tt -> tt 309.27/291.70 isNat :: n__0:n__plus:n__s:n__x -> tt 309.27/291.70 activate :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U21 :: tt -> tt 309.27/291.70 U31 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 U32 :: tt -> tt 309.27/291.70 U41 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U51 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U52 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U61 :: tt -> n__0:n__plus:n__s:n__x 309.27/291.70 0' :: n__0:n__plus:n__s:n__x 309.27/291.70 U71 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U72 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__0 :: n__0:n__plus:n__s:n__x 309.27/291.70 n__plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 hole_tt1_3 :: tt 309.27/291.70 hole_n__0:n__plus:n__s:n__x2_3 :: n__0:n__plus:n__s:n__x 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3 :: Nat -> n__0:n__plus:n__s:n__x 309.27/291.70 309.27/291.70 309.27/291.70 Generator Equations: 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(0) <=> n__0 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s:n__x3_3(x), n__0) 309.27/291.70 309.27/291.70 309.27/291.70 The following defined symbols remain to be analysed: 309.27/291.70 activate, isNat, U41, plus, x 309.27/291.70 309.27/291.70 They will be analysed ascendingly in the following order: 309.27/291.70 isNat = activate 309.27/291.70 isNat = U41 309.27/291.70 isNat = plus 309.27/291.70 isNat = x 309.27/291.70 activate = U41 309.27/291.70 activate = plus 309.27/291.70 activate = x 309.27/291.70 U41 = plus 309.27/291.70 U41 = x 309.27/291.70 plus = x 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (7) RewriteLemmaProof (LOWER BOUND(ID)) 309.27/291.70 Proved the following rewrite lemma: 309.27/291.70 isNat(gen_n__0:n__plus:n__s:n__x3_3(n225_3)) -> tt, rt in Omega(1 + n225_3) 309.27/291.70 309.27/291.70 Induction Base: 309.27/291.70 isNat(gen_n__0:n__plus:n__s:n__x3_3(0)) ->_R^Omega(1) 309.27/291.70 tt 309.27/291.70 309.27/291.70 Induction Step: 309.27/291.70 isNat(gen_n__0:n__plus:n__s:n__x3_3(+(n225_3, 1))) ->_R^Omega(1) 309.27/291.70 U11(isNat(activate(gen_n__0:n__plus:n__s:n__x3_3(n225_3))), activate(n__0)) ->_R^Omega(1) 309.27/291.70 U11(isNat(gen_n__0:n__plus:n__s:n__x3_3(n225_3)), activate(n__0)) ->_IH 309.27/291.70 U11(tt, activate(n__0)) ->_R^Omega(1) 309.27/291.70 U11(tt, n__0) ->_R^Omega(1) 309.27/291.70 U12(isNat(activate(n__0))) ->_R^Omega(1) 309.27/291.70 U12(isNat(n__0)) ->_R^Omega(1) 309.27/291.70 U12(tt) ->_R^Omega(1) 309.27/291.70 tt 309.27/291.70 309.27/291.70 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (8) 309.27/291.70 Complex Obligation (BEST) 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (9) 309.27/291.70 Obligation: 309.27/291.70 Proved the lower bound n^1 for the following obligation: 309.27/291.70 309.27/291.70 TRS: 309.27/291.70 Rules: 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0' 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0') -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0') -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0' -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0' 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 Types: 309.27/291.70 U11 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 tt :: tt 309.27/291.70 U12 :: tt -> tt 309.27/291.70 isNat :: n__0:n__plus:n__s:n__x -> tt 309.27/291.70 activate :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U21 :: tt -> tt 309.27/291.70 U31 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 U32 :: tt -> tt 309.27/291.70 U41 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U51 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U52 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U61 :: tt -> n__0:n__plus:n__s:n__x 309.27/291.70 0' :: n__0:n__plus:n__s:n__x 309.27/291.70 U71 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U72 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__0 :: n__0:n__plus:n__s:n__x 309.27/291.70 n__plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 hole_tt1_3 :: tt 309.27/291.70 hole_n__0:n__plus:n__s:n__x2_3 :: n__0:n__plus:n__s:n__x 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3 :: Nat -> n__0:n__plus:n__s:n__x 309.27/291.70 309.27/291.70 309.27/291.70 Generator Equations: 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(0) <=> n__0 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s:n__x3_3(x), n__0) 309.27/291.70 309.27/291.70 309.27/291.70 The following defined symbols remain to be analysed: 309.27/291.70 isNat, x 309.27/291.70 309.27/291.70 They will be analysed ascendingly in the following order: 309.27/291.70 isNat = activate 309.27/291.70 isNat = U41 309.27/291.70 isNat = plus 309.27/291.70 isNat = x 309.27/291.70 activate = U41 309.27/291.70 activate = plus 309.27/291.70 activate = x 309.27/291.70 U41 = plus 309.27/291.70 U41 = x 309.27/291.70 plus = x 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (10) LowerBoundPropagationProof (FINISHED) 309.27/291.70 Propagated lower bound. 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (11) 309.27/291.70 BOUNDS(n^1, INF) 309.27/291.70 309.27/291.70 ---------------------------------------- 309.27/291.70 309.27/291.70 (12) 309.27/291.70 Obligation: 309.27/291.70 TRS: 309.27/291.70 Rules: 309.27/291.70 U11(tt, V2) -> U12(isNat(activate(V2))) 309.27/291.70 U12(tt) -> tt 309.27/291.70 U21(tt) -> tt 309.27/291.70 U31(tt, V2) -> U32(isNat(activate(V2))) 309.27/291.70 U32(tt) -> tt 309.27/291.70 U41(tt, N) -> activate(N) 309.27/291.70 U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U52(tt, M, N) -> s(plus(activate(N), activate(M))) 309.27/291.70 U61(tt) -> 0' 309.27/291.70 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) 309.27/291.70 U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 309.27/291.70 isNat(n__0) -> tt 309.27/291.70 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 309.27/291.70 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 309.27/291.70 isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) 309.27/291.70 plus(N, 0') -> U41(isNat(N), N) 309.27/291.70 plus(N, s(M)) -> U51(isNat(M), M, N) 309.27/291.70 x(N, 0') -> U61(isNat(N)) 309.27/291.70 x(N, s(M)) -> U71(isNat(M), M, N) 309.27/291.70 0' -> n__0 309.27/291.70 plus(X1, X2) -> n__plus(X1, X2) 309.27/291.70 s(X) -> n__s(X) 309.27/291.70 x(X1, X2) -> n__x(X1, X2) 309.27/291.70 activate(n__0) -> 0' 309.27/291.70 activate(n__plus(X1, X2)) -> plus(X1, X2) 309.27/291.70 activate(n__s(X)) -> s(X) 309.27/291.70 activate(n__x(X1, X2)) -> x(X1, X2) 309.27/291.70 activate(X) -> X 309.27/291.70 309.27/291.70 Types: 309.27/291.70 U11 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 tt :: tt 309.27/291.70 U12 :: tt -> tt 309.27/291.70 isNat :: n__0:n__plus:n__s:n__x -> tt 309.27/291.70 activate :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U21 :: tt -> tt 309.27/291.70 U31 :: tt -> n__0:n__plus:n__s:n__x -> tt 309.27/291.70 U32 :: tt -> tt 309.27/291.70 U41 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U51 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U52 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U61 :: tt -> n__0:n__plus:n__s:n__x 309.27/291.70 0' :: n__0:n__plus:n__s:n__x 309.27/291.70 U71 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 U72 :: tt -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__0 :: n__0:n__plus:n__s:n__x 309.27/291.70 n__plus :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__s :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 n__x :: n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x -> n__0:n__plus:n__s:n__x 309.27/291.70 hole_tt1_3 :: tt 309.27/291.70 hole_n__0:n__plus:n__s:n__x2_3 :: n__0:n__plus:n__s:n__x 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3 :: Nat -> n__0:n__plus:n__s:n__x 309.27/291.70 309.27/291.70 309.27/291.70 Lemmas: 309.27/291.70 isNat(gen_n__0:n__plus:n__s:n__x3_3(n225_3)) -> tt, rt in Omega(1 + n225_3) 309.27/291.70 309.27/291.70 309.27/291.70 Generator Equations: 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(0) <=> n__0 309.27/291.70 gen_n__0:n__plus:n__s:n__x3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s:n__x3_3(x), n__0) 309.27/291.70 309.27/291.70 309.27/291.70 The following defined symbols remain to be analysed: 309.27/291.70 x, activate, U41, plus 309.27/291.70 309.27/291.70 They will be analysed ascendingly in the following order: 309.27/291.70 isNat = activate 309.27/291.70 isNat = U41 309.27/291.70 isNat = plus 309.27/291.70 isNat = x 309.27/291.70 activate = U41 309.27/291.70 activate = plus 309.27/291.70 activate = x 309.27/291.70 U41 = plus 309.27/291.70 U41 = x 309.27/291.70 plus = x 309.33/291.73 EOF