29.02/9.40 WORST_CASE(NON_POLY, ?) 29.13/9.41 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 29.13/9.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 29.13/9.41 29.13/9.41 29.13/9.41 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 29.13/9.41 29.13/9.41 (0) CpxTRS 29.13/9.41 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 29.13/9.41 (2) TRS for Loop Detection 29.13/9.41 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 29.13/9.41 (4) BEST 29.13/9.41 (5) proven lower bound 29.13/9.41 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 29.13/9.41 (7) BOUNDS(n^1, INF) 29.13/9.41 (8) TRS for Loop Detection 29.13/9.41 (9) DecreasingLoopProof [FINISHED, 7002 ms] 29.13/9.41 (10) BOUNDS(EXP, INF) 29.13/9.41 29.13/9.41 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (0) 29.13/9.41 Obligation: 29.13/9.41 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 29.13/9.41 29.13/9.41 29.13/9.41 The TRS R consists of the following rules: 29.13/9.41 29.13/9.41 a__and(tt, T) -> mark(T) 29.13/9.41 a__isNatIList(IL) -> a__isNatList(IL) 29.13/9.41 a__isNat(0) -> tt 29.13/9.41 a__isNat(s(N)) -> a__isNat(N) 29.13/9.41 a__isNat(length(L)) -> a__isNatList(L) 29.13/9.41 a__isNatIList(zeros) -> tt 29.13/9.41 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__isNatList(nil) -> tt 29.13/9.41 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 29.13/9.41 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__zeros -> cons(0, zeros) 29.13/9.41 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 29.13/9.41 a__uTake1(tt) -> nil 29.13/9.41 a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) 29.13/9.41 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 29.13/9.41 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 29.13/9.41 a__uLength(tt, L) -> s(a__length(mark(L))) 29.13/9.41 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 29.13/9.41 mark(isNatIList(X)) -> a__isNatIList(X) 29.13/9.41 mark(isNatList(X)) -> a__isNatList(X) 29.13/9.41 mark(isNat(X)) -> a__isNat(X) 29.13/9.41 mark(length(X)) -> a__length(mark(X)) 29.13/9.41 mark(zeros) -> a__zeros 29.13/9.41 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 29.13/9.41 mark(uTake1(X)) -> a__uTake1(mark(X)) 29.13/9.41 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 29.13/9.41 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 29.13/9.41 mark(tt) -> tt 29.13/9.41 mark(0) -> 0 29.13/9.41 mark(s(X)) -> s(mark(X)) 29.13/9.41 mark(cons(X1, X2)) -> cons(mark(X1), X2) 29.13/9.41 mark(nil) -> nil 29.13/9.41 a__and(X1, X2) -> and(X1, X2) 29.13/9.41 a__isNatIList(X) -> isNatIList(X) 29.13/9.41 a__isNatList(X) -> isNatList(X) 29.13/9.41 a__isNat(X) -> isNat(X) 29.13/9.41 a__length(X) -> length(X) 29.13/9.41 a__zeros -> zeros 29.13/9.41 a__take(X1, X2) -> take(X1, X2) 29.13/9.41 a__uTake1(X) -> uTake1(X) 29.13/9.41 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 29.13/9.41 a__uLength(X1, X2) -> uLength(X1, X2) 29.13/9.41 29.13/9.41 S is empty. 29.13/9.41 Rewrite Strategy: FULL 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 29.13/9.41 Transformed a relative TRS into a decreasing-loop problem. 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (2) 29.13/9.41 Obligation: 29.13/9.41 Analyzing the following TRS for decreasing loops: 29.13/9.41 29.13/9.41 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 29.13/9.41 29.13/9.41 29.13/9.41 The TRS R consists of the following rules: 29.13/9.41 29.13/9.41 a__and(tt, T) -> mark(T) 29.13/9.41 a__isNatIList(IL) -> a__isNatList(IL) 29.13/9.41 a__isNat(0) -> tt 29.13/9.41 a__isNat(s(N)) -> a__isNat(N) 29.13/9.41 a__isNat(length(L)) -> a__isNatList(L) 29.13/9.41 a__isNatIList(zeros) -> tt 29.13/9.41 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__isNatList(nil) -> tt 29.13/9.41 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 29.13/9.41 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__zeros -> cons(0, zeros) 29.13/9.41 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 29.13/9.41 a__uTake1(tt) -> nil 29.13/9.41 a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) 29.13/9.41 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 29.13/9.41 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 29.13/9.41 a__uLength(tt, L) -> s(a__length(mark(L))) 29.13/9.41 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 29.13/9.41 mark(isNatIList(X)) -> a__isNatIList(X) 29.13/9.41 mark(isNatList(X)) -> a__isNatList(X) 29.13/9.41 mark(isNat(X)) -> a__isNat(X) 29.13/9.41 mark(length(X)) -> a__length(mark(X)) 29.13/9.41 mark(zeros) -> a__zeros 29.13/9.41 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 29.13/9.41 mark(uTake1(X)) -> a__uTake1(mark(X)) 29.13/9.41 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 29.13/9.41 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 29.13/9.41 mark(tt) -> tt 29.13/9.41 mark(0) -> 0 29.13/9.41 mark(s(X)) -> s(mark(X)) 29.13/9.41 mark(cons(X1, X2)) -> cons(mark(X1), X2) 29.13/9.41 mark(nil) -> nil 29.13/9.41 a__and(X1, X2) -> and(X1, X2) 29.13/9.41 a__isNatIList(X) -> isNatIList(X) 29.13/9.41 a__isNatList(X) -> isNatList(X) 29.13/9.41 a__isNat(X) -> isNat(X) 29.13/9.41 a__length(X) -> length(X) 29.13/9.41 a__zeros -> zeros 29.13/9.41 a__take(X1, X2) -> take(X1, X2) 29.13/9.41 a__uTake1(X) -> uTake1(X) 29.13/9.41 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 29.13/9.41 a__uLength(X1, X2) -> uLength(X1, X2) 29.13/9.41 29.13/9.41 S is empty. 29.13/9.41 Rewrite Strategy: FULL 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (3) DecreasingLoopProof (LOWER BOUND(ID)) 29.13/9.41 The following loop(s) give(s) rise to the lower bound Omega(n^1): 29.13/9.41 29.13/9.41 The rewrite sequence 29.13/9.41 29.13/9.41 a__isNat(s(N)) ->^+ a__isNat(N) 29.13/9.41 29.13/9.41 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 29.13/9.41 29.13/9.41 The pumping substitution is [N / s(N)]. 29.13/9.41 29.13/9.41 The result substitution is [ ]. 29.13/9.41 29.13/9.41 29.13/9.41 29.13/9.41 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (4) 29.13/9.41 Complex Obligation (BEST) 29.13/9.41 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (5) 29.13/9.41 Obligation: 29.13/9.41 Proved the lower bound n^1 for the following obligation: 29.13/9.41 29.13/9.41 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 29.13/9.41 29.13/9.41 29.13/9.41 The TRS R consists of the following rules: 29.13/9.41 29.13/9.41 a__and(tt, T) -> mark(T) 29.13/9.41 a__isNatIList(IL) -> a__isNatList(IL) 29.13/9.41 a__isNat(0) -> tt 29.13/9.41 a__isNat(s(N)) -> a__isNat(N) 29.13/9.41 a__isNat(length(L)) -> a__isNatList(L) 29.13/9.41 a__isNatIList(zeros) -> tt 29.13/9.41 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__isNatList(nil) -> tt 29.13/9.41 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 29.13/9.41 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__zeros -> cons(0, zeros) 29.13/9.41 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 29.13/9.41 a__uTake1(tt) -> nil 29.13/9.41 a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) 29.13/9.41 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 29.13/9.41 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 29.13/9.41 a__uLength(tt, L) -> s(a__length(mark(L))) 29.13/9.41 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 29.13/9.41 mark(isNatIList(X)) -> a__isNatIList(X) 29.13/9.41 mark(isNatList(X)) -> a__isNatList(X) 29.13/9.41 mark(isNat(X)) -> a__isNat(X) 29.13/9.41 mark(length(X)) -> a__length(mark(X)) 29.13/9.41 mark(zeros) -> a__zeros 29.13/9.41 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 29.13/9.41 mark(uTake1(X)) -> a__uTake1(mark(X)) 29.13/9.41 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 29.13/9.41 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 29.13/9.41 mark(tt) -> tt 29.13/9.41 mark(0) -> 0 29.13/9.41 mark(s(X)) -> s(mark(X)) 29.13/9.41 mark(cons(X1, X2)) -> cons(mark(X1), X2) 29.13/9.41 mark(nil) -> nil 29.13/9.41 a__and(X1, X2) -> and(X1, X2) 29.13/9.41 a__isNatIList(X) -> isNatIList(X) 29.13/9.41 a__isNatList(X) -> isNatList(X) 29.13/9.41 a__isNat(X) -> isNat(X) 29.13/9.41 a__length(X) -> length(X) 29.13/9.41 a__zeros -> zeros 29.13/9.41 a__take(X1, X2) -> take(X1, X2) 29.13/9.41 a__uTake1(X) -> uTake1(X) 29.13/9.41 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 29.13/9.41 a__uLength(X1, X2) -> uLength(X1, X2) 29.13/9.41 29.13/9.41 S is empty. 29.13/9.41 Rewrite Strategy: FULL 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (6) LowerBoundPropagationProof (FINISHED) 29.13/9.41 Propagated lower bound. 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (7) 29.13/9.41 BOUNDS(n^1, INF) 29.13/9.41 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (8) 29.13/9.41 Obligation: 29.13/9.41 Analyzing the following TRS for decreasing loops: 29.13/9.41 29.13/9.41 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 29.13/9.41 29.13/9.41 29.13/9.41 The TRS R consists of the following rules: 29.13/9.41 29.13/9.41 a__and(tt, T) -> mark(T) 29.13/9.41 a__isNatIList(IL) -> a__isNatList(IL) 29.13/9.41 a__isNat(0) -> tt 29.13/9.41 a__isNat(s(N)) -> a__isNat(N) 29.13/9.41 a__isNat(length(L)) -> a__isNatList(L) 29.13/9.41 a__isNatIList(zeros) -> tt 29.13/9.41 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__isNatList(nil) -> tt 29.13/9.41 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 29.13/9.41 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 29.13/9.41 a__zeros -> cons(0, zeros) 29.13/9.41 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 29.13/9.41 a__uTake1(tt) -> nil 29.13/9.41 a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) 29.13/9.41 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 29.13/9.41 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 29.13/9.41 a__uLength(tt, L) -> s(a__length(mark(L))) 29.13/9.41 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 29.13/9.41 mark(isNatIList(X)) -> a__isNatIList(X) 29.13/9.41 mark(isNatList(X)) -> a__isNatList(X) 29.13/9.41 mark(isNat(X)) -> a__isNat(X) 29.13/9.41 mark(length(X)) -> a__length(mark(X)) 29.13/9.41 mark(zeros) -> a__zeros 29.13/9.41 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 29.13/9.41 mark(uTake1(X)) -> a__uTake1(mark(X)) 29.13/9.41 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 29.13/9.41 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 29.13/9.41 mark(tt) -> tt 29.13/9.41 mark(0) -> 0 29.13/9.41 mark(s(X)) -> s(mark(X)) 29.13/9.41 mark(cons(X1, X2)) -> cons(mark(X1), X2) 29.13/9.41 mark(nil) -> nil 29.13/9.41 a__and(X1, X2) -> and(X1, X2) 29.13/9.41 a__isNatIList(X) -> isNatIList(X) 29.13/9.41 a__isNatList(X) -> isNatList(X) 29.13/9.41 a__isNat(X) -> isNat(X) 29.13/9.41 a__length(X) -> length(X) 29.13/9.41 a__zeros -> zeros 29.13/9.41 a__take(X1, X2) -> take(X1, X2) 29.13/9.41 a__uTake1(X) -> uTake1(X) 29.13/9.41 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 29.13/9.41 a__uLength(X1, X2) -> uLength(X1, X2) 29.13/9.41 29.13/9.41 S is empty. 29.13/9.41 Rewrite Strategy: FULL 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (9) DecreasingLoopProof (FINISHED) 29.13/9.41 The following loop(s) give(s) rise to the lower bound EXP: 29.13/9.41 29.13/9.41 The rewrite sequence 29.13/9.41 29.13/9.41 mark(take(s(X1_0), cons(X11_1, X22_1))) ->^+ a__uTake2(a__and(a__isNat(mark(X1_0)), a__and(a__isNat(mark(X11_1)), a__isNatIList(X22_1))), mark(X1_0), mark(X11_1), X22_1) 29.13/9.41 29.13/9.41 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0]. 29.13/9.41 29.13/9.41 The pumping substitution is [X1_0 / take(s(X1_0), cons(X11_1, X22_1))]. 29.13/9.41 29.13/9.41 The result substitution is [ ]. 29.13/9.41 29.13/9.41 29.13/9.41 29.13/9.41 The rewrite sequence 29.13/9.41 29.13/9.41 mark(take(s(X1_0), cons(X11_1, X22_1))) ->^+ a__uTake2(a__and(a__isNat(mark(X1_0)), a__and(a__isNat(mark(X11_1)), a__isNatIList(X22_1))), mark(X1_0), mark(X11_1), X22_1) 29.13/9.41 29.13/9.41 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 29.13/9.41 29.13/9.41 The pumping substitution is [X1_0 / take(s(X1_0), cons(X11_1, X22_1))]. 29.13/9.41 29.13/9.41 The result substitution is [ ]. 29.13/9.41 29.13/9.41 29.13/9.41 29.13/9.41 29.13/9.41 ---------------------------------------- 29.13/9.41 29.13/9.41 (10) 29.13/9.41 BOUNDS(EXP, INF) 29.19/9.46 EOF