7.36/3.13 WORST_CASE(Omega(n^1), O(n^1)) 7.36/3.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.36/3.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.36/3.14 7.36/3.14 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 7.36/3.14 7.36/3.14 (0) CpxTRS 7.36/3.14 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 7.36/3.14 (2) CpxTRS 7.36/3.14 (3) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 7.36/3.14 (4) BOUNDS(1, n^1) 7.36/3.14 (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 7.36/3.14 (6) TRS for Loop Detection 7.36/3.14 (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 7.36/3.14 (8) BEST 7.36/3.14 (9) proven lower bound 7.36/3.14 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 7.36/3.14 (11) BOUNDS(n^1, INF) 7.36/3.14 (12) TRS for Loop Detection 7.36/3.14 7.36/3.14 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (0) 7.36/3.14 Obligation: 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 7.36/3.14 7.36/3.14 7.36/3.14 The TRS R consists of the following rules: 7.36/3.14 7.36/3.14 f(X) -> g(n__h(n__f(X))) 7.36/3.14 h(X) -> n__h(X) 7.36/3.14 f(X) -> n__f(X) 7.36/3.14 activate(n__h(X)) -> h(activate(X)) 7.36/3.14 activate(n__f(X)) -> f(activate(X)) 7.36/3.14 activate(X) -> X 7.36/3.14 7.36/3.14 S is empty. 7.36/3.14 Rewrite Strategy: FULL 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 7.36/3.14 transformed relative TRS to TRS 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (2) 7.36/3.14 Obligation: 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 7.36/3.14 7.36/3.14 7.36/3.14 The TRS R consists of the following rules: 7.36/3.14 7.36/3.14 f(X) -> g(n__h(n__f(X))) 7.36/3.14 h(X) -> n__h(X) 7.36/3.14 f(X) -> n__f(X) 7.36/3.14 activate(n__h(X)) -> h(activate(X)) 7.36/3.14 activate(n__f(X)) -> f(activate(X)) 7.36/3.14 activate(X) -> X 7.36/3.14 7.36/3.14 S is empty. 7.36/3.14 Rewrite Strategy: FULL 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (3) CpxTrsMatchBoundsProof (FINISHED) 7.36/3.14 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2. 7.36/3.14 The certificate found is represented by the following graph. 7.36/3.14 7.36/3.14 "[1, 2, 3, 4, 5, 6, 7, 8] 7.36/3.14 {(1,2,[f_1|0, h_1|0, activate_1|0, n__f_1|1, n__h_1|1, g_1|1]), (1,3,[g_1|1]), (1,5,[h_1|1, n__h_1|2]), (1,6,[f_1|1, n__f_1|2]), (1,7,[g_1|2]), (2,2,[g_1|0, n__h_1|0, n__f_1|0]), (3,4,[n__h_1|1]), (4,2,[n__f_1|1]), (5,2,[activate_1|1, n__h_1|1, n__f_1|1, g_1|1]), (5,5,[h_1|1, n__h_1|2]), (5,6,[f_1|1, n__f_1|2]), (5,7,[g_1|2]), (6,2,[activate_1|1, n__h_1|1, n__f_1|1, g_1|1]), (6,5,[h_1|1, n__h_1|2]), (6,6,[f_1|1, n__f_1|2]), (6,7,[g_1|2]), (7,8,[n__h_1|2]), (8,6,[n__f_1|2])}" 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (4) 7.36/3.14 BOUNDS(1, n^1) 7.36/3.14 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 7.36/3.14 Transformed a relative TRS into a decreasing-loop problem. 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (6) 7.36/3.14 Obligation: 7.36/3.14 Analyzing the following TRS for decreasing loops: 7.36/3.14 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 7.36/3.14 7.36/3.14 7.36/3.14 The TRS R consists of the following rules: 7.36/3.14 7.36/3.14 f(X) -> g(n__h(n__f(X))) 7.36/3.14 h(X) -> n__h(X) 7.36/3.14 f(X) -> n__f(X) 7.36/3.14 activate(n__h(X)) -> h(activate(X)) 7.36/3.14 activate(n__f(X)) -> f(activate(X)) 7.36/3.14 activate(X) -> X 7.36/3.14 7.36/3.14 S is empty. 7.36/3.14 Rewrite Strategy: FULL 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (7) DecreasingLoopProof (LOWER BOUND(ID)) 7.36/3.14 The following loop(s) give(s) rise to the lower bound Omega(n^1): 7.36/3.14 7.36/3.14 The rewrite sequence 7.36/3.14 7.36/3.14 activate(n__f(X)) ->^+ f(activate(X)) 7.36/3.14 7.36/3.14 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 7.36/3.14 7.36/3.14 The pumping substitution is [X / n__f(X)]. 7.36/3.14 7.36/3.14 The result substitution is [ ]. 7.36/3.14 7.36/3.14 7.36/3.14 7.36/3.14 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (8) 7.36/3.14 Complex Obligation (BEST) 7.36/3.14 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (9) 7.36/3.14 Obligation: 7.36/3.14 Proved the lower bound n^1 for the following obligation: 7.36/3.14 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 7.36/3.14 7.36/3.14 7.36/3.14 The TRS R consists of the following rules: 7.36/3.14 7.36/3.14 f(X) -> g(n__h(n__f(X))) 7.36/3.14 h(X) -> n__h(X) 7.36/3.14 f(X) -> n__f(X) 7.36/3.14 activate(n__h(X)) -> h(activate(X)) 7.36/3.14 activate(n__f(X)) -> f(activate(X)) 7.36/3.14 activate(X) -> X 7.36/3.14 7.36/3.14 S is empty. 7.36/3.14 Rewrite Strategy: FULL 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (10) LowerBoundPropagationProof (FINISHED) 7.36/3.14 Propagated lower bound. 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (11) 7.36/3.14 BOUNDS(n^1, INF) 7.36/3.14 7.36/3.14 ---------------------------------------- 7.36/3.14 7.36/3.14 (12) 7.36/3.14 Obligation: 7.36/3.14 Analyzing the following TRS for decreasing loops: 7.36/3.14 7.36/3.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 7.36/3.14 7.36/3.14 7.36/3.14 The TRS R consists of the following rules: 7.36/3.14 7.36/3.14 f(X) -> g(n__h(n__f(X))) 7.36/3.14 h(X) -> n__h(X) 7.36/3.14 f(X) -> n__f(X) 7.36/3.14 activate(n__h(X)) -> h(activate(X)) 7.36/3.14 activate(n__f(X)) -> f(activate(X)) 7.36/3.14 activate(X) -> X 7.36/3.14 7.36/3.14 S is empty. 7.36/3.14 Rewrite Strategy: FULL 7.66/3.22 EOF