22.58/8.22 WORST_CASE(Omega(n^1), O(n^1)) 22.58/8.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 22.58/8.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 22.58/8.23 22.58/8.23 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.58/8.23 22.58/8.23 (0) CpxTRS 22.58/8.23 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 22.58/8.23 (2) CpxTRS 22.58/8.23 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 22.58/8.23 (4) CpxTRS 22.58/8.23 (5) CpxTrsMatchBoundsTAProof [FINISHED, 49 ms] 22.58/8.23 (6) BOUNDS(1, n^1) 22.58/8.23 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 22.58/8.23 (8) TRS for Loop Detection 22.58/8.23 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 22.58/8.23 (10) BEST 22.58/8.23 (11) proven lower bound 22.58/8.23 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 22.58/8.23 (13) BOUNDS(n^1, INF) 22.58/8.23 (14) TRS for Loop Detection 22.58/8.23 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (0) 22.58/8.23 Obligation: 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 22.58/8.23 active(__(X, nil)) -> mark(X) 22.58/8.23 active(__(nil, X)) -> mark(X) 22.58/8.23 active(U11(tt)) -> mark(U12(tt)) 22.58/8.23 active(U12(tt)) -> mark(tt) 22.58/8.23 active(isNePal(__(I, __(P, I)))) -> mark(U11(tt)) 22.58/8.23 active(__(X1, X2)) -> __(active(X1), X2) 22.58/8.23 active(__(X1, X2)) -> __(X1, active(X2)) 22.58/8.23 active(U11(X)) -> U11(active(X)) 22.58/8.23 active(U12(X)) -> U12(active(X)) 22.58/8.23 active(isNePal(X)) -> isNePal(active(X)) 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(U11(X)) -> U11(proper(X)) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 proper(U12(X)) -> U12(proper(X)) 22.58/8.23 proper(isNePal(X)) -> isNePal(proper(X)) 22.58/8.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.23 U11(ok(X)) -> ok(U11(X)) 22.58/8.23 U12(ok(X)) -> ok(U12(X)) 22.58/8.23 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.23 top(mark(X)) -> top(proper(X)) 22.58/8.23 top(ok(X)) -> top(active(X)) 22.58/8.23 22.58/8.23 S is empty. 22.58/8.23 Rewrite Strategy: FULL 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 22.58/8.23 The following defined symbols can occur below the 0th argument of top: proper, active 22.58/8.23 The following defined symbols can occur below the 0th argument of proper: proper, active 22.58/8.23 The following defined symbols can occur below the 0th argument of active: proper, active 22.58/8.23 22.58/8.23 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 22.58/8.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 22.58/8.23 active(__(X, nil)) -> mark(X) 22.58/8.23 active(__(nil, X)) -> mark(X) 22.58/8.23 active(U11(tt)) -> mark(U12(tt)) 22.58/8.23 active(U12(tt)) -> mark(tt) 22.58/8.23 active(isNePal(__(I, __(P, I)))) -> mark(U11(tt)) 22.58/8.23 active(__(X1, X2)) -> __(active(X1), X2) 22.58/8.23 active(__(X1, X2)) -> __(X1, active(X2)) 22.58/8.23 active(U11(X)) -> U11(active(X)) 22.58/8.23 active(U12(X)) -> U12(active(X)) 22.58/8.23 active(isNePal(X)) -> isNePal(active(X)) 22.58/8.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 22.58/8.23 proper(U11(X)) -> U11(proper(X)) 22.58/8.23 proper(U12(X)) -> U12(proper(X)) 22.58/8.23 proper(isNePal(X)) -> isNePal(proper(X)) 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (2) 22.58/8.23 Obligation: 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.23 U11(ok(X)) -> ok(U11(X)) 22.58/8.23 U12(ok(X)) -> ok(U12(X)) 22.58/8.23 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.23 top(mark(X)) -> top(proper(X)) 22.58/8.23 top(ok(X)) -> top(active(X)) 22.58/8.23 22.58/8.23 S is empty. 22.58/8.23 Rewrite Strategy: FULL 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 22.58/8.23 transformed relative TRS to TRS 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (4) 22.58/8.23 Obligation: 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.23 U11(ok(X)) -> ok(U11(X)) 22.58/8.23 U12(ok(X)) -> ok(U12(X)) 22.58/8.23 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.23 top(mark(X)) -> top(proper(X)) 22.58/8.23 top(ok(X)) -> top(active(X)) 22.58/8.23 22.58/8.23 S is empty. 22.58/8.23 Rewrite Strategy: FULL 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (5) CpxTrsMatchBoundsTAProof (FINISHED) 22.58/8.23 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 22.58/8.23 22.58/8.23 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 22.58/8.23 final states : [1, 2, 3, 4, 5, 6] 22.58/8.23 transitions: 22.58/8.23 mark0(0) -> 0 22.58/8.23 nil0() -> 0 22.58/8.23 ok0(0) -> 0 22.58/8.23 tt0() -> 0 22.58/8.23 active0(0) -> 0 22.58/8.23 __0(0, 0) -> 1 22.58/8.23 U110(0) -> 2 22.58/8.23 U120(0) -> 3 22.58/8.23 isNePal0(0) -> 4 22.58/8.23 proper0(0) -> 5 22.58/8.23 top0(0) -> 6 22.58/8.23 __1(0, 0) -> 7 22.58/8.23 mark1(7) -> 1 22.58/8.23 U111(0) -> 8 22.58/8.23 mark1(8) -> 2 22.58/8.23 U121(0) -> 9 22.58/8.23 mark1(9) -> 3 22.58/8.23 isNePal1(0) -> 10 22.58/8.23 mark1(10) -> 4 22.58/8.23 nil1() -> 11 22.58/8.23 ok1(11) -> 5 22.58/8.23 tt1() -> 12 22.58/8.23 ok1(12) -> 5 22.58/8.23 __1(0, 0) -> 13 22.58/8.23 ok1(13) -> 1 22.58/8.23 U111(0) -> 14 22.58/8.23 ok1(14) -> 2 22.58/8.23 U121(0) -> 15 22.58/8.23 ok1(15) -> 3 22.58/8.23 isNePal1(0) -> 16 22.58/8.23 ok1(16) -> 4 22.58/8.23 proper1(0) -> 17 22.58/8.23 top1(17) -> 6 22.58/8.23 active1(0) -> 18 22.58/8.23 top1(18) -> 6 22.58/8.23 mark1(7) -> 7 22.58/8.23 mark1(7) -> 13 22.58/8.23 mark1(8) -> 8 22.58/8.23 mark1(8) -> 14 22.58/8.23 mark1(9) -> 9 22.58/8.23 mark1(9) -> 15 22.58/8.23 mark1(10) -> 10 22.58/8.23 mark1(10) -> 16 22.58/8.23 ok1(11) -> 17 22.58/8.23 ok1(12) -> 17 22.58/8.23 ok1(13) -> 7 22.58/8.23 ok1(13) -> 13 22.58/8.23 ok1(14) -> 8 22.58/8.23 ok1(14) -> 14 22.58/8.23 ok1(15) -> 9 22.58/8.23 ok1(15) -> 15 22.58/8.23 ok1(16) -> 10 22.58/8.23 ok1(16) -> 16 22.58/8.23 active2(11) -> 19 22.58/8.23 top2(19) -> 6 22.58/8.23 active2(12) -> 19 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (6) 22.58/8.23 BOUNDS(1, n^1) 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 22.58/8.23 Transformed a relative TRS into a decreasing-loop problem. 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (8) 22.58/8.23 Obligation: 22.58/8.23 Analyzing the following TRS for decreasing loops: 22.58/8.23 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 22.58/8.23 active(__(X, nil)) -> mark(X) 22.58/8.23 active(__(nil, X)) -> mark(X) 22.58/8.23 active(U11(tt)) -> mark(U12(tt)) 22.58/8.23 active(U12(tt)) -> mark(tt) 22.58/8.23 active(isNePal(__(I, __(P, I)))) -> mark(U11(tt)) 22.58/8.23 active(__(X1, X2)) -> __(active(X1), X2) 22.58/8.23 active(__(X1, X2)) -> __(X1, active(X2)) 22.58/8.23 active(U11(X)) -> U11(active(X)) 22.58/8.23 active(U12(X)) -> U12(active(X)) 22.58/8.23 active(isNePal(X)) -> isNePal(active(X)) 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(U11(X)) -> U11(proper(X)) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 proper(U12(X)) -> U12(proper(X)) 22.58/8.23 proper(isNePal(X)) -> isNePal(proper(X)) 22.58/8.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.23 U11(ok(X)) -> ok(U11(X)) 22.58/8.23 U12(ok(X)) -> ok(U12(X)) 22.58/8.23 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.23 top(mark(X)) -> top(proper(X)) 22.58/8.23 top(ok(X)) -> top(active(X)) 22.58/8.23 22.58/8.23 S is empty. 22.58/8.23 Rewrite Strategy: FULL 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (9) DecreasingLoopProof (LOWER BOUND(ID)) 22.58/8.23 The following loop(s) give(s) rise to the lower bound Omega(n^1): 22.58/8.23 22.58/8.23 The rewrite sequence 22.58/8.23 22.58/8.23 U11(mark(X)) ->^+ mark(U11(X)) 22.58/8.23 22.58/8.23 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 22.58/8.23 22.58/8.23 The pumping substitution is [X / mark(X)]. 22.58/8.23 22.58/8.23 The result substitution is [ ]. 22.58/8.23 22.58/8.23 22.58/8.23 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (10) 22.58/8.23 Complex Obligation (BEST) 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (11) 22.58/8.23 Obligation: 22.58/8.23 Proved the lower bound n^1 for the following obligation: 22.58/8.23 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 22.58/8.23 active(__(X, nil)) -> mark(X) 22.58/8.23 active(__(nil, X)) -> mark(X) 22.58/8.23 active(U11(tt)) -> mark(U12(tt)) 22.58/8.23 active(U12(tt)) -> mark(tt) 22.58/8.23 active(isNePal(__(I, __(P, I)))) -> mark(U11(tt)) 22.58/8.23 active(__(X1, X2)) -> __(active(X1), X2) 22.58/8.23 active(__(X1, X2)) -> __(X1, active(X2)) 22.58/8.23 active(U11(X)) -> U11(active(X)) 22.58/8.23 active(U12(X)) -> U12(active(X)) 22.58/8.23 active(isNePal(X)) -> isNePal(active(X)) 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(U11(X)) -> U11(proper(X)) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 proper(U12(X)) -> U12(proper(X)) 22.58/8.23 proper(isNePal(X)) -> isNePal(proper(X)) 22.58/8.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.23 U11(ok(X)) -> ok(U11(X)) 22.58/8.23 U12(ok(X)) -> ok(U12(X)) 22.58/8.23 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.23 top(mark(X)) -> top(proper(X)) 22.58/8.23 top(ok(X)) -> top(active(X)) 22.58/8.23 22.58/8.23 S is empty. 22.58/8.23 Rewrite Strategy: FULL 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (12) LowerBoundPropagationProof (FINISHED) 22.58/8.23 Propagated lower bound. 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (13) 22.58/8.23 BOUNDS(n^1, INF) 22.58/8.23 22.58/8.23 ---------------------------------------- 22.58/8.23 22.58/8.23 (14) 22.58/8.23 Obligation: 22.58/8.23 Analyzing the following TRS for decreasing loops: 22.58/8.23 22.58/8.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.58/8.23 22.58/8.23 22.58/8.23 The TRS R consists of the following rules: 22.58/8.23 22.58/8.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 22.58/8.23 active(__(X, nil)) -> mark(X) 22.58/8.23 active(__(nil, X)) -> mark(X) 22.58/8.23 active(U11(tt)) -> mark(U12(tt)) 22.58/8.23 active(U12(tt)) -> mark(tt) 22.58/8.23 active(isNePal(__(I, __(P, I)))) -> mark(U11(tt)) 22.58/8.23 active(__(X1, X2)) -> __(active(X1), X2) 22.58/8.23 active(__(X1, X2)) -> __(X1, active(X2)) 22.58/8.23 active(U11(X)) -> U11(active(X)) 22.58/8.23 active(U12(X)) -> U12(active(X)) 22.58/8.23 active(isNePal(X)) -> isNePal(active(X)) 22.58/8.23 __(mark(X1), X2) -> mark(__(X1, X2)) 22.58/8.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 22.58/8.23 U11(mark(X)) -> mark(U11(X)) 22.58/8.23 U12(mark(X)) -> mark(U12(X)) 22.58/8.23 isNePal(mark(X)) -> mark(isNePal(X)) 22.58/8.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 22.58/8.23 proper(nil) -> ok(nil) 22.58/8.23 proper(U11(X)) -> U11(proper(X)) 22.58/8.23 proper(tt) -> ok(tt) 22.58/8.23 proper(U12(X)) -> U12(proper(X)) 22.58/8.24 proper(isNePal(X)) -> isNePal(proper(X)) 22.58/8.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 22.58/8.24 U11(ok(X)) -> ok(U11(X)) 22.58/8.24 U12(ok(X)) -> ok(U12(X)) 22.58/8.24 isNePal(ok(X)) -> ok(isNePal(X)) 22.58/8.24 top(mark(X)) -> top(proper(X)) 22.58/8.24 top(ok(X)) -> top(active(X)) 22.58/8.24 22.58/8.24 S is empty. 22.58/8.24 Rewrite Strategy: FULL 22.80/11.46 EOF