4.05/1.83 WORST_CASE(NON_POLY, ?) 4.05/1.83 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.05/1.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.05/1.83 4.05/1.83 4.05/1.83 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.05/1.83 4.05/1.83 (0) CpxTRS 4.05/1.83 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 4.05/1.83 (2) TRS for Loop Detection 4.05/1.83 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 4.05/1.83 (4) BEST 4.05/1.83 (5) proven lower bound 4.05/1.83 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 4.05/1.83 (7) BOUNDS(n^1, INF) 4.05/1.83 (8) TRS for Loop Detection 4.05/1.83 (9) DecreasingLoopProof [FINISHED, 92 ms] 4.05/1.83 (10) BOUNDS(EXP, INF) 4.05/1.83 4.05/1.83 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (0) 4.05/1.83 Obligation: 4.05/1.83 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.05/1.83 4.05/1.83 4.05/1.83 The TRS R consists of the following rules: 4.05/1.83 4.05/1.83 a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) 4.05/1.83 a__sel(0, cons(X, Z)) -> mark(X) 4.05/1.83 a__first(0, Z) -> nil 4.05/1.83 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 4.05/1.83 a__from(X) -> cons(mark(X), from(s(X))) 4.05/1.83 a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__sel1(0, cons(X, Z)) -> a__quote(X) 4.05/1.83 a__first1(0, Z) -> nil1 4.05/1.83 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) 4.05/1.83 a__quote(0) -> 01 4.05/1.83 a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) 4.05/1.83 a__quote1(nil) -> nil1 4.05/1.83 a__quote(s(X)) -> s1(a__quote(X)) 4.05/1.83 a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) 4.05/1.83 a__unquote(01) -> 0 4.05/1.83 a__unquote(s1(X)) -> s(a__unquote(mark(X))) 4.05/1.83 a__unquote1(nil1) -> nil 4.05/1.83 a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) 4.05/1.83 a__fcons(X, Z) -> cons(mark(X), Z) 4.05/1.83 mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) 4.05/1.83 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 4.05/1.83 mark(from(X)) -> a__from(mark(X)) 4.05/1.83 mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) 4.05/1.83 mark(quote(X)) -> a__quote(X) 4.05/1.83 mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) 4.05/1.83 mark(quote1(X)) -> a__quote1(X) 4.05/1.83 mark(unquote(X)) -> a__unquote(mark(X)) 4.05/1.83 mark(unquote1(X)) -> a__unquote1(mark(X)) 4.05/1.83 mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) 4.05/1.83 mark(s(X)) -> s(mark(X)) 4.05/1.83 mark(cons(X1, X2)) -> cons(mark(X1), X2) 4.05/1.83 mark(0) -> 0 4.05/1.83 mark(nil) -> nil 4.05/1.83 mark(nil1) -> nil1 4.05/1.83 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 4.05/1.83 mark(01) -> 01 4.05/1.83 mark(s1(X)) -> s1(mark(X)) 4.05/1.83 a__sel(X1, X2) -> sel(X1, X2) 4.05/1.83 a__first(X1, X2) -> first(X1, X2) 4.05/1.83 a__from(X) -> from(X) 4.05/1.83 a__sel1(X1, X2) -> sel1(X1, X2) 4.05/1.83 a__quote(X) -> quote(X) 4.05/1.83 a__first1(X1, X2) -> first1(X1, X2) 4.05/1.83 a__quote1(X) -> quote1(X) 4.05/1.83 a__unquote(X) -> unquote(X) 4.05/1.83 a__unquote1(X) -> unquote1(X) 4.05/1.83 a__fcons(X1, X2) -> fcons(X1, X2) 4.05/1.83 4.05/1.83 S is empty. 4.05/1.83 Rewrite Strategy: FULL 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 4.05/1.83 Transformed a relative TRS into a decreasing-loop problem. 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (2) 4.05/1.83 Obligation: 4.05/1.83 Analyzing the following TRS for decreasing loops: 4.05/1.83 4.05/1.83 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.05/1.83 4.05/1.83 4.05/1.83 The TRS R consists of the following rules: 4.05/1.83 4.05/1.83 a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) 4.05/1.83 a__sel(0, cons(X, Z)) -> mark(X) 4.05/1.83 a__first(0, Z) -> nil 4.05/1.83 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 4.05/1.83 a__from(X) -> cons(mark(X), from(s(X))) 4.05/1.83 a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__sel1(0, cons(X, Z)) -> a__quote(X) 4.05/1.83 a__first1(0, Z) -> nil1 4.05/1.83 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) 4.05/1.83 a__quote(0) -> 01 4.05/1.83 a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) 4.05/1.83 a__quote1(nil) -> nil1 4.05/1.83 a__quote(s(X)) -> s1(a__quote(X)) 4.05/1.83 a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) 4.05/1.83 a__unquote(01) -> 0 4.05/1.83 a__unquote(s1(X)) -> s(a__unquote(mark(X))) 4.05/1.83 a__unquote1(nil1) -> nil 4.05/1.83 a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) 4.05/1.83 a__fcons(X, Z) -> cons(mark(X), Z) 4.05/1.83 mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) 4.05/1.83 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 4.05/1.83 mark(from(X)) -> a__from(mark(X)) 4.05/1.83 mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) 4.05/1.83 mark(quote(X)) -> a__quote(X) 4.05/1.83 mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) 4.05/1.83 mark(quote1(X)) -> a__quote1(X) 4.05/1.83 mark(unquote(X)) -> a__unquote(mark(X)) 4.05/1.83 mark(unquote1(X)) -> a__unquote1(mark(X)) 4.05/1.83 mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) 4.05/1.83 mark(s(X)) -> s(mark(X)) 4.05/1.83 mark(cons(X1, X2)) -> cons(mark(X1), X2) 4.05/1.83 mark(0) -> 0 4.05/1.83 mark(nil) -> nil 4.05/1.83 mark(nil1) -> nil1 4.05/1.83 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 4.05/1.83 mark(01) -> 01 4.05/1.83 mark(s1(X)) -> s1(mark(X)) 4.05/1.83 a__sel(X1, X2) -> sel(X1, X2) 4.05/1.83 a__first(X1, X2) -> first(X1, X2) 4.05/1.83 a__from(X) -> from(X) 4.05/1.83 a__sel1(X1, X2) -> sel1(X1, X2) 4.05/1.83 a__quote(X) -> quote(X) 4.05/1.83 a__first1(X1, X2) -> first1(X1, X2) 4.05/1.83 a__quote1(X) -> quote1(X) 4.05/1.83 a__unquote(X) -> unquote(X) 4.05/1.83 a__unquote1(X) -> unquote1(X) 4.05/1.83 a__fcons(X1, X2) -> fcons(X1, X2) 4.05/1.83 4.05/1.83 S is empty. 4.05/1.83 Rewrite Strategy: FULL 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (3) DecreasingLoopProof (LOWER BOUND(ID)) 4.05/1.83 The following loop(s) give(s) rise to the lower bound Omega(n^1): 4.05/1.83 4.05/1.83 The rewrite sequence 4.05/1.83 4.05/1.83 mark(sel1(X1, X2)) ->^+ a__sel1(mark(X1), mark(X2)) 4.05/1.83 4.05/1.83 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 4.05/1.83 4.05/1.83 The pumping substitution is [X1 / sel1(X1, X2)]. 4.05/1.83 4.05/1.83 The result substitution is [ ]. 4.05/1.83 4.05/1.83 4.05/1.83 4.05/1.83 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (4) 4.05/1.83 Complex Obligation (BEST) 4.05/1.83 4.05/1.83 ---------------------------------------- 4.05/1.83 4.05/1.83 (5) 4.05/1.83 Obligation: 4.05/1.83 Proved the lower bound n^1 for the following obligation: 4.05/1.83 4.05/1.83 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.05/1.83 4.05/1.83 4.05/1.83 The TRS R consists of the following rules: 4.05/1.83 4.05/1.83 a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) 4.05/1.83 a__sel(0, cons(X, Z)) -> mark(X) 4.05/1.83 a__first(0, Z) -> nil 4.05/1.83 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 4.05/1.83 a__from(X) -> cons(mark(X), from(s(X))) 4.05/1.83 a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__sel1(0, cons(X, Z)) -> a__quote(X) 4.05/1.83 a__first1(0, Z) -> nil1 4.05/1.83 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) 4.05/1.83 a__quote(0) -> 01 4.05/1.83 a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) 4.05/1.83 a__quote1(nil) -> nil1 4.05/1.83 a__quote(s(X)) -> s1(a__quote(X)) 4.05/1.83 a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.83 a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) 4.05/1.83 a__unquote(01) -> 0 4.05/1.83 a__unquote(s1(X)) -> s(a__unquote(mark(X))) 4.05/1.83 a__unquote1(nil1) -> nil 4.05/1.83 a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) 4.05/1.83 a__fcons(X, Z) -> cons(mark(X), Z) 4.05/1.83 mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) 4.05/1.83 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 4.05/1.83 mark(from(X)) -> a__from(mark(X)) 4.05/1.83 mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) 4.05/1.83 mark(quote(X)) -> a__quote(X) 4.05/1.83 mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) 4.05/1.83 mark(quote1(X)) -> a__quote1(X) 4.05/1.83 mark(unquote(X)) -> a__unquote(mark(X)) 4.05/1.83 mark(unquote1(X)) -> a__unquote1(mark(X)) 4.05/1.84 mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) 4.05/1.84 mark(s(X)) -> s(mark(X)) 4.05/1.84 mark(cons(X1, X2)) -> cons(mark(X1), X2) 4.05/1.84 mark(0) -> 0 4.05/1.84 mark(nil) -> nil 4.05/1.84 mark(nil1) -> nil1 4.05/1.84 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 4.05/1.84 mark(01) -> 01 4.05/1.84 mark(s1(X)) -> s1(mark(X)) 4.05/1.84 a__sel(X1, X2) -> sel(X1, X2) 4.05/1.84 a__first(X1, X2) -> first(X1, X2) 4.05/1.84 a__from(X) -> from(X) 4.05/1.84 a__sel1(X1, X2) -> sel1(X1, X2) 4.05/1.84 a__quote(X) -> quote(X) 4.05/1.84 a__first1(X1, X2) -> first1(X1, X2) 4.05/1.84 a__quote1(X) -> quote1(X) 4.05/1.84 a__unquote(X) -> unquote(X) 4.05/1.84 a__unquote1(X) -> unquote1(X) 4.05/1.84 a__fcons(X1, X2) -> fcons(X1, X2) 4.05/1.84 4.05/1.84 S is empty. 4.05/1.84 Rewrite Strategy: FULL 4.05/1.84 ---------------------------------------- 4.05/1.84 4.05/1.84 (6) LowerBoundPropagationProof (FINISHED) 4.05/1.84 Propagated lower bound. 4.05/1.84 ---------------------------------------- 4.05/1.84 4.05/1.84 (7) 4.05/1.84 BOUNDS(n^1, INF) 4.05/1.84 4.05/1.84 ---------------------------------------- 4.05/1.84 4.05/1.84 (8) 4.05/1.84 Obligation: 4.05/1.84 Analyzing the following TRS for decreasing loops: 4.05/1.84 4.05/1.84 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.05/1.84 4.05/1.84 4.05/1.84 The TRS R consists of the following rules: 4.05/1.84 4.05/1.84 a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) 4.05/1.84 a__sel(0, cons(X, Z)) -> mark(X) 4.05/1.84 a__first(0, Z) -> nil 4.05/1.84 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 4.05/1.84 a__from(X) -> cons(mark(X), from(s(X))) 4.05/1.84 a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.84 a__sel1(0, cons(X, Z)) -> a__quote(X) 4.05/1.84 a__first1(0, Z) -> nil1 4.05/1.84 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) 4.05/1.84 a__quote(0) -> 01 4.05/1.84 a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) 4.05/1.84 a__quote1(nil) -> nil1 4.05/1.84 a__quote(s(X)) -> s1(a__quote(X)) 4.05/1.84 a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) 4.05/1.84 a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) 4.05/1.84 a__unquote(01) -> 0 4.05/1.84 a__unquote(s1(X)) -> s(a__unquote(mark(X))) 4.05/1.84 a__unquote1(nil1) -> nil 4.05/1.84 a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) 4.05/1.84 a__fcons(X, Z) -> cons(mark(X), Z) 4.05/1.84 mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) 4.05/1.84 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 4.05/1.84 mark(from(X)) -> a__from(mark(X)) 4.05/1.84 mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) 4.05/1.84 mark(quote(X)) -> a__quote(X) 4.05/1.84 mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) 4.05/1.84 mark(quote1(X)) -> a__quote1(X) 4.05/1.84 mark(unquote(X)) -> a__unquote(mark(X)) 4.05/1.84 mark(unquote1(X)) -> a__unquote1(mark(X)) 4.05/1.84 mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) 4.05/1.84 mark(s(X)) -> s(mark(X)) 4.05/1.84 mark(cons(X1, X2)) -> cons(mark(X1), X2) 4.05/1.84 mark(0) -> 0 4.05/1.84 mark(nil) -> nil 4.05/1.84 mark(nil1) -> nil1 4.05/1.84 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 4.05/1.84 mark(01) -> 01 4.05/1.84 mark(s1(X)) -> s1(mark(X)) 4.05/1.84 a__sel(X1, X2) -> sel(X1, X2) 4.05/1.84 a__first(X1, X2) -> first(X1, X2) 4.05/1.84 a__from(X) -> from(X) 4.05/1.84 a__sel1(X1, X2) -> sel1(X1, X2) 4.05/1.84 a__quote(X) -> quote(X) 4.05/1.84 a__first1(X1, X2) -> first1(X1, X2) 4.05/1.84 a__quote1(X) -> quote1(X) 4.05/1.84 a__unquote(X) -> unquote(X) 4.05/1.84 a__unquote1(X) -> unquote1(X) 4.05/1.84 a__fcons(X1, X2) -> fcons(X1, X2) 4.05/1.84 4.05/1.84 S is empty. 4.05/1.84 Rewrite Strategy: FULL 4.05/1.84 ---------------------------------------- 4.05/1.84 4.05/1.84 (9) DecreasingLoopProof (FINISHED) 4.05/1.84 The following loop(s) give(s) rise to the lower bound EXP: 4.05/1.84 4.05/1.84 The rewrite sequence 4.05/1.84 4.05/1.84 mark(from(X)) ->^+ cons(mark(mark(X)), from(s(mark(X)))) 4.05/1.84 4.05/1.84 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0]. 4.05/1.84 4.05/1.84 The pumping substitution is [X / from(X)]. 4.05/1.84 4.05/1.84 The result substitution is [ ]. 4.05/1.84 4.05/1.84 4.05/1.84 4.05/1.84 The rewrite sequence 4.05/1.84 4.05/1.84 mark(from(X)) ->^+ cons(mark(mark(X)), from(s(mark(X)))) 4.05/1.84 4.05/1.84 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0,0]. 4.05/1.84 4.05/1.84 The pumping substitution is [X / from(X)]. 4.05/1.84 4.05/1.84 The result substitution is [ ]. 4.05/1.84 4.05/1.84 4.05/1.84 4.05/1.84 4.05/1.84 ---------------------------------------- 4.05/1.84 4.05/1.84 (10) 4.05/1.84 BOUNDS(EXP, INF) 4.05/1.88 EOF