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