5.55/2.22 WORST_CASE(NON_POLY, ?) 5.55/2.22 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.55/2.22 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.55/2.22 5.55/2.22 5.55/2.22 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.55/2.22 5.55/2.22 (0) CpxTRS 5.55/2.22 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 5.55/2.22 (2) TRS for Loop Detection 5.55/2.22 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 5.55/2.22 (4) BEST 5.55/2.22 (5) proven lower bound 5.55/2.22 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 5.55/2.22 (7) BOUNDS(n^1, INF) 5.55/2.22 (8) TRS for Loop Detection 5.55/2.22 (9) DecreasingLoopProof [FINISHED, 416 ms] 5.55/2.22 (10) BOUNDS(EXP, INF) 5.55/2.22 5.55/2.22 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (0) 5.55/2.22 Obligation: 5.55/2.22 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.55/2.22 5.55/2.22 5.55/2.22 The TRS R consists of the following rules: 5.55/2.22 5.55/2.22 a__U11(tt, M, N) -> a__U12(tt, M, N) 5.55/2.22 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 5.55/2.22 a__U21(tt, M, N) -> a__U22(tt, M, N) 5.55/2.22 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 5.55/2.22 a__plus(N, 0) -> mark(N) 5.55/2.22 a__plus(N, s(M)) -> a__U11(tt, M, N) 5.55/2.22 a__x(N, 0) -> 0 5.55/2.22 a__x(N, s(M)) -> a__U21(tt, M, N) 5.55/2.22 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 5.55/2.22 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 5.55/2.22 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 5.55/2.22 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 5.55/2.22 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 5.55/2.22 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 5.55/2.22 mark(tt) -> tt 5.55/2.22 mark(s(X)) -> s(mark(X)) 5.55/2.22 mark(0) -> 0 5.55/2.22 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 5.55/2.22 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 5.55/2.22 a__plus(X1, X2) -> plus(X1, X2) 5.55/2.22 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 5.55/2.22 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 5.55/2.22 a__x(X1, X2) -> x(X1, X2) 5.55/2.22 5.55/2.22 S is empty. 5.55/2.22 Rewrite Strategy: FULL 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 5.55/2.22 Transformed a relative TRS into a decreasing-loop problem. 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (2) 5.55/2.22 Obligation: 5.55/2.22 Analyzing the following TRS for decreasing loops: 5.55/2.22 5.55/2.22 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.55/2.22 5.55/2.22 5.55/2.22 The TRS R consists of the following rules: 5.55/2.22 5.55/2.22 a__U11(tt, M, N) -> a__U12(tt, M, N) 5.55/2.22 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 5.55/2.22 a__U21(tt, M, N) -> a__U22(tt, M, N) 5.55/2.22 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 5.55/2.22 a__plus(N, 0) -> mark(N) 5.55/2.22 a__plus(N, s(M)) -> a__U11(tt, M, N) 5.55/2.22 a__x(N, 0) -> 0 5.55/2.22 a__x(N, s(M)) -> a__U21(tt, M, N) 5.55/2.22 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 5.55/2.22 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 5.55/2.22 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 5.55/2.22 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 5.55/2.22 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 5.55/2.22 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 5.55/2.22 mark(tt) -> tt 5.55/2.22 mark(s(X)) -> s(mark(X)) 5.55/2.22 mark(0) -> 0 5.55/2.22 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 5.55/2.22 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 5.55/2.22 a__plus(X1, X2) -> plus(X1, X2) 5.55/2.22 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 5.55/2.22 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 5.55/2.22 a__x(X1, X2) -> x(X1, X2) 5.55/2.22 5.55/2.22 S is empty. 5.55/2.22 Rewrite Strategy: FULL 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (3) DecreasingLoopProof (LOWER BOUND(ID)) 5.55/2.22 The following loop(s) give(s) rise to the lower bound Omega(n^1): 5.55/2.22 5.55/2.22 The rewrite sequence 5.55/2.22 5.55/2.22 mark(U12(X1, X2, X3)) ->^+ a__U12(mark(X1), X2, X3) 5.55/2.22 5.55/2.22 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 5.55/2.22 5.55/2.22 The pumping substitution is [X1 / U12(X1, X2, X3)]. 5.55/2.22 5.55/2.22 The result substitution is [ ]. 5.55/2.22 5.55/2.22 5.55/2.22 5.55/2.22 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (4) 5.55/2.22 Complex Obligation (BEST) 5.55/2.22 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (5) 5.55/2.22 Obligation: 5.55/2.22 Proved the lower bound n^1 for the following obligation: 5.55/2.22 5.55/2.22 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.55/2.22 5.55/2.22 5.55/2.22 The TRS R consists of the following rules: 5.55/2.22 5.55/2.22 a__U11(tt, M, N) -> a__U12(tt, M, N) 5.55/2.22 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 5.55/2.22 a__U21(tt, M, N) -> a__U22(tt, M, N) 5.55/2.22 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 5.55/2.22 a__plus(N, 0) -> mark(N) 5.55/2.22 a__plus(N, s(M)) -> a__U11(tt, M, N) 5.55/2.22 a__x(N, 0) -> 0 5.55/2.22 a__x(N, s(M)) -> a__U21(tt, M, N) 5.55/2.22 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 5.55/2.22 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 5.55/2.22 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 5.55/2.22 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 5.55/2.22 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 5.55/2.22 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 5.55/2.22 mark(tt) -> tt 5.55/2.22 mark(s(X)) -> s(mark(X)) 5.55/2.22 mark(0) -> 0 5.55/2.22 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 5.55/2.22 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 5.55/2.22 a__plus(X1, X2) -> plus(X1, X2) 5.55/2.22 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 5.55/2.22 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 5.55/2.22 a__x(X1, X2) -> x(X1, X2) 5.55/2.22 5.55/2.22 S is empty. 5.55/2.22 Rewrite Strategy: FULL 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (6) LowerBoundPropagationProof (FINISHED) 5.55/2.22 Propagated lower bound. 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (7) 5.55/2.22 BOUNDS(n^1, INF) 5.55/2.22 5.55/2.22 ---------------------------------------- 5.55/2.22 5.55/2.22 (8) 5.55/2.22 Obligation: 5.55/2.22 Analyzing the following TRS for decreasing loops: 5.55/2.22 5.55/2.22 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.55/2.22 5.55/2.22 5.55/2.22 The TRS R consists of the following rules: 5.55/2.22 5.55/2.22 a__U11(tt, M, N) -> a__U12(tt, M, N) 5.55/2.22 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 5.55/2.22 a__U21(tt, M, N) -> a__U22(tt, M, N) 5.55/2.22 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 5.55/2.22 a__plus(N, 0) -> mark(N) 5.55/2.22 a__plus(N, s(M)) -> a__U11(tt, M, N) 5.55/2.22 a__x(N, 0) -> 0 5.55/2.22 a__x(N, s(M)) -> a__U21(tt, M, N) 5.55/2.22 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 5.55/2.22 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 5.55/2.22 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 5.55/2.22 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 5.55/2.22 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 5.55/2.22 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 5.55/2.22 mark(tt) -> tt 5.55/2.22 mark(s(X)) -> s(mark(X)) 5.55/2.22 mark(0) -> 0 5.55/2.22 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 5.55/2.22 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 5.55/2.22 a__plus(X1, X2) -> plus(X1, X2) 5.55/2.22 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 5.55/2.22 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 5.55/2.23 a__x(X1, X2) -> x(X1, X2) 5.55/2.23 5.55/2.23 S is empty. 5.55/2.23 Rewrite Strategy: FULL 5.55/2.23 ---------------------------------------- 5.55/2.23 5.55/2.23 (9) DecreasingLoopProof (FINISHED) 5.55/2.23 The following loop(s) give(s) rise to the lower bound EXP: 5.55/2.23 5.55/2.23 The rewrite sequence 5.55/2.23 5.55/2.23 mark(U22(tt, X2, X3)) ->^+ a__plus(a__x(mark(X3), mark(X2)), mark(X3)) 5.55/2.23 5.55/2.23 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0]. 5.55/2.23 5.55/2.23 The pumping substitution is [X3 / U22(tt, X2, X3)]. 5.55/2.23 5.55/2.23 The result substitution is [ ]. 5.55/2.23 5.55/2.23 5.55/2.23 5.55/2.23 The rewrite sequence 5.55/2.23 5.55/2.23 mark(U22(tt, X2, X3)) ->^+ a__plus(a__x(mark(X3), mark(X2)), mark(X3)) 5.55/2.23 5.55/2.23 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 5.55/2.23 5.55/2.23 The pumping substitution is [X3 / U22(tt, X2, X3)]. 5.55/2.23 5.55/2.23 The result substitution is [ ]. 5.55/2.23 5.55/2.23 5.55/2.23 5.55/2.23 5.55/2.23 ---------------------------------------- 5.55/2.23 5.55/2.23 (10) 5.55/2.23 BOUNDS(EXP, INF) 5.81/2.30 EOF