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