9.74/3.25 WORST_CASE(NON_POLY, ?) 9.74/3.26 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 9.74/3.26 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.74/3.26 9.74/3.26 9.74/3.26 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 9.74/3.26 9.74/3.26 (0) CpxTRS 9.74/3.26 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 9.74/3.26 (2) TRS for Loop Detection 9.74/3.26 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 9.74/3.26 (4) BEST 9.74/3.26 (5) proven lower bound 9.74/3.26 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 9.74/3.26 (7) BOUNDS(n^1, INF) 9.74/3.26 (8) TRS for Loop Detection 9.74/3.26 (9) InfiniteLowerBoundProof [FINISHED, 1192 ms] 9.74/3.26 (10) BOUNDS(INF, INF) 9.74/3.26 9.74/3.26 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (0) 9.74/3.26 Obligation: 9.74/3.26 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 9.74/3.26 9.74/3.26 9.74/3.26 The TRS R consists of the following rules: 9.74/3.26 9.74/3.26 from(X) -> cons(X, n__from(n__s(X))) 9.74/3.26 length(n__nil) -> 0 9.74/3.26 length(n__cons(X, Y)) -> s(length1(activate(Y))) 9.74/3.26 length1(X) -> length(activate(X)) 9.74/3.26 from(X) -> n__from(X) 9.74/3.26 s(X) -> n__s(X) 9.74/3.26 nil -> n__nil 9.74/3.26 cons(X1, X2) -> n__cons(X1, X2) 9.74/3.26 activate(n__from(X)) -> from(activate(X)) 9.74/3.26 activate(n__s(X)) -> s(activate(X)) 9.74/3.26 activate(n__nil) -> nil 9.74/3.26 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 9.74/3.26 activate(X) -> X 9.74/3.26 9.74/3.26 S is empty. 9.74/3.26 Rewrite Strategy: INNERMOST 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 9.74/3.26 Transformed a relative TRS into a decreasing-loop problem. 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (2) 9.74/3.26 Obligation: 9.74/3.26 Analyzing the following TRS for decreasing loops: 9.74/3.26 9.74/3.26 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 9.74/3.26 9.74/3.26 9.74/3.26 The TRS R consists of the following rules: 9.74/3.26 9.74/3.26 from(X) -> cons(X, n__from(n__s(X))) 9.74/3.26 length(n__nil) -> 0 9.74/3.26 length(n__cons(X, Y)) -> s(length1(activate(Y))) 9.74/3.26 length1(X) -> length(activate(X)) 9.74/3.26 from(X) -> n__from(X) 9.74/3.26 s(X) -> n__s(X) 9.74/3.26 nil -> n__nil 9.74/3.26 cons(X1, X2) -> n__cons(X1, X2) 9.74/3.26 activate(n__from(X)) -> from(activate(X)) 9.74/3.26 activate(n__s(X)) -> s(activate(X)) 9.74/3.26 activate(n__nil) -> nil 9.74/3.26 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 9.74/3.26 activate(X) -> X 9.74/3.26 9.74/3.26 S is empty. 9.74/3.26 Rewrite Strategy: INNERMOST 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (3) DecreasingLoopProof (LOWER BOUND(ID)) 9.74/3.26 The following loop(s) give(s) rise to the lower bound Omega(n^1): 9.74/3.26 9.74/3.26 The rewrite sequence 9.74/3.26 9.74/3.26 activate(n__s(X)) ->^+ s(activate(X)) 9.74/3.26 9.74/3.26 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 9.74/3.26 9.74/3.26 The pumping substitution is [X / n__s(X)]. 9.74/3.26 9.74/3.26 The result substitution is [ ]. 9.74/3.26 9.74/3.26 9.74/3.26 9.74/3.26 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (4) 9.74/3.26 Complex Obligation (BEST) 9.74/3.26 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (5) 9.74/3.26 Obligation: 9.74/3.26 Proved the lower bound n^1 for the following obligation: 9.74/3.26 9.74/3.26 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 9.74/3.26 9.74/3.26 9.74/3.26 The TRS R consists of the following rules: 9.74/3.26 9.74/3.26 from(X) -> cons(X, n__from(n__s(X))) 9.74/3.26 length(n__nil) -> 0 9.74/3.26 length(n__cons(X, Y)) -> s(length1(activate(Y))) 9.74/3.26 length1(X) -> length(activate(X)) 9.74/3.26 from(X) -> n__from(X) 9.74/3.26 s(X) -> n__s(X) 9.74/3.26 nil -> n__nil 9.74/3.26 cons(X1, X2) -> n__cons(X1, X2) 9.74/3.26 activate(n__from(X)) -> from(activate(X)) 9.74/3.26 activate(n__s(X)) -> s(activate(X)) 9.74/3.26 activate(n__nil) -> nil 9.74/3.26 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 9.74/3.26 activate(X) -> X 9.74/3.26 9.74/3.26 S is empty. 9.74/3.26 Rewrite Strategy: INNERMOST 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (6) LowerBoundPropagationProof (FINISHED) 9.74/3.26 Propagated lower bound. 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (7) 9.74/3.26 BOUNDS(n^1, INF) 9.74/3.26 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (8) 9.74/3.26 Obligation: 9.74/3.26 Analyzing the following TRS for decreasing loops: 9.74/3.26 9.74/3.26 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 9.74/3.26 9.74/3.26 9.74/3.26 The TRS R consists of the following rules: 9.74/3.26 9.74/3.26 from(X) -> cons(X, n__from(n__s(X))) 9.74/3.26 length(n__nil) -> 0 9.74/3.26 length(n__cons(X, Y)) -> s(length1(activate(Y))) 9.74/3.26 length1(X) -> length(activate(X)) 9.74/3.26 from(X) -> n__from(X) 9.74/3.26 s(X) -> n__s(X) 9.74/3.26 nil -> n__nil 9.74/3.26 cons(X1, X2) -> n__cons(X1, X2) 9.74/3.26 activate(n__from(X)) -> from(activate(X)) 9.74/3.26 activate(n__s(X)) -> s(activate(X)) 9.74/3.26 activate(n__nil) -> nil 9.74/3.26 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 9.74/3.26 activate(X) -> X 9.74/3.26 9.74/3.26 S is empty. 9.74/3.26 Rewrite Strategy: INNERMOST 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (9) InfiniteLowerBoundProof (FINISHED) 9.74/3.26 The following loop proves infinite runtime complexity: 9.74/3.26 9.74/3.26 The rewrite sequence 9.74/3.26 9.74/3.26 length(n__cons(X, n__from(X1_0))) ->^+ s(length(n__cons(X1_0, n__from(n__s(X1_0))))) 9.74/3.26 9.74/3.26 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 9.74/3.26 9.74/3.26 The pumping substitution is [ ]. 9.74/3.26 9.74/3.26 The result substitution is [X / X1_0, X1_0 / n__s(X1_0)]. 9.74/3.26 9.74/3.26 9.74/3.26 9.74/3.26 9.74/3.26 ---------------------------------------- 9.74/3.26 9.74/3.26 (10) 9.74/3.26 BOUNDS(INF, INF) 10.08/3.29 EOF