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