TIMEOUT

The TRS could not be proven terminating. The proof attempt took 60039 ms.

The following DP Processors were used


Problem 1 was processed with processor DependencyGraph (1534ms).
 | – Problem 2 remains open; application of the following processors failed [SubtermCriterion (1ms), DependencyGraph (1298ms), PolynomialLinearRange4iUR (timeout), DependencyGraph (1014ms), PolynomialLinearRange8NegiUR (30032ms), DependencyGraph (timeout), ReductionPairSAT (timeout)].

The following open problems remain:



Open Dependency Pair Problem 2

Dependency Pairs

a__length#(cons(N, L))a__uLength#(a__and(a__isNat(N), a__isNatList(L)), L)a__uLength#(tt, L)mark#(L)
mark#(take(X1, X2))mark#(X1)mark#(isNat(X))a__isNat#(X)
a__take#(s(M), cons(N, IL))a__isNat#(M)mark#(isNatIList(X))a__isNatIList#(X)
a__isNat#(s(N))a__isNat#(N)a__isNatList#(cons(N, L))a__and#(a__isNat(N), a__isNatList(L))
a__isNatIList#(IL)a__isNatList#(IL)mark#(and(X1, X2))mark#(X2)
mark#(length(X))a__length#(mark(X))a__take#(s(M), cons(N, IL))a__isNatIList#(IL)
a__take#(s(M), cons(N, IL))a__isNat#(N)mark#(length(X))mark#(X)
mark#(uLength(X1, X2))a__uLength#(mark(X1), X2)mark#(and(X1, X2))a__and#(mark(X1), mark(X2))
a__take#(s(M), cons(N, IL))a__and#(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL)))mark#(s(X))mark#(X)
mark#(uLength(X1, X2))mark#(X1)a__take#(s(M), cons(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))
a__length#(cons(N, L))a__isNatList#(L)a__take#(0, IL)a__isNatIList#(IL)
a__uLength#(tt, L)a__length#(mark(L))a__isNatList#(cons(N, L))a__isNat#(N)
a__isNatList#(take(N, IL))a__isNat#(N)a__uTake2#(tt, M, N, IL)mark#(N)
a__isNatList#(take(N, IL))a__isNatIList#(IL)mark#(uTake2(X1, X2, X3, X4))a__uTake2#(mark(X1), X2, X3, X4)
mark#(cons(X1, X2))mark#(X1)mark#(uTake2(X1, X2, X3, X4))mark#(X1)
a__isNatList#(take(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))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)
a__length#(cons(N, L))a__isNat#(N)a__isNat#(length(L))a__isNatList#(L)
mark#(isNatList(X))a__isNatList#(X)mark#(uTake1(X))mark#(X)
mark#(and(X1, X2))mark#(X1)a__isNatIList#(cons(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))
a__isNatIList#(cons(N, IL))a__isNatIList#(IL)mark#(take(X1, X2))a__take#(mark(X1), mark(X2))
mark#(take(X1, X2))mark#(X2)a__isNatList#(cons(N, L))a__isNatList#(L)
a__isNatIList#(cons(N, IL))a__isNat#(N)a__and#(tt, T)mark#(T)
a__length#(cons(N, L))a__and#(a__isNat(N), a__isNatList(L))

Rewrite Rules

a__and(tt, T)mark(T)a__isNatIList(IL)a__isNatList(IL)
a__isNat(0)tta__isNat(s(N))a__isNat(N)
a__isNat(length(L))a__isNatList(L)a__isNatIList(zeros)tt
a__isNatIList(cons(N, IL))a__and(a__isNat(N), a__isNatIList(IL))a__isNatList(nil)tt
a__isNatList(cons(N, L))a__and(a__isNat(N), a__isNatList(L))a__isNatList(take(N, IL))a__and(a__isNat(N), a__isNatIList(IL))
a__zeroscons(0, zeros)a__take(0, IL)a__uTake1(a__isNatIList(IL))
a__uTake1(tt)nila__take(s(M), cons(N, IL))a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
a__uTake2(tt, M, N, IL)cons(mark(N), take(M, IL))a__length(cons(N, L))a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
a__uLength(tt, L)s(a__length(mark(L)))mark(and(X1, X2))a__and(mark(X1), mark(X2))
mark(isNatIList(X))a__isNatIList(X)mark(isNatList(X))a__isNatList(X)
mark(isNat(X))a__isNat(X)mark(length(X))a__length(mark(X))
mark(zeros)a__zerosmark(take(X1, X2))a__take(mark(X1), mark(X2))
mark(uTake1(X))a__uTake1(mark(X))mark(uTake2(X1, X2, X3, X4))a__uTake2(mark(X1), X2, X3, X4)
mark(uLength(X1, X2))a__uLength(mark(X1), X2)mark(tt)tt
mark(0)0mark(s(X))s(mark(X))
mark(cons(X1, X2))cons(mark(X1), X2)mark(nil)nil
a__and(X1, X2)and(X1, X2)a__isNatIList(X)isNatIList(X)
a__isNatList(X)isNatList(X)a__isNat(X)isNat(X)
a__length(X)length(X)a__zeroszeros
a__take(X1, X2)take(X1, X2)a__uTake1(X)uTake1(X)
a__uTake2(X1, X2, X3, X4)uTake2(X1, X2, X3, X4)a__uLength(X1, X2)uLength(X1, X2)

Original Signature

Termination of terms over the following signature is verified: a__take, a__and, isNat, a__isNatList, length, cons, a__zeros, isNatIList, uLength, a__length, mark, a__uLength, and, uTake1, 0, uTake2, s, a__isNatIList, a__uTake1, isNatList, zeros, tt, a__uTake2, take, a__isNat, nil


Problem 1: DependencyGraph



Dependency Pair Problem

Dependency Pairs

a__length#(cons(N, L))a__uLength#(a__and(a__isNat(N), a__isNatList(L)), L)a__uLength#(tt, L)mark#(L)
mark#(isNat(X))a__isNat#(X)mark#(take(X1, X2))mark#(X1)
a__take#(s(M), cons(N, IL))a__isNat#(M)mark#(isNatIList(X))a__isNatIList#(X)
a__isNat#(s(N))a__isNat#(N)mark#(zeros)a__zeros#
a__isNatList#(cons(N, L))a__and#(a__isNat(N), a__isNatList(L))mark#(uTake1(X))a__uTake1#(mark(X))
a__isNatIList#(IL)a__isNatList#(IL)mark#(and(X1, X2))mark#(X2)
mark#(length(X))a__length#(mark(X))a__take#(s(M), cons(N, IL))a__isNat#(N)
a__take#(s(M), cons(N, IL))a__isNatIList#(IL)a__take#(0, IL)a__uTake1#(a__isNatIList(IL))
mark#(uLength(X1, X2))a__uLength#(mark(X1), X2)mark#(length(X))mark#(X)
mark#(and(X1, X2))a__and#(mark(X1), mark(X2))a__take#(s(M), cons(N, IL))a__and#(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL)))
mark#(s(X))mark#(X)mark#(uLength(X1, X2))mark#(X1)
a__take#(s(M), cons(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))a__length#(cons(N, L))a__isNatList#(L)
a__take#(0, IL)a__isNatIList#(IL)a__isNatList#(cons(N, L))a__isNat#(N)
a__uLength#(tt, L)a__length#(mark(L))a__isNatList#(take(N, IL))a__isNat#(N)
a__uTake2#(tt, M, N, IL)mark#(N)a__isNatList#(take(N, IL))a__isNatIList#(IL)
mark#(uTake2(X1, X2, X3, X4))a__uTake2#(mark(X1), X2, X3, X4)mark#(cons(X1, X2))mark#(X1)
mark#(uTake2(X1, X2, X3, X4))mark#(X1)a__isNatList#(take(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))
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)a__length#(cons(N, L))a__isNat#(N)
a__isNat#(length(L))a__isNatList#(L)mark#(isNatList(X))a__isNatList#(X)
mark#(uTake1(X))mark#(X)mark#(and(X1, X2))mark#(X1)
a__isNatIList#(cons(N, IL))a__and#(a__isNat(N), a__isNatIList(IL))a__isNatIList#(cons(N, IL))a__isNatIList#(IL)
mark#(take(X1, X2))a__take#(mark(X1), mark(X2))mark#(take(X1, X2))mark#(X2)
a__isNatList#(cons(N, L))a__isNatList#(L)a__and#(tt, T)mark#(T)
a__isNatIList#(cons(N, IL))a__isNat#(N)a__length#(cons(N, L))a__and#(a__isNat(N), a__isNatList(L))

Rewrite Rules

a__and(tt, T)mark(T)a__isNatIList(IL)a__isNatList(IL)
a__isNat(0)tta__isNat(s(N))a__isNat(N)
a__isNat(length(L))a__isNatList(L)a__isNatIList(zeros)tt
a__isNatIList(cons(N, IL))a__and(a__isNat(N), a__isNatIList(IL))a__isNatList(nil)tt
a__isNatList(cons(N, L))a__and(a__isNat(N), a__isNatList(L))a__isNatList(take(N, IL))a__and(a__isNat(N), a__isNatIList(IL))
a__zeroscons(0, zeros)a__take(0, IL)a__uTake1(a__isNatIList(IL))
a__uTake1(tt)nila__take(s(M), cons(N, IL))a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
a__uTake2(tt, M, N, IL)cons(mark(N), take(M, IL))a__length(cons(N, L))a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
a__uLength(tt, L)s(a__length(mark(L)))mark(and(X1, X2))a__and(mark(X1), mark(X2))
mark(isNatIList(X))a__isNatIList(X)mark(isNatList(X))a__isNatList(X)
mark(isNat(X))a__isNat(X)mark(length(X))a__length(mark(X))
mark(zeros)a__zerosmark(take(X1, X2))a__take(mark(X1), mark(X2))
mark(uTake1(X))a__uTake1(mark(X))mark(uTake2(X1, X2, X3, X4))a__uTake2(mark(X1), X2, X3, X4)
mark(uLength(X1, X2))a__uLength(mark(X1), X2)mark(tt)tt
mark(0)0mark(s(X))s(mark(X))
mark(cons(X1, X2))cons(mark(X1), X2)mark(nil)nil
a__and(X1, X2)and(X1, X2)a__isNatIList(X)isNatIList(X)
a__isNatList(X)isNatList(X)a__isNat(X)isNat(X)
a__length(X)length(X)a__zeroszeros
a__take(X1, X2)take(X1, X2)a__uTake1(X)uTake1(X)
a__uTake2(X1, X2, X3, X4)uTake2(X1, X2, X3, X4)a__uLength(X1, X2)uLength(X1, X2)

Original Signature

Termination of terms over the following signature is verified: a__take, a__and, isNat, a__isNatList, length, cons, a__zeros, isNatIList, uLength, a__length, mark, a__uLength, and, uTake1, 0, uTake2, s, a__isNatIList, a__uTake1, isNatList, zeros, tt, a__uTake2, take, a__isNat, nil

Strategy


The following SCCs where found

mark#(isNat(X)) → a__isNat#(X)mark#(take(X1, X2)) → mark#(X1)
a__uLength#(tt, L) → mark#(L)a__length#(cons(N, L)) → a__uLength#(a__and(a__isNat(N), a__isNatList(L)), L)
mark#(isNatIList(X)) → a__isNatIList#(X)a__take#(s(M), cons(N, IL)) → a__isNat#(M)
a__isNat#(s(N)) → a__isNat#(N)a__isNatList#(cons(N, L)) → a__and#(a__isNat(N), a__isNatList(L))
a__isNatIList#(IL) → a__isNatList#(IL)mark#(and(X1, X2)) → mark#(X2)
mark#(length(X)) → a__length#(mark(X))a__take#(s(M), cons(N, IL)) → a__isNat#(N)
a__take#(s(M), cons(N, IL)) → a__isNatIList#(IL)mark#(and(X1, X2)) → a__and#(mark(X1), mark(X2))
mark#(uLength(X1, X2)) → a__uLength#(mark(X1), X2)mark#(length(X)) → mark#(X)
a__take#(s(M), cons(N, IL)) → a__and#(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL)))mark#(s(X)) → mark#(X)
a__take#(s(M), cons(N, IL)) → a__and#(a__isNat(N), a__isNatIList(IL))mark#(uLength(X1, X2)) → mark#(X1)
a__length#(cons(N, L)) → a__isNatList#(L)a__take#(0, IL) → a__isNatIList#(IL)
a__isNatList#(cons(N, L)) → a__isNat#(N)a__uLength#(tt, L) → a__length#(mark(L))
a__isNatList#(take(N, IL)) → a__isNat#(N)a__isNatList#(take(N, IL)) → a__isNatIList#(IL)
a__uTake2#(tt, M, N, IL) → mark#(N)mark#(uTake2(X1, X2, X3, X4)) → a__uTake2#(mark(X1), X2, X3, X4)
mark#(cons(X1, X2)) → mark#(X1)mark#(uTake2(X1, X2, X3, X4)) → mark#(X1)
a__isNatList#(take(N, IL)) → a__and#(a__isNat(N), a__isNatIList(IL))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)
a__isNat#(length(L)) → a__isNatList#(L)a__length#(cons(N, L)) → a__isNat#(N)
mark#(uTake1(X)) → mark#(X)mark#(isNatList(X)) → a__isNatList#(X)
mark#(and(X1, X2)) → mark#(X1)a__isNatIList#(cons(N, IL)) → a__and#(a__isNat(N), a__isNatIList(IL))
a__isNatIList#(cons(N, IL)) → a__isNatIList#(IL)mark#(take(X1, X2)) → a__take#(mark(X1), mark(X2))
mark#(take(X1, X2)) → mark#(X2)a__isNatList#(cons(N, L)) → a__isNatList#(L)
a__and#(tt, T) → mark#(T)a__isNatIList#(cons(N, IL)) → a__isNat#(N)
a__length#(cons(N, L)) → a__and#(a__isNat(N), a__isNatList(L))