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