8.60/2.93 WORST_CASE(NON_POLY, ?) 8.60/2.94 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.60/2.94 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.60/2.94 8.60/2.94 8.60/2.94 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 8.60/2.94 8.60/2.94 (0) CpxTRS 8.60/2.94 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 8.60/2.94 (2) TRS for Loop Detection 8.60/2.94 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 8.60/2.94 (4) BEST 8.60/2.94 (5) proven lower bound 8.60/2.94 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 8.60/2.94 (7) BOUNDS(n^1, INF) 8.60/2.94 (8) TRS for Loop Detection 8.60/2.94 (9) InfiniteLowerBoundProof [FINISHED, 978 ms] 8.60/2.94 (10) BOUNDS(INF, INF) 8.60/2.94 8.60/2.94 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (0) 8.60/2.94 Obligation: 8.60/2.94 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 8.60/2.94 8.60/2.94 8.60/2.94 The TRS R consists of the following rules: 8.60/2.94 8.60/2.94 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 8.60/2.94 sel(0, cons(X, Z)) -> X 8.60/2.94 first(0, Z) -> nil 8.60/2.94 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 8.60/2.94 from(X) -> cons(X, n__from(s(X))) 8.60/2.94 sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) 8.60/2.94 sel1(0, cons(X, Z)) -> quote(X) 8.60/2.94 first1(0, Z) -> nil1 8.60/2.94 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) 8.60/2.94 quote(n__0) -> 01 8.60/2.94 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) 8.60/2.94 quote1(n__nil) -> nil1 8.60/2.94 quote(n__s(X)) -> s1(quote(activate(X))) 8.60/2.94 quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) 8.60/2.94 quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) 8.60/2.94 unquote(01) -> 0 8.60/2.94 unquote(s1(X)) -> s(unquote(X)) 8.60/2.94 unquote1(nil1) -> nil 8.60/2.94 unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) 8.60/2.94 fcons(X, Z) -> cons(X, Z) 8.60/2.94 first(X1, X2) -> n__first(X1, X2) 8.60/2.94 from(X) -> n__from(X) 8.60/2.94 0 -> n__0 8.60/2.94 cons(X1, X2) -> n__cons(X1, X2) 8.60/2.94 nil -> n__nil 8.60/2.94 s(X) -> n__s(X) 8.60/2.94 sel(X1, X2) -> n__sel(X1, X2) 8.60/2.94 activate(n__first(X1, X2)) -> first(X1, X2) 8.60/2.94 activate(n__from(X)) -> from(X) 8.60/2.94 activate(n__0) -> 0 8.60/2.94 activate(n__cons(X1, X2)) -> cons(X1, X2) 8.60/2.94 activate(n__nil) -> nil 8.60/2.94 activate(n__s(X)) -> s(X) 8.60/2.94 activate(n__sel(X1, X2)) -> sel(X1, X2) 8.60/2.94 activate(X) -> X 8.60/2.94 8.60/2.94 S is empty. 8.60/2.94 Rewrite Strategy: FULL 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 8.60/2.94 Transformed a relative TRS into a decreasing-loop problem. 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (2) 8.60/2.94 Obligation: 8.60/2.94 Analyzing the following TRS for decreasing loops: 8.60/2.94 8.60/2.94 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 8.60/2.94 8.60/2.94 8.60/2.94 The TRS R consists of the following rules: 8.60/2.94 8.60/2.94 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 8.60/2.94 sel(0, cons(X, Z)) -> X 8.60/2.94 first(0, Z) -> nil 8.60/2.94 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 8.60/2.94 from(X) -> cons(X, n__from(s(X))) 8.60/2.94 sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) 8.60/2.94 sel1(0, cons(X, Z)) -> quote(X) 8.60/2.94 first1(0, Z) -> nil1 8.60/2.94 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) 8.60/2.94 quote(n__0) -> 01 8.60/2.94 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) 8.60/2.94 quote1(n__nil) -> nil1 8.60/2.94 quote(n__s(X)) -> s1(quote(activate(X))) 8.60/2.94 quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) 8.60/2.94 quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) 8.60/2.94 unquote(01) -> 0 8.60/2.94 unquote(s1(X)) -> s(unquote(X)) 8.60/2.94 unquote1(nil1) -> nil 8.60/2.94 unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) 8.60/2.94 fcons(X, Z) -> cons(X, Z) 8.60/2.94 first(X1, X2) -> n__first(X1, X2) 8.60/2.94 from(X) -> n__from(X) 8.60/2.94 0 -> n__0 8.60/2.94 cons(X1, X2) -> n__cons(X1, X2) 8.60/2.94 nil -> n__nil 8.60/2.94 s(X) -> n__s(X) 8.60/2.94 sel(X1, X2) -> n__sel(X1, X2) 8.60/2.94 activate(n__first(X1, X2)) -> first(X1, X2) 8.60/2.94 activate(n__from(X)) -> from(X) 8.60/2.94 activate(n__0) -> 0 8.60/2.94 activate(n__cons(X1, X2)) -> cons(X1, X2) 8.60/2.94 activate(n__nil) -> nil 8.60/2.94 activate(n__s(X)) -> s(X) 8.60/2.94 activate(n__sel(X1, X2)) -> sel(X1, X2) 8.60/2.94 activate(X) -> X 8.60/2.94 8.60/2.94 S is empty. 8.60/2.94 Rewrite Strategy: FULL 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (3) DecreasingLoopProof (LOWER BOUND(ID)) 8.60/2.94 The following loop(s) give(s) rise to the lower bound Omega(n^1): 8.60/2.94 8.60/2.94 The rewrite sequence 8.60/2.94 8.60/2.94 unquote1(cons1(X, Z)) ->^+ fcons(unquote(X), unquote1(Z)) 8.60/2.94 8.60/2.94 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 8.60/2.94 8.60/2.94 The pumping substitution is [Z / cons1(X, Z)]. 8.60/2.94 8.60/2.94 The result substitution is [ ]. 8.60/2.94 8.60/2.94 8.60/2.94 8.60/2.94 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (4) 8.60/2.94 Complex Obligation (BEST) 8.60/2.94 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (5) 8.60/2.94 Obligation: 8.60/2.94 Proved the lower bound n^1 for the following obligation: 8.60/2.94 8.60/2.94 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 8.60/2.94 8.60/2.94 8.60/2.94 The TRS R consists of the following rules: 8.60/2.94 8.60/2.94 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 8.60/2.94 sel(0, cons(X, Z)) -> X 8.60/2.94 first(0, Z) -> nil 8.60/2.94 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 8.60/2.94 from(X) -> cons(X, n__from(s(X))) 8.60/2.94 sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) 8.60/2.94 sel1(0, cons(X, Z)) -> quote(X) 8.60/2.94 first1(0, Z) -> nil1 8.60/2.94 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) 8.60/2.94 quote(n__0) -> 01 8.60/2.94 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) 8.60/2.94 quote1(n__nil) -> nil1 8.60/2.94 quote(n__s(X)) -> s1(quote(activate(X))) 8.60/2.94 quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) 8.60/2.94 quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) 8.60/2.94 unquote(01) -> 0 8.60/2.94 unquote(s1(X)) -> s(unquote(X)) 8.60/2.94 unquote1(nil1) -> nil 8.60/2.94 unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) 8.60/2.94 fcons(X, Z) -> cons(X, Z) 8.60/2.94 first(X1, X2) -> n__first(X1, X2) 8.60/2.94 from(X) -> n__from(X) 8.60/2.94 0 -> n__0 8.60/2.94 cons(X1, X2) -> n__cons(X1, X2) 8.60/2.94 nil -> n__nil 8.60/2.94 s(X) -> n__s(X) 8.60/2.94 sel(X1, X2) -> n__sel(X1, X2) 8.60/2.94 activate(n__first(X1, X2)) -> first(X1, X2) 8.60/2.94 activate(n__from(X)) -> from(X) 8.60/2.94 activate(n__0) -> 0 8.60/2.94 activate(n__cons(X1, X2)) -> cons(X1, X2) 8.60/2.94 activate(n__nil) -> nil 8.60/2.94 activate(n__s(X)) -> s(X) 8.60/2.94 activate(n__sel(X1, X2)) -> sel(X1, X2) 8.60/2.94 activate(X) -> X 8.60/2.94 8.60/2.94 S is empty. 8.60/2.94 Rewrite Strategy: FULL 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (6) LowerBoundPropagationProof (FINISHED) 8.60/2.94 Propagated lower bound. 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (7) 8.60/2.94 BOUNDS(n^1, INF) 8.60/2.94 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (8) 8.60/2.94 Obligation: 8.60/2.94 Analyzing the following TRS for decreasing loops: 8.60/2.94 8.60/2.94 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 8.60/2.94 8.60/2.94 8.60/2.94 The TRS R consists of the following rules: 8.60/2.94 8.60/2.94 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 8.60/2.94 sel(0, cons(X, Z)) -> X 8.60/2.94 first(0, Z) -> nil 8.60/2.94 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 8.60/2.94 from(X) -> cons(X, n__from(s(X))) 8.60/2.94 sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) 8.60/2.94 sel1(0, cons(X, Z)) -> quote(X) 8.60/2.94 first1(0, Z) -> nil1 8.60/2.94 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) 8.60/2.94 quote(n__0) -> 01 8.60/2.94 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) 8.60/2.94 quote1(n__nil) -> nil1 8.60/2.94 quote(n__s(X)) -> s1(quote(activate(X))) 8.60/2.94 quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) 8.60/2.94 quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) 8.60/2.94 unquote(01) -> 0 8.60/2.94 unquote(s1(X)) -> s(unquote(X)) 8.60/2.94 unquote1(nil1) -> nil 8.60/2.94 unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) 8.60/2.94 fcons(X, Z) -> cons(X, Z) 8.60/2.94 first(X1, X2) -> n__first(X1, X2) 8.60/2.94 from(X) -> n__from(X) 8.60/2.94 0 -> n__0 8.60/2.94 cons(X1, X2) -> n__cons(X1, X2) 8.60/2.94 nil -> n__nil 8.60/2.94 s(X) -> n__s(X) 8.60/2.94 sel(X1, X2) -> n__sel(X1, X2) 8.60/2.94 activate(n__first(X1, X2)) -> first(X1, X2) 8.60/2.94 activate(n__from(X)) -> from(X) 8.60/2.94 activate(n__0) -> 0 8.60/2.94 activate(n__cons(X1, X2)) -> cons(X1, X2) 8.60/2.94 activate(n__nil) -> nil 8.60/2.94 activate(n__s(X)) -> s(X) 8.60/2.94 activate(n__sel(X1, X2)) -> sel(X1, X2) 8.60/2.94 activate(X) -> X 8.60/2.94 8.60/2.94 S is empty. 8.60/2.94 Rewrite Strategy: FULL 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (9) InfiniteLowerBoundProof (FINISHED) 8.60/2.94 The following loop proves infinite runtime complexity: 8.60/2.94 8.60/2.94 The rewrite sequence 8.60/2.94 8.60/2.94 quote1(n__cons(X, n__from(X1_0))) ->^+ cons1(quote(activate(X)), quote1(n__cons(X1_0, n__from(s(X1_0))))) 8.60/2.94 8.60/2.94 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 8.60/2.94 8.60/2.94 The pumping substitution is [ ]. 8.60/2.94 8.60/2.94 The result substitution is [X / X1_0, X1_0 / s(X1_0)]. 8.60/2.94 8.60/2.94 8.60/2.94 8.60/2.94 8.60/2.94 ---------------------------------------- 8.60/2.94 8.60/2.94 (10) 8.60/2.94 BOUNDS(INF, INF) 8.96/3.19 EOF