315.96/291.46 WORST_CASE(Omega(n^1), ?) 316.02/291.47 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 316.02/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 316.02/291.47 316.02/291.47 316.02/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 316.02/291.47 316.02/291.47 (0) CpxTRS 316.02/291.47 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 316.02/291.47 (2) TRS for Loop Detection 316.02/291.47 (3) DecreasingLoopProof [LOWER BOUND(ID), 54 ms] 316.02/291.47 (4) BEST 316.02/291.47 (5) proven lower bound 316.02/291.47 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 316.02/291.47 (7) BOUNDS(n^1, INF) 316.02/291.47 (8) TRS for Loop Detection 316.02/291.47 316.02/291.47 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (0) 316.02/291.47 Obligation: 316.02/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 316.02/291.47 316.02/291.47 316.02/291.47 The TRS R consists of the following rules: 316.02/291.47 316.02/291.47 U11(tt, V2) -> U12(isNat(activate(V2))) 316.02/291.47 U12(tt) -> tt 316.02/291.47 U21(tt) -> tt 316.02/291.47 U31(tt, N) -> activate(N) 316.02/291.47 U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N)) 316.02/291.47 U42(tt, M, N) -> s(plus(activate(N), activate(M))) 316.02/291.47 isNat(n__0) -> tt 316.02/291.47 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 316.02/291.47 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 316.02/291.47 plus(N, 0) -> U31(isNat(N), N) 316.02/291.47 plus(N, s(M)) -> U41(isNat(M), M, N) 316.02/291.47 0 -> n__0 316.02/291.47 plus(X1, X2) -> n__plus(X1, X2) 316.02/291.47 s(X) -> n__s(X) 316.02/291.47 activate(n__0) -> 0 316.02/291.47 activate(n__plus(X1, X2)) -> plus(X1, X2) 316.02/291.47 activate(n__s(X)) -> s(X) 316.02/291.47 activate(X) -> X 316.02/291.47 316.02/291.47 S is empty. 316.02/291.47 Rewrite Strategy: FULL 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 316.02/291.47 Transformed a relative TRS into a decreasing-loop problem. 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (2) 316.02/291.47 Obligation: 316.02/291.47 Analyzing the following TRS for decreasing loops: 316.02/291.47 316.02/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 316.02/291.47 316.02/291.47 316.02/291.47 The TRS R consists of the following rules: 316.02/291.47 316.02/291.47 U11(tt, V2) -> U12(isNat(activate(V2))) 316.02/291.47 U12(tt) -> tt 316.02/291.47 U21(tt) -> tt 316.02/291.47 U31(tt, N) -> activate(N) 316.02/291.47 U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N)) 316.02/291.47 U42(tt, M, N) -> s(plus(activate(N), activate(M))) 316.02/291.47 isNat(n__0) -> tt 316.02/291.47 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 316.02/291.47 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 316.02/291.47 plus(N, 0) -> U31(isNat(N), N) 316.02/291.47 plus(N, s(M)) -> U41(isNat(M), M, N) 316.02/291.47 0 -> n__0 316.02/291.47 plus(X1, X2) -> n__plus(X1, X2) 316.02/291.47 s(X) -> n__s(X) 316.02/291.47 activate(n__0) -> 0 316.02/291.47 activate(n__plus(X1, X2)) -> plus(X1, X2) 316.02/291.47 activate(n__s(X)) -> s(X) 316.02/291.47 activate(X) -> X 316.02/291.47 316.02/291.47 S is empty. 316.02/291.47 Rewrite Strategy: FULL 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (3) DecreasingLoopProof (LOWER BOUND(ID)) 316.02/291.47 The following loop(s) give(s) rise to the lower bound Omega(n^1): 316.02/291.47 316.02/291.47 The rewrite sequence 316.02/291.47 316.02/291.47 isNat(n__plus(V1, V2)) ->^+ U11(isNat(V1), activate(V2)) 316.02/291.47 316.02/291.47 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 316.02/291.47 316.02/291.47 The pumping substitution is [V1 / n__plus(V1, V2)]. 316.02/291.47 316.02/291.47 The result substitution is [ ]. 316.02/291.47 316.02/291.47 316.02/291.47 316.02/291.47 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (4) 316.02/291.47 Complex Obligation (BEST) 316.02/291.47 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (5) 316.02/291.47 Obligation: 316.02/291.47 Proved the lower bound n^1 for the following obligation: 316.02/291.47 316.02/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 316.02/291.47 316.02/291.47 316.02/291.47 The TRS R consists of the following rules: 316.02/291.47 316.02/291.47 U11(tt, V2) -> U12(isNat(activate(V2))) 316.02/291.47 U12(tt) -> tt 316.02/291.47 U21(tt) -> tt 316.02/291.47 U31(tt, N) -> activate(N) 316.02/291.47 U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N)) 316.02/291.47 U42(tt, M, N) -> s(plus(activate(N), activate(M))) 316.02/291.47 isNat(n__0) -> tt 316.02/291.47 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 316.02/291.47 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 316.02/291.47 plus(N, 0) -> U31(isNat(N), N) 316.02/291.47 plus(N, s(M)) -> U41(isNat(M), M, N) 316.02/291.47 0 -> n__0 316.02/291.47 plus(X1, X2) -> n__plus(X1, X2) 316.02/291.47 s(X) -> n__s(X) 316.02/291.47 activate(n__0) -> 0 316.02/291.47 activate(n__plus(X1, X2)) -> plus(X1, X2) 316.02/291.47 activate(n__s(X)) -> s(X) 316.02/291.47 activate(X) -> X 316.02/291.47 316.02/291.47 S is empty. 316.02/291.47 Rewrite Strategy: FULL 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (6) LowerBoundPropagationProof (FINISHED) 316.02/291.47 Propagated lower bound. 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (7) 316.02/291.47 BOUNDS(n^1, INF) 316.02/291.47 316.02/291.47 ---------------------------------------- 316.02/291.47 316.02/291.47 (8) 316.02/291.47 Obligation: 316.02/291.47 Analyzing the following TRS for decreasing loops: 316.02/291.47 316.02/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 316.02/291.47 316.02/291.47 316.02/291.47 The TRS R consists of the following rules: 316.02/291.47 316.02/291.47 U11(tt, V2) -> U12(isNat(activate(V2))) 316.02/291.47 U12(tt) -> tt 316.02/291.47 U21(tt) -> tt 316.02/291.47 U31(tt, N) -> activate(N) 316.02/291.47 U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N)) 316.02/291.47 U42(tt, M, N) -> s(plus(activate(N), activate(M))) 316.02/291.47 isNat(n__0) -> tt 316.02/291.47 isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) 316.02/291.47 isNat(n__s(V1)) -> U21(isNat(activate(V1))) 316.02/291.47 plus(N, 0) -> U31(isNat(N), N) 316.02/291.47 plus(N, s(M)) -> U41(isNat(M), M, N) 316.02/291.47 0 -> n__0 316.02/291.47 plus(X1, X2) -> n__plus(X1, X2) 316.02/291.47 s(X) -> n__s(X) 316.02/291.47 activate(n__0) -> 0 316.02/291.47 activate(n__plus(X1, X2)) -> plus(X1, X2) 316.02/291.47 activate(n__s(X)) -> s(X) 316.02/291.47 activate(X) -> X 316.02/291.47 316.02/291.47 S is empty. 316.02/291.47 Rewrite Strategy: FULL 316.02/291.51 EOF