3.12/2.15 WORST_CASE(NON_POLY, ?) 3.12/2.16 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.12/2.16 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.12/2.16 3.12/2.16 3.12/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.12/2.16 3.12/2.16 (0) CpxTRS 3.12/2.16 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 3.12/2.16 (2) TRS for Loop Detection 3.12/2.16 (3) InfiniteLowerBoundProof [FINISHED, 0 ms] 3.12/2.16 (4) BOUNDS(INF, INF) 3.12/2.16 3.12/2.16 3.12/2.16 ---------------------------------------- 3.12/2.16 3.12/2.16 (0) 3.12/2.16 Obligation: 3.12/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.12/2.16 3.12/2.16 3.12/2.16 The TRS R consists of the following rules: 3.12/2.16 3.12/2.16 f(a) -> f(a) 3.12/2.16 3.12/2.16 S is empty. 3.12/2.16 Rewrite Strategy: FULL 3.12/2.16 ---------------------------------------- 3.12/2.16 3.12/2.16 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 3.12/2.16 Transformed a relative TRS into a decreasing-loop problem. 3.12/2.16 ---------------------------------------- 3.12/2.16 3.12/2.16 (2) 3.12/2.16 Obligation: 3.12/2.16 Analyzing the following TRS for decreasing loops: 3.12/2.16 3.12/2.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.12/2.16 3.12/2.16 3.12/2.16 The TRS R consists of the following rules: 3.12/2.16 3.12/2.16 f(a) -> f(a) 3.12/2.16 3.12/2.16 S is empty. 3.12/2.16 Rewrite Strategy: FULL 3.12/2.16 ---------------------------------------- 3.12/2.16 3.12/2.16 (3) InfiniteLowerBoundProof (FINISHED) 3.12/2.16 The following loop proves infinite runtime complexity: 3.12/2.16 3.12/2.16 The rewrite sequence 3.12/2.16 3.12/2.16 f(a) ->^+ f(a) 3.12/2.16 3.12/2.16 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 3.12/2.16 3.12/2.16 The pumping substitution is [ ]. 3.12/2.16 3.12/2.16 The result substitution is [ ]. 3.12/2.16 3.12/2.16 3.12/2.16 3.12/2.16 3.12/2.16 ---------------------------------------- 3.12/2.16 3.12/2.16 (4) 3.12/2.16 BOUNDS(INF, INF) 3.12/2.18 EOF