TIMEOUT

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

The following DP Processors were used


Problem 1 was processed with processor DependencyGraph (873ms).
 | – Problem 2 remains open; application of the following processors failed [SubtermCriterion (1ms), DependencyGraph (635ms), PolynomialLinearRange4iUR (timeout), PolynomialLinearRange4iUR (-3ms), PolynomialLinearRange8NegiUR (30000ms), DependencyGraph (timeout), ReductionPairSAT (14356ms), DependencyGraph (461ms), SizeChangePrinciple (timeout)].

The following open problems remain:



Open Dependency Pair Problem 2

Dependency Pairs

a__sel#(0, cons(X, Y))mark#(X)mark#(dbls(X))mark#(X)
a__sel#(s(X), cons(Y, Z))mark#(Z)a__quote#(sel(X, Y))mark#(X)
a__quote#(dbl(X))mark#(X)mark#(quote(X))a__quote#(mark(X))
mark#(quote(X))mark#(X)mark#(sel(X1, X2))mark#(X2)
a__sel1#(0, cons(X, Y))mark#(X)a__quote#(s(X))mark#(X)
mark#(sel(X1, X2))mark#(X1)mark#(sel1(X1, X2))a__sel1#(mark(X1), mark(X2))
a__quote#(dbl(X))a__dbl1#(mark(X))mark#(dbl1(X))mark#(X)
a__sel1#(s(X), cons(Y, Z))mark#(Z)a__sel#(s(X), cons(Y, Z))a__sel#(mark(X), mark(Z))
mark#(sel1(X1, X2))mark#(X2)mark#(dbl1(X))a__dbl1#(mark(X))
a__sel1#(s(X), cons(Y, Z))mark#(X)mark#(indx(X1, X2))mark#(X1)
mark#(dbl(X))mark#(X)a__sel1#(s(X), cons(Y, Z))a__sel1#(mark(X), mark(Z))
mark#(s1(X))mark#(X)a__quote#(s(X))a__quote#(mark(X))
mark#(sel(X1, X2))a__sel#(mark(X1), mark(X2))a__dbl1#(s(X))mark#(X)
a__dbl1#(s(X))a__dbl1#(mark(X))a__quote#(sel(X, Y))a__sel1#(mark(X), mark(Y))
mark#(sel1(X1, X2))mark#(X1)a__sel#(s(X), cons(Y, Z))mark#(X)
a__quote#(sel(X, Y))mark#(Y)

Rewrite Rules

a__dbl(0)0a__dbl(s(X))s(s(dbl(X)))
a__dbls(nil)nila__dbls(cons(X, Y))cons(dbl(X), dbls(Y))
a__sel(0, cons(X, Y))mark(X)a__sel(s(X), cons(Y, Z))a__sel(mark(X), mark(Z))
a__indx(nil, X)nila__indx(cons(X, Y), Z)cons(sel(X, Z), indx(Y, Z))
a__from(X)cons(X, from(s(X)))a__dbl1(0)01
a__dbl1(s(X))s1(s1(a__dbl1(mark(X))))a__sel1(0, cons(X, Y))mark(X)
a__sel1(s(X), cons(Y, Z))a__sel1(mark(X), mark(Z))a__quote(0)01
a__quote(s(X))s1(a__quote(mark(X)))a__quote(dbl(X))a__dbl1(mark(X))
a__quote(sel(X, Y))a__sel1(mark(X), mark(Y))mark(dbl(X))a__dbl(mark(X))
mark(dbls(X))a__dbls(mark(X))mark(sel(X1, X2))a__sel(mark(X1), mark(X2))
mark(indx(X1, X2))a__indx(mark(X1), X2)mark(from(X))a__from(X)
mark(dbl1(X))a__dbl1(mark(X))mark(sel1(X1, X2))a__sel1(mark(X1), mark(X2))
mark(quote(X))a__quote(mark(X))mark(0)0
mark(s(X))s(X)mark(nil)nil
mark(cons(X1, X2))cons(X1, X2)mark(01)01
mark(s1(X))s1(mark(X))a__dbl(X)dbl(X)
a__dbls(X)dbls(X)a__sel(X1, X2)sel(X1, X2)
a__indx(X1, X2)indx(X1, X2)a__from(X)from(X)
a__dbl1(X)dbl1(X)a__sel1(X1, X2)sel1(X1, X2)
a__quote(X)quote(X)

Original Signature

Termination of terms over the following signature is verified: a__sel1, a__dbl1, s1, dbl1, dbl, mark, from, 01, dbls, 0, sel1, a__dbl, s, indx, quote, a__dbls, a__sel, a__indx, sel, a__from, a__quote, nil, cons


Problem 1: DependencyGraph



Dependency Pair Problem

Dependency Pairs

a__sel#(0, cons(X, Y))mark#(X)mark#(dbls(X))mark#(X)
a__sel#(s(X), cons(Y, Z))mark#(Z)a__quote#(sel(X, Y))mark#(X)
mark#(from(X))a__from#(X)a__quote#(dbl(X))mark#(X)
mark#(dbl(X))a__dbl#(mark(X))mark#(quote(X))a__quote#(mark(X))
mark#(quote(X))mark#(X)mark#(indx(X1, X2))a__indx#(mark(X1), X2)
mark#(sel(X1, X2))mark#(X2)a__sel1#(0, cons(X, Y))mark#(X)
a__quote#(s(X))mark#(X)mark#(sel(X1, X2))mark#(X1)
mark#(sel1(X1, X2))a__sel1#(mark(X1), mark(X2))mark#(dbl1(X))mark#(X)
a__quote#(dbl(X))a__dbl1#(mark(X))a__sel1#(s(X), cons(Y, Z))mark#(Z)
a__sel#(s(X), cons(Y, Z))a__sel#(mark(X), mark(Z))mark#(sel1(X1, X2))mark#(X2)
mark#(dbl1(X))a__dbl1#(mark(X))a__sel1#(s(X), cons(Y, Z))mark#(X)
mark#(indx(X1, X2))mark#(X1)mark#(dbl(X))mark#(X)
a__sel1#(s(X), cons(Y, Z))a__sel1#(mark(X), mark(Z))mark#(s1(X))mark#(X)
a__quote#(s(X))a__quote#(mark(X))mark#(sel(X1, X2))a__sel#(mark(X1), mark(X2))
a__dbl1#(s(X))mark#(X)mark#(dbls(X))a__dbls#(mark(X))
a__quote#(sel(X, Y))a__sel1#(mark(X), mark(Y))a__dbl1#(s(X))a__dbl1#(mark(X))
a__sel#(s(X), cons(Y, Z))mark#(X)mark#(sel1(X1, X2))mark#(X1)
a__quote#(sel(X, Y))mark#(Y)

Rewrite Rules

a__dbl(0)0a__dbl(s(X))s(s(dbl(X)))
a__dbls(nil)nila__dbls(cons(X, Y))cons(dbl(X), dbls(Y))
a__sel(0, cons(X, Y))mark(X)a__sel(s(X), cons(Y, Z))a__sel(mark(X), mark(Z))
a__indx(nil, X)nila__indx(cons(X, Y), Z)cons(sel(X, Z), indx(Y, Z))
a__from(X)cons(X, from(s(X)))a__dbl1(0)01
a__dbl1(s(X))s1(s1(a__dbl1(mark(X))))a__sel1(0, cons(X, Y))mark(X)
a__sel1(s(X), cons(Y, Z))a__sel1(mark(X), mark(Z))a__quote(0)01
a__quote(s(X))s1(a__quote(mark(X)))a__quote(dbl(X))a__dbl1(mark(X))
a__quote(sel(X, Y))a__sel1(mark(X), mark(Y))mark(dbl(X))a__dbl(mark(X))
mark(dbls(X))a__dbls(mark(X))mark(sel(X1, X2))a__sel(mark(X1), mark(X2))
mark(indx(X1, X2))a__indx(mark(X1), X2)mark(from(X))a__from(X)
mark(dbl1(X))a__dbl1(mark(X))mark(sel1(X1, X2))a__sel1(mark(X1), mark(X2))
mark(quote(X))a__quote(mark(X))mark(0)0
mark(s(X))s(X)mark(nil)nil
mark(cons(X1, X2))cons(X1, X2)mark(01)01
mark(s1(X))s1(mark(X))a__dbl(X)dbl(X)
a__dbls(X)dbls(X)a__sel(X1, X2)sel(X1, X2)
a__indx(X1, X2)indx(X1, X2)a__from(X)from(X)
a__dbl1(X)dbl1(X)a__sel1(X1, X2)sel1(X1, X2)
a__quote(X)quote(X)

Original Signature

Termination of terms over the following signature is verified: a__sel1, a__dbl1, s1, dbl1, dbl, mark, from, 01, dbls, 0, indx, sel1, a__dbl, s, quote, a__dbls, a__indx, a__sel, sel, a__from, cons, nil, a__quote

Strategy


The following SCCs where found

a__sel#(0, cons(X, Y)) → mark#(X)mark#(dbls(X)) → mark#(X)
a__sel#(s(X), cons(Y, Z)) → mark#(Z)a__quote#(sel(X, Y)) → mark#(X)
a__quote#(dbl(X)) → mark#(X)mark#(quote(X)) → a__quote#(mark(X))
mark#(quote(X)) → mark#(X)mark#(sel(X1, X2)) → mark#(X2)
a__sel1#(0, cons(X, Y)) → mark#(X)a__quote#(s(X)) → mark#(X)
mark#(sel(X1, X2)) → mark#(X1)mark#(sel1(X1, X2)) → a__sel1#(mark(X1), mark(X2))
mark#(dbl1(X)) → mark#(X)a__quote#(dbl(X)) → a__dbl1#(mark(X))
a__sel1#(s(X), cons(Y, Z)) → mark#(Z)a__sel#(s(X), cons(Y, Z)) → a__sel#(mark(X), mark(Z))
a__sel1#(s(X), cons(Y, Z)) → mark#(X)mark#(dbl1(X)) → a__dbl1#(mark(X))
mark#(sel1(X1, X2)) → mark#(X2)mark#(indx(X1, X2)) → mark#(X1)
mark#(dbl(X)) → mark#(X)mark#(s1(X)) → mark#(X)
a__sel1#(s(X), cons(Y, Z)) → a__sel1#(mark(X), mark(Z))a__quote#(s(X)) → a__quote#(mark(X))
mark#(sel(X1, X2)) → a__sel#(mark(X1), mark(X2))a__dbl1#(s(X)) → mark#(X)
a__quote#(sel(X, Y)) → a__sel1#(mark(X), mark(Y))a__dbl1#(s(X)) → a__dbl1#(mark(X))
a__sel#(s(X), cons(Y, Z)) → mark#(X)mark#(sel1(X1, X2)) → mark#(X1)
a__quote#(sel(X, Y)) → mark#(Y)