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