Term Rewriting System R:
[X, Y, Z, X1, X2]
dbl(0) -> 0
dbl(s(X)) -> s(ns(ndbl(activate(X))))
dbl(X) -> ndbl(X)
dbls(nil) -> nil
dbls(cons(X, Y)) -> cons(ndbl(activate(X)), ndbls(activate(Y)))
dbls(X) -> ndbls(X)
sel(0, cons(X, Y)) -> activate(X)
sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z))
sel(X1, X2) -> nsel(X1, X2)
indx(nil, X) -> nil
indx(cons(X, Y), Z) -> cons(nsel(activate(X), activate(Z)), nindx(activate(Y), activate(Z)))
indx(X1, X2) -> nindx(X1, X2)
from(X) -> cons(activate(X), nfrom(ns(activate(X))))
from(X) -> nfrom(X)
s(X) -> ns(X)
activate(ns(X)) -> s(X)
activate(ndbl(X)) -> dbl(X)
activate(ndbls(X)) -> dbls(X)
activate(nsel(X1, X2)) -> sel(X1, X2)
activate(nindx(X1, X2)) -> indx(X1, X2)
activate(nfrom(X)) -> from(X)
activate(X) -> X

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

DBL(s(X)) -> S(ns(ndbl(activate(X))))
DBL(s(X)) -> ACTIVATE(X)
DBLS(cons(X, Y)) -> ACTIVATE(X)
DBLS(cons(X, Y)) -> ACTIVATE(Y)
SEL(0, cons(X, Y)) -> ACTIVATE(X)
SEL(s(X), cons(Y, Z)) -> SEL(activate(X), activate(Z))
SEL(s(X), cons(Y, Z)) -> ACTIVATE(X)
SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z)
INDX(cons(X, Y), Z) -> ACTIVATE(X)
INDX(cons(X, Y), Z) -> ACTIVATE(Z)
INDX(cons(X, Y), Z) -> ACTIVATE(Y)
FROM(X) -> ACTIVATE(X)
ACTIVATE(ns(X)) -> S(X)
ACTIVATE(ndbl(X)) -> DBL(X)
ACTIVATE(ndbls(X)) -> DBLS(X)
ACTIVATE(nsel(X1, X2)) -> SEL(X1, X2)
ACTIVATE(nindx(X1, X2)) -> INDX(X1, X2)
ACTIVATE(nfrom(X)) -> FROM(X)

Furthermore, R contains one SCC.


   R
DPs
       →DP Problem 1
Narrowing Transformation


Dependency Pairs:

DBLS(cons(X, Y)) -> ACTIVATE(Y)
SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z)
SEL(s(X), cons(Y, Z)) -> ACTIVATE(X)
SEL(s(X), cons(Y, Z)) -> SEL(activate(X), activate(Z))
INDX(cons(X, Y), Z) -> ACTIVATE(Y)
INDX(cons(X, Y), Z) -> ACTIVATE(Z)
FROM(X) -> ACTIVATE(X)
ACTIVATE(nfrom(X)) -> FROM(X)
INDX(cons(X, Y), Z) -> ACTIVATE(X)
ACTIVATE(nindx(X1, X2)) -> INDX(X1, X2)
SEL(0, cons(X, Y)) -> ACTIVATE(X)
ACTIVATE(nsel(X1, X2)) -> SEL(X1, X2)
DBLS(cons(X, Y)) -> ACTIVATE(X)
ACTIVATE(ndbls(X)) -> DBLS(X)
ACTIVATE(ndbl(X)) -> DBL(X)
DBL(s(X)) -> ACTIVATE(X)


Rules:


dbl(0) -> 0
dbl(s(X)) -> s(ns(ndbl(activate(X))))
dbl(X) -> ndbl(X)
dbls(nil) -> nil
dbls(cons(X, Y)) -> cons(ndbl(activate(X)), ndbls(activate(Y)))
dbls(X) -> ndbls(X)
sel(0, cons(X, Y)) -> activate(X)
sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z))
sel(X1, X2) -> nsel(X1, X2)
indx(nil, X) -> nil
indx(cons(X, Y), Z) -> cons(nsel(activate(X), activate(Z)), nindx(activate(Y), activate(Z)))
indx(X1, X2) -> nindx(X1, X2)
from(X) -> cons(activate(X), nfrom(ns(activate(X))))
from(X) -> nfrom(X)
s(X) -> ns(X)
activate(ns(X)) -> s(X)
activate(ndbl(X)) -> dbl(X)
activate(ndbls(X)) -> dbls(X)
activate(nsel(X1, X2)) -> sel(X1, X2)
activate(nindx(X1, X2)) -> indx(X1, X2)
activate(nfrom(X)) -> from(X)
activate(X) -> X





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

SEL(s(X), cons(Y, Z)) -> SEL(activate(X), activate(Z))
14 new Dependency Pairs are created:

SEL(s(ns(X'')), cons(Y, Z)) -> SEL(s(X''), activate(Z))
SEL(s(ndbl(X'')), cons(Y, Z)) -> SEL(dbl(X''), activate(Z))
SEL(s(ndbls(X'')), cons(Y, Z)) -> SEL(dbls(X''), activate(Z))
SEL(s(nsel(X1', X2')), cons(Y, Z)) -> SEL(sel(X1', X2'), activate(Z))
SEL(s(nindx(X1', X2')), cons(Y, Z)) -> SEL(indx(X1', X2'), activate(Z))
SEL(s(nfrom(X'')), cons(Y, Z)) -> SEL(from(X''), activate(Z))
SEL(s(X''), cons(Y, Z)) -> SEL(X'', activate(Z))
SEL(s(X), cons(Y, ns(X''))) -> SEL(activate(X), s(X''))
SEL(s(X), cons(Y, ndbl(X''))) -> SEL(activate(X), dbl(X''))
SEL(s(X), cons(Y, ndbls(X''))) -> SEL(activate(X), dbls(X''))
SEL(s(X), cons(Y, nsel(X1', X2'))) -> SEL(activate(X), sel(X1', X2'))
SEL(s(X), cons(Y, nindx(X1', X2'))) -> SEL(activate(X), indx(X1', X2'))
SEL(s(X), cons(Y, nfrom(X''))) -> SEL(activate(X), from(X''))
SEL(s(X), cons(Y, Z')) -> SEL(activate(X), Z')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Remaining Obligation(s)




The following remains to be proven:
Dependency Pairs:

SEL(s(X), cons(Y, Z')) -> SEL(activate(X), Z')
SEL(s(X), cons(Y, nfrom(X''))) -> SEL(activate(X), from(X''))
SEL(s(X), cons(Y, nindx(X1', X2'))) -> SEL(activate(X), indx(X1', X2'))
SEL(s(X), cons(Y, nsel(X1', X2'))) -> SEL(activate(X), sel(X1', X2'))
SEL(s(X), cons(Y, ndbls(X''))) -> SEL(activate(X), dbls(X''))
SEL(s(X), cons(Y, ndbl(X''))) -> SEL(activate(X), dbl(X''))
SEL(s(X), cons(Y, ns(X''))) -> SEL(activate(X), s(X''))
SEL(s(X''), cons(Y, Z)) -> SEL(X'', activate(Z))
SEL(s(nfrom(X'')), cons(Y, Z)) -> SEL(from(X''), activate(Z))
SEL(s(nindx(X1', X2')), cons(Y, Z)) -> SEL(indx(X1', X2'), activate(Z))
SEL(s(nsel(X1', X2')), cons(Y, Z)) -> SEL(sel(X1', X2'), activate(Z))
SEL(s(ndbls(X'')), cons(Y, Z)) -> SEL(dbls(X''), activate(Z))
SEL(s(ndbl(X'')), cons(Y, Z)) -> SEL(dbl(X''), activate(Z))
SEL(s(ns(X'')), cons(Y, Z)) -> SEL(s(X''), activate(Z))
SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z)
SEL(s(X), cons(Y, Z)) -> ACTIVATE(X)
INDX(cons(X, Y), Z) -> ACTIVATE(Y)
INDX(cons(X, Y), Z) -> ACTIVATE(Z)
FROM(X) -> ACTIVATE(X)
ACTIVATE(nfrom(X)) -> FROM(X)
INDX(cons(X, Y), Z) -> ACTIVATE(X)
ACTIVATE(nindx(X1, X2)) -> INDX(X1, X2)
SEL(0, cons(X, Y)) -> ACTIVATE(X)
ACTIVATE(nsel(X1, X2)) -> SEL(X1, X2)
DBLS(cons(X, Y)) -> ACTIVATE(X)
ACTIVATE(ndbls(X)) -> DBLS(X)
DBL(s(X)) -> ACTIVATE(X)
ACTIVATE(ndbl(X)) -> DBL(X)
DBLS(cons(X, Y)) -> ACTIVATE(Y)


Rules:


dbl(0) -> 0
dbl(s(X)) -> s(ns(ndbl(activate(X))))
dbl(X) -> ndbl(X)
dbls(nil) -> nil
dbls(cons(X, Y)) -> cons(ndbl(activate(X)), ndbls(activate(Y)))
dbls(X) -> ndbls(X)
sel(0, cons(X, Y)) -> activate(X)
sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z))
sel(X1, X2) -> nsel(X1, X2)
indx(nil, X) -> nil
indx(cons(X, Y), Z) -> cons(nsel(activate(X), activate(Z)), nindx(activate(Y), activate(Z)))
indx(X1, X2) -> nindx(X1, X2)
from(X) -> cons(activate(X), nfrom(ns(activate(X))))
from(X) -> nfrom(X)
s(X) -> ns(X)
activate(ns(X)) -> s(X)
activate(ndbl(X)) -> dbl(X)
activate(ndbls(X)) -> dbls(X)
activate(nsel(X1, X2)) -> sel(X1, X2)
activate(nindx(X1, X2)) -> indx(X1, X2)
activate(nfrom(X)) -> from(X)
activate(X) -> X




Termination of R could not be shown.
Duration:
0:06 minutes