YES
The TRS could be proven terminating. The proof took 46864 ms.
The following DP Processors were used
Problem 1 was processed with processor DependencyGraph (588ms).
| – Problem 2 was processed with processor PolynomialLinearRange4iUR (706ms).
| | – Problem 6 was processed with processor DependencyGraph (0ms).
| – Problem 3 was processed with processor PolynomialLinearRange4 (158ms).
| | – Problem 7 was processed with processor DependencyGraph (7ms).
| | | – Problem 8 was processed with processor PolynomialLinearRange4 (137ms).
| | | | – Problem 9 was processed with processor DependencyGraph (2ms).
| – Problem 4 was processed with processor SubtermCriterion (23ms).
| – Problem 5 was processed with processor SubtermCriterion (8ms).
Problem 1: DependencyGraph
Dependency Pair Problem
Dependency Pairs
| isNeList#(n____(V1, V2)) | → | U41#(isList(activate(V1)), activate(V2)) | | isNeList#(n____(V1, V2)) | → | U51#(isNeList(activate(V1)), activate(V2)) |
| activate#(n__o) | → | o# | | isNePal#(n____(I, n____(P, I))) | → | activate#(I) |
| activate#(n____(X1, X2)) | → | activate#(X2) | | isList#(V) | → | U11#(isNeList(activate(V))) |
| isNeList#(n____(V1, V2)) | → | isList#(activate(V1)) | | isList#(n____(V1, V2)) | → | U21#(isList(activate(V1)), activate(V2)) |
| activate#(n__a) | → | a# | | isNePal#(n____(I, n____(P, I))) | → | isQid#(activate(I)) |
| U21#(tt, V2) | → | U22#(isList(activate(V2))) | | isNeList#(n____(V1, V2)) | → | activate#(V1) |
| U51#(tt, V2) | → | activate#(V2) | | U71#(tt, P) | → | isPal#(activate(P)) |
| U41#(tt, V2) | → | U42#(isNeList(activate(V2))) | | isPal#(V) | → | isNePal#(activate(V)) |
| activate#(n__u) | → | u# | | activate#(n__e) | → | e# |
| isNeList#(V) | → | U31#(isQid(activate(V))) | | activate#(n__i) | → | i# |
| isNeList#(n____(V1, V2)) | → | activate#(V2) | | isPal#(V) | → | activate#(V) |
| U51#(tt, V2) | → | U52#(isList(activate(V2))) | | isNeList#(n____(V1, V2)) | → | isNeList#(activate(V1)) |
| isList#(n____(V1, V2)) | → | isList#(activate(V1)) | | isPal#(V) | → | U81#(isNePal(activate(V))) |
| isNePal#(n____(I, n____(P, I))) | → | activate#(P) | | isNePal#(V) | → | isQid#(activate(V)) |
| __#(__(X, Y), Z) | → | __#(Y, Z) | | isNePal#(V) | → | activate#(V) |
| activate#(n____(X1, X2)) | → | __#(activate(X1), activate(X2)) | | isList#(n____(V1, V2)) | → | activate#(V1) |
| U41#(tt, V2) | → | isNeList#(activate(V2)) | | isList#(n____(V1, V2)) | → | activate#(V2) |
| isNeList#(V) | → | activate#(V) | | U21#(tt, V2) | → | activate#(V2) |
| U41#(tt, V2) | → | activate#(V2) | | activate#(n____(X1, X2)) | → | activate#(X1) |
| isNePal#(V) | → | U61#(isQid(activate(V))) | | U21#(tt, V2) | → | isList#(activate(V2)) |
| U71#(tt, P) | → | U72#(isPal(activate(P))) | | __#(__(X, Y), Z) | → | __#(X, __(Y, Z)) |
| isNeList#(V) | → | isQid#(activate(V)) | | U71#(tt, P) | → | activate#(P) |
| activate#(n__nil) | → | nil# | | U51#(tt, V2) | → | isList#(activate(V2)) |
| isNePal#(n____(I, n____(P, I))) | → | U71#(isQid(activate(I)), activate(P)) | | isList#(V) | → | activate#(V) |
| isList#(V) | → | isNeList#(activate(V)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
The following SCCs where found
| activate#(n____(X1, X2)) → activate#(X1) | activate#(n____(X1, X2)) → activate#(X2) |
| U71#(tt, P) → isPal#(activate(P)) | isNePal#(n____(I, n____(P, I))) → U71#(isQid(activate(I)), activate(P)) |
| isPal#(V) → isNePal#(activate(V)) |
| __#(__(X, Y), Z) → __#(X, __(Y, Z)) | __#(__(X, Y), Z) → __#(Y, Z) |
| isList#(n____(V1, V2)) → U21#(isList(activate(V1)), activate(V2)) | isNeList#(n____(V1, V2)) → U41#(isList(activate(V1)), activate(V2)) |
| isNeList#(n____(V1, V2)) → U51#(isNeList(activate(V1)), activate(V2)) | U21#(tt, V2) → isList#(activate(V2)) |
| U51#(tt, V2) → isList#(activate(V2)) | isNeList#(n____(V1, V2)) → isNeList#(activate(V1)) |
| U41#(tt, V2) → isNeList#(activate(V2)) | isNeList#(n____(V1, V2)) → isList#(activate(V1)) |
| isList#(n____(V1, V2)) → isList#(activate(V1)) | isList#(V) → isNeList#(activate(V)) |
Problem 2: PolynomialLinearRange4iUR
Dependency Pair Problem
Dependency Pairs
| U71#(tt, P) | → | isPal#(activate(P)) | | isNePal#(n____(I, n____(P, I))) | → | U71#(isQid(activate(I)), activate(P)) |
| isPal#(V) | → | isNePal#(activate(V)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
Polynomial Interpretation
- U11(x): 0
- U21(x,y): 0
- U22(x): 0
- U31(x): 0
- U41(x,y): 0
- U42(x): 0
- U51(x,y): 0
- U52(x): 0
- U61(x): 0
- U71(x,y): 0
- U71#(x,y): y
- U72(x): 0
- U81(x): 0
- __(x,y): y + x + 1
- a: 0
- activate(x): x
- e: 0
- i: 3
- isList(x): 0
- isNeList(x): 0
- isNePal(x): 0
- isNePal#(x): x
- isPal(x): 0
- isPal#(x): x
- isQid(x): 0
- n____(x,y): y + x + 1
- n__a: 0
- n__e: 0
- n__i: 3
- n__nil: 0
- n__o: 0
- n__u: 0
- nil: 0
- o: 0
- tt: 0
- u: 0
Improved Usable rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| e | → | n__e | | activate(n__i) | → | i |
| a | → | n__a | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(X) | → | X |
| activate(n__u) | → | u | | __(nil, X) | → | X |
| i | → | n__i | | u | → | n__u |
| activate(n__o) | → | o | | __(X1, X2) | → | n____(X1, X2) |
| nil | → | n__nil | | o | → | n__o |
| activate(n__a) | → | a | | activate(n__e) | → | e |
The following dependency pairs are strictly oriented by an ordering on the given polynomial interpretation, thus they are removed:
| isNePal#(n____(I, n____(P, I))) | → | U71#(isQid(activate(I)), activate(P)) |
Problem 6: DependencyGraph
Dependency Pair Problem
Dependency Pairs
| U71#(tt, P) | → | isPal#(activate(P)) | | isPal#(V) | → | isNePal#(activate(V)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, n__o, U42, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U52, U81, U11, U31, isQid, n____, nil
Strategy
There are no SCCs!
Problem 3: PolynomialLinearRange4
Dependency Pair Problem
Dependency Pairs
| isList#(n____(V1, V2)) | → | U21#(isList(activate(V1)), activate(V2)) | | isNeList#(n____(V1, V2)) | → | U41#(isList(activate(V1)), activate(V2)) |
| isNeList#(n____(V1, V2)) | → | U51#(isNeList(activate(V1)), activate(V2)) | | U21#(tt, V2) | → | isList#(activate(V2)) |
| U51#(tt, V2) | → | isList#(activate(V2)) | | isNeList#(n____(V1, V2)) | → | isNeList#(activate(V1)) |
| U41#(tt, V2) | → | isNeList#(activate(V2)) | | isNeList#(n____(V1, V2)) | → | isList#(activate(V1)) |
| isList#(n____(V1, V2)) | → | isList#(activate(V1)) | | isList#(V) | → | isNeList#(activate(V)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
Polynomial Interpretation
- U11(x): x
- U21(x,y): y + x
- U21#(x,y): 2y
- U22(x): 2
- U31(x): x
- U41(x,y): y + x
- U41#(x,y): 2y + x
- U42(x): 2
- U51(x,y): x
- U51#(x,y): 2y
- U52(x): 2
- U61(x): 0
- U71(x,y): 0
- U72(x): 0
- U81(x): 0
- __(x,y): y + x
- a: 3
- activate(x): x
- e: 2
- i: 2
- isList(x): 2x
- isList#(x): 2x
- isNeList(x): 2x
- isNeList#(x): 2x
- isNePal(x): 0
- isPal(x): 0
- isQid(x): x
- n____(x,y): y + x
- n__a: 3
- n__e: 2
- n__i: 2
- n__nil: 1
- n__o: 2
- n__u: 2
- nil: 1
- o: 2
- tt: 2
- u: 2
Standard Usable rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| __(X, nil) | → | X | | a | → | n__a |
| U31(tt) | → | tt | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isQid(n__u) | → | tt |
| isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) | | isQid(n__e) | → | tt |
| U41(tt, V2) | → | U42(isNeList(activate(V2))) | | isList(V) | → | U11(isNeList(activate(V))) |
| __(X1, X2) | → | n____(X1, X2) | | U22(tt) | → | tt |
| activate(n__a) | → | a | | U11(tt) | → | tt |
| e | → | n__e | | activate(n__i) | → | i |
| isList(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__i) | → | tt | | U42(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | isNeList(V) | → | U31(isQid(activate(V))) |
| activate(X) | → | X | | activate(n__u) | → | u |
| __(nil, X) | → | X | | i | → | n__i |
| u | → | n__u | | activate(n__o) | → | o |
| nil | → | n__nil | | o | → | n__o |
| isQid(n__o) | → | tt | | U52(tt) | → | tt |
| activate(n__e) | → | e |
The following dependency pairs are strictly oriented by an ordering on the given polynomial interpretation, thus they are removed:
| U41#(tt, V2) | → | isNeList#(activate(V2)) |
Problem 7: DependencyGraph
Dependency Pair Problem
Dependency Pairs
| isList#(n____(V1, V2)) | → | U21#(isList(activate(V1)), activate(V2)) | | isNeList#(n____(V1, V2)) | → | U41#(isList(activate(V1)), activate(V2)) |
| isNeList#(n____(V1, V2)) | → | U51#(isNeList(activate(V1)), activate(V2)) | | U21#(tt, V2) | → | isList#(activate(V2)) |
| U51#(tt, V2) | → | isList#(activate(V2)) | | isNeList#(n____(V1, V2)) | → | isNeList#(activate(V1)) |
| isList#(V) | → | isNeList#(activate(V)) | | isList#(n____(V1, V2)) | → | isList#(activate(V1)) |
| isNeList#(n____(V1, V2)) | → | isList#(activate(V1)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, n__o, U42, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U52, U81, U11, U31, isQid, n____, nil
Strategy
The following SCCs where found
| isList#(n____(V1, V2)) → U21#(isList(activate(V1)), activate(V2)) | isNeList#(n____(V1, V2)) → U51#(isNeList(activate(V1)), activate(V2)) |
| U21#(tt, V2) → isList#(activate(V2)) | U51#(tt, V2) → isList#(activate(V2)) |
| isNeList#(n____(V1, V2)) → isNeList#(activate(V1)) | isList#(V) → isNeList#(activate(V)) |
| isNeList#(n____(V1, V2)) → isList#(activate(V1)) | isList#(n____(V1, V2)) → isList#(activate(V1)) |
Problem 8: PolynomialLinearRange4
Dependency Pair Problem
Dependency Pairs
| isList#(n____(V1, V2)) | → | U21#(isList(activate(V1)), activate(V2)) | | isNeList#(n____(V1, V2)) | → | U51#(isNeList(activate(V1)), activate(V2)) |
| U21#(tt, V2) | → | isList#(activate(V2)) | | U51#(tt, V2) | → | isList#(activate(V2)) |
| isNeList#(n____(V1, V2)) | → | isNeList#(activate(V1)) | | isList#(V) | → | isNeList#(activate(V)) |
| isNeList#(n____(V1, V2)) | → | isList#(activate(V1)) | | isList#(n____(V1, V2)) | → | isList#(activate(V1)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, n__o, U42, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U52, U81, U11, U31, isQid, n____, nil
Strategy
Polynomial Interpretation
- U11(x): 1
- U21(x,y): 1
- U21#(x,y): 2y
- U22(x): 1
- U31(x): 2x
- U41(x,y): 2y + 2
- U42(x): x + 1
- U51(x,y): 2y + x + 1
- U51#(x,y): 2y + 2
- U52(x): x + 1
- U61(x): 0
- U71(x,y): 0
- U72(x): 0
- U81(x): 0
- __(x,y): y + x + 1
- a: 1
- activate(x): x
- e: 2
- i: 1
- isList(x): 1
- isList#(x): 2x
- isNeList(x): 2x
- isNeList#(x): 2x
- isNePal(x): 0
- isPal(x): 0
- isQid(x): x
- n____(x,y): y + x + 1
- n__a: 1
- n__e: 2
- n__i: 1
- n__nil: 2
- n__o: 1
- n__u: 2
- nil: 2
- o: 1
- tt: 1
- u: 2
Standard Usable rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| __(X, nil) | → | X | | a | → | n__a |
| U31(tt) | → | tt | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isQid(n__u) | → | tt |
| isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) | | isQid(n__e) | → | tt |
| U41(tt, V2) | → | U42(isNeList(activate(V2))) | | isList(V) | → | U11(isNeList(activate(V))) |
| __(X1, X2) | → | n____(X1, X2) | | U22(tt) | → | tt |
| activate(n__a) | → | a | | U11(tt) | → | tt |
| e | → | n__e | | activate(n__i) | → | i |
| isList(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__i) | → | tt | | U42(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | isNeList(V) | → | U31(isQid(activate(V))) |
| activate(X) | → | X | | activate(n__u) | → | u |
| __(nil, X) | → | X | | i | → | n__i |
| u | → | n__u | | activate(n__o) | → | o |
| nil | → | n__nil | | o | → | n__o |
| isQid(n__o) | → | tt | | U52(tt) | → | tt |
| activate(n__e) | → | e |
The following dependency pairs are strictly oriented by an ordering on the given polynomial interpretation, thus they are removed:
| isList#(n____(V1, V2)) | → | U21#(isList(activate(V1)), activate(V2)) | | U51#(tt, V2) | → | isList#(activate(V2)) |
| isNeList#(n____(V1, V2)) | → | isNeList#(activate(V1)) | | isList#(n____(V1, V2)) | → | isList#(activate(V1)) |
| isNeList#(n____(V1, V2)) | → | isList#(activate(V1)) |
Problem 9: DependencyGraph
Dependency Pair Problem
Dependency Pairs
| isNeList#(n____(V1, V2)) | → | U51#(isNeList(activate(V1)), activate(V2)) | | U21#(tt, V2) | → | isList#(activate(V2)) |
| isList#(V) | → | isNeList#(activate(V)) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
There are no SCCs!
Problem 4: SubtermCriterion
Dependency Pair Problem
Dependency Pairs
| __#(__(X, Y), Z) | → | __#(X, __(Y, Z)) | | __#(__(X, Y), Z) | → | __#(Y, Z) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
Projection
The following projection was used:
Thus, the following dependency pairs are removed:
| __#(__(X, Y), Z) | → | __#(X, __(Y, Z)) | | __#(__(X, Y), Z) | → | __#(Y, Z) |
Problem 5: SubtermCriterion
Dependency Pair Problem
Dependency Pairs
| activate#(n____(X1, X2)) | → | activate#(X1) | | activate#(n____(X1, X2)) | → | activate#(X2) |
Rewrite Rules
| __(__(X, Y), Z) | → | __(X, __(Y, Z)) | | __(X, nil) | → | X |
| __(nil, X) | → | X | | U11(tt) | → | tt |
| U21(tt, V2) | → | U22(isList(activate(V2))) | | U22(tt) | → | tt |
| U31(tt) | → | tt | | U41(tt, V2) | → | U42(isNeList(activate(V2))) |
| U42(tt) | → | tt | | U51(tt, V2) | → | U52(isList(activate(V2))) |
| U52(tt) | → | tt | | U61(tt) | → | tt |
| U71(tt, P) | → | U72(isPal(activate(P))) | | U72(tt) | → | tt |
| U81(tt) | → | tt | | isList(V) | → | U11(isNeList(activate(V))) |
| isList(n__nil) | → | tt | | isList(n____(V1, V2)) | → | U21(isList(activate(V1)), activate(V2)) |
| isNeList(V) | → | U31(isQid(activate(V))) | | isNeList(n____(V1, V2)) | → | U41(isList(activate(V1)), activate(V2)) |
| isNeList(n____(V1, V2)) | → | U51(isNeList(activate(V1)), activate(V2)) | | isNePal(V) | → | U61(isQid(activate(V))) |
| isNePal(n____(I, n____(P, I))) | → | U71(isQid(activate(I)), activate(P)) | | isPal(V) | → | U81(isNePal(activate(V))) |
| isPal(n__nil) | → | tt | | isQid(n__a) | → | tt |
| isQid(n__e) | → | tt | | isQid(n__i) | → | tt |
| isQid(n__o) | → | tt | | isQid(n__u) | → | tt |
| nil | → | n__nil | | __(X1, X2) | → | n____(X1, X2) |
| a | → | n__a | | e | → | n__e |
| i | → | n__i | | o | → | n__o |
| u | → | n__u | | activate(n__nil) | → | nil |
| activate(n____(X1, X2)) | → | __(activate(X1), activate(X2)) | | activate(n__a) | → | a |
| activate(n__e) | → | e | | activate(n__i) | → | i |
| activate(n__o) | → | o | | activate(n__u) | → | u |
| activate(X) | → | X |
Original Signature
Termination of terms over the following signature is verified: isList, isNeList, __, activate, n__u, U61, U42, n__o, U41, isNePal, n__nil, U21, U22, n__e, e, n__a, a, o, isPal, n__i, i, U71, U72, u, U51, tt, U81, U52, U11, isQid, U31, n____, nil
Strategy
Projection
The following projection was used:
Thus, the following dependency pairs are removed:
| activate#(n____(X1, X2)) | → | activate#(X1) | | activate#(n____(X1, X2)) | → | activate#(X2) |