Term Rewriting System R:
[X, Y, Z, X1, X2]
af(X) -> cons(mark(X), f(g(X)))
af(X) -> f(X)
ag(0) -> s(0)
ag(s(X)) -> s(s(ag(mark(X))))
ag(X) -> g(X)
asel(0, cons(X, Y)) -> mark(X)
asel(s(X), cons(Y, Z)) -> asel(mark(X), mark(Z))
asel(X1, X2) -> sel(X1, X2)
mark(f(X)) -> af(mark(X))
mark(g(X)) -> ag(mark(X))
mark(sel(X1, X2)) -> asel(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0) -> 0
mark(s(X)) -> s(mark(X))

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

AF(X) -> MARK(X)
AG(s(X)) -> AG(mark(X))
AG(s(X)) -> MARK(X)
ASEL(0, cons(X, Y)) -> MARK(X)
ASEL(s(X), cons(Y, Z)) -> ASEL(mark(X), mark(Z))
ASEL(s(X), cons(Y, Z)) -> MARK(X)
ASEL(s(X), cons(Y, Z)) -> MARK(Z)
MARK(f(X)) -> AF(mark(X))
MARK(f(X)) -> MARK(X)
MARK(g(X)) -> AG(mark(X))
MARK(g(X)) -> MARK(X)
MARK(sel(X1, X2)) -> ASEL(mark(X1), mark(X2))
MARK(sel(X1, X2)) -> MARK(X1)
MARK(sel(X1, X2)) -> MARK(X2)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(s(X)) -> MARK(X)

Furthermore, R contains one SCC.


   R
DPs
       →DP Problem 1
Remaining Obligation(s)




The following remains to be proven:
Dependency Pairs:

ASEL(s(X), cons(Y, Z)) -> MARK(Z)
ASEL(s(X), cons(Y, Z)) -> MARK(X)
ASEL(s(X), cons(Y, Z)) -> ASEL(mark(X), mark(Z))
MARK(s(X)) -> MARK(X)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(sel(X1, X2)) -> MARK(X2)
MARK(sel(X1, X2)) -> MARK(X1)
ASEL(0, cons(X, Y)) -> MARK(X)
MARK(sel(X1, X2)) -> ASEL(mark(X1), mark(X2))
MARK(g(X)) -> MARK(X)
AG(s(X)) -> MARK(X)
AG(s(X)) -> AG(mark(X))
MARK(g(X)) -> AG(mark(X))
MARK(f(X)) -> MARK(X)
MARK(f(X)) -> AF(mark(X))
AF(X) -> MARK(X)


Rules:


af(X) -> cons(mark(X), f(g(X)))
af(X) -> f(X)
ag(0) -> s(0)
ag(s(X)) -> s(s(ag(mark(X))))
ag(X) -> g(X)
asel(0, cons(X, Y)) -> mark(X)
asel(s(X), cons(Y, Z)) -> asel(mark(X), mark(Z))
asel(X1, X2) -> sel(X1, X2)
mark(f(X)) -> af(mark(X))
mark(g(X)) -> ag(mark(X))
mark(sel(X1, X2)) -> asel(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0) -> 0
mark(s(X)) -> s(mark(X))




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