19.91/7.08 WORST_CASE(Omega(n^1), O(n^1)) 19.91/7.09 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 19.91/7.09 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.91/7.09 19.91/7.09 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.91/7.09 19.91/7.09 (0) CpxTRS 19.91/7.09 (1) DependencyGraphProof [UPPER BOUND(ID), 0 ms] 19.91/7.09 (2) CpxTRS 19.91/7.09 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 19.91/7.09 (4) CpxTRS 19.91/7.09 (5) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 19.91/7.09 (6) BOUNDS(1, n^1) 19.91/7.09 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 19.91/7.09 (8) TRS for Loop Detection 19.91/7.09 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 19.91/7.09 (10) BEST 19.91/7.09 (11) proven lower bound 19.91/7.09 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 19.91/7.09 (13) BOUNDS(n^1, INF) 19.91/7.09 (14) TRS for Loop Detection 19.91/7.09 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (0) 19.91/7.09 Obligation: 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 f(f(x)) -> f(c(f(x))) 19.91/7.09 f(f(x)) -> f(d(f(x))) 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (1) DependencyGraphProof (UPPER BOUND(ID)) 19.91/7.09 The following rules are not reachable from basic terms in the dependency graph and can be removed: 19.91/7.09 19.91/7.09 f(f(x)) -> f(c(f(x))) 19.91/7.09 f(f(x)) -> f(d(f(x))) 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (2) 19.91/7.09 Obligation: 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 19.91/7.09 transformed relative TRS to TRS 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (4) 19.91/7.09 Obligation: 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (5) CpxTrsMatchBoundsProof (FINISHED) 19.91/7.09 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2. 19.91/7.09 The certificate found is represented by the following graph. 19.91/7.09 19.91/7.09 "[5, 6, 7, 8, 9, 10, 11] 19.91/7.09 {(5,6,[g_1|0, c_1|1, d_1|1, h_1|1, 0|1, 1|1, g_1|1, 1|2]), (5,7,[g_1|1]), (5,9,[g_1|1]), (5,11,[h_1|2]), (6,6,[c_1|0, d_1|0, h_1|0, 0|0, 1|0]), (7,8,[d_1|1]), (8,6,[1|1]), (9,10,[d_1|1]), (10,11,[h_1|1]), (11,6,[0|1])}" 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (6) 19.91/7.09 BOUNDS(1, n^1) 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 19.91/7.09 Transformed a relative TRS into a decreasing-loop problem. 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (8) 19.91/7.09 Obligation: 19.91/7.09 Analyzing the following TRS for decreasing loops: 19.91/7.09 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 f(f(x)) -> f(c(f(x))) 19.91/7.09 f(f(x)) -> f(d(f(x))) 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (9) DecreasingLoopProof (LOWER BOUND(ID)) 19.91/7.09 The following loop(s) give(s) rise to the lower bound Omega(n^1): 19.91/7.09 19.91/7.09 The rewrite sequence 19.91/7.09 19.91/7.09 g(h(x)) ->^+ g(x) 19.91/7.09 19.91/7.09 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 19.91/7.09 19.91/7.09 The pumping substitution is [x / h(x)]. 19.91/7.09 19.91/7.09 The result substitution is [ ]. 19.91/7.09 19.91/7.09 19.91/7.09 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (10) 19.91/7.09 Complex Obligation (BEST) 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (11) 19.91/7.09 Obligation: 19.91/7.09 Proved the lower bound n^1 for the following obligation: 19.91/7.09 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 f(f(x)) -> f(c(f(x))) 19.91/7.09 f(f(x)) -> f(d(f(x))) 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (12) LowerBoundPropagationProof (FINISHED) 19.91/7.09 Propagated lower bound. 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (13) 19.91/7.09 BOUNDS(n^1, INF) 19.91/7.09 19.91/7.09 ---------------------------------------- 19.91/7.09 19.91/7.09 (14) 19.91/7.09 Obligation: 19.91/7.09 Analyzing the following TRS for decreasing loops: 19.91/7.09 19.91/7.09 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.91/7.09 19.91/7.09 19.91/7.09 The TRS R consists of the following rules: 19.91/7.09 19.91/7.09 f(f(x)) -> f(c(f(x))) 19.91/7.09 f(f(x)) -> f(d(f(x))) 19.91/7.09 g(c(x)) -> x 19.91/7.09 g(d(x)) -> x 19.91/7.09 g(c(h(0))) -> g(d(1)) 19.91/7.09 g(c(1)) -> g(d(h(0))) 19.91/7.09 g(h(x)) -> g(x) 19.91/7.09 19.91/7.09 S is empty. 19.91/7.09 Rewrite Strategy: FULL 19.99/7.14 EOF