Consider the TRS R consisting of the rewrite rules

1: active(and(true,X)) -> mark(X)
2: active(and(false,Y)) -> mark(false)
3: active(if(true,X,Y)) -> mark(X)
4: active(if(false,X,Y)) -> mark(Y)
5: active(add(0,X)) -> mark(X)
6: active(add(s(X),Y)) -> mark(s(add(X,Y)))
7: active(first(0,X)) -> mark(nil)
8: active(first(s(X),cons(Y,Z))) -> mark(cons(Y,first(X,Z)))
9: active(from(X)) -> mark(cons(X,from(s(X))))
10: active(and(X1,X2)) -> and(active(X1),X2)
11: active(if(X1,X2,X3)) -> if(active(X1),X2,X3)
12: active(add(X1,X2)) -> add(active(X1),X2)
13: active(first(X1,X2)) -> first(active(X1),X2)
14: active(first(X1,X2)) -> first(X1,active(X2))
15: and(mark(X1),X2) -> mark(and(X1,X2))
16: if(mark(X1),X2,X3) -> mark(if(X1,X2,X3))
17: add(mark(X1),X2) -> mark(add(X1,X2))
18: first(mark(X1),X2) -> mark(first(X1,X2))
19: first(X1,mark(X2)) -> mark(first(X1,X2))
20: proper(and(X1,X2)) -> and(proper(X1),proper(X2))
21: proper(true) -> ok(true)
22: proper(false) -> ok(false)
23: proper(if(X1,X2,X3)) -> if(proper(X1),proper(X2),proper(X3))
24: proper(add(X1,X2)) -> add(proper(X1),proper(X2))
25: proper(0) -> ok(0)
26: proper(s(X)) -> s(proper(X))
27: proper(first(X1,X2)) -> first(proper(X1),proper(X2))
28: proper(nil) -> ok(nil)
29: proper(cons(X1,X2)) -> cons(proper(X1),proper(X2))
30: proper(from(X)) -> from(proper(X))
31: and(ok(X1),ok(X2)) -> ok(and(X1,X2))
32: if(ok(X1),ok(X2),ok(X3)) -> ok(if(X1,X2,X3))
33: add(ok(X1),ok(X2)) -> ok(add(X1,X2))
34: s(ok(X)) -> ok(s(X))
35: first(ok(X1),ok(X2)) -> ok(first(X1,X2))
36: cons(ok(X1),ok(X2)) -> ok(cons(X1,X2))
37: from(ok(X)) -> ok(from(X))
38: top(mark(X)) -> top(proper(X))
39: top(ok(X)) -> top(active(X))

There are 53 dependency pairs:

40: ACTIVE(add(s(X),Y)) -> S(add(X,Y))
41: ACTIVE(add(s(X),Y)) -> ADD(X,Y)
42: ACTIVE(first(s(X),cons(Y,Z))) -> CONS(Y,first(X,Z))
43: ACTIVE(first(s(X),cons(Y,Z))) -> FIRST(X,Z)
44: ACTIVE(from(X)) -> CONS(X,from(s(X)))
45: ACTIVE(from(X)) -> FROM(s(X))
46: ACTIVE(from(X)) -> S(X)
47: ACTIVE(and(X1,X2)) -> AND(active(X1),X2)
48: ACTIVE(and(X1,X2)) -> ACTIVE(X1)
49: ACTIVE(if(X1,X2,X3)) -> IF(active(X1),X2,X3)
50: ACTIVE(if(X1,X2,X3)) -> ACTIVE(X1)
51: ACTIVE(add(X1,X2)) -> ADD(active(X1),X2)
52: ACTIVE(add(X1,X2)) -> ACTIVE(X1)
53: ACTIVE(first(X1,X2)) -> FIRST(active(X1),X2)
54: ACTIVE(first(X1,X2)) -> ACTIVE(X1)
55: ACTIVE(first(X1,X2)) -> FIRST(X1,active(X2))
56: ACTIVE(first(X1,X2)) -> ACTIVE(X2)
57: AND(mark(X1),X2) -> AND(X1,X2)
58: IF(mark(X1),X2,X3) -> IF(X1,X2,X3)
59: ADD(mark(X1),X2) -> ADD(X1,X2)
60: FIRST(mark(X1),X2) -> FIRST(X1,X2)
61: FIRST(X1,mark(X2)) -> FIRST(X1,X2)
62: PROPER(and(X1,X2)) -> AND(proper(X1),proper(X2))
63: PROPER(and(X1,X2)) -> PROPER(X1)
64: PROPER(and(X1,X2)) -> PROPER(X2)
65: PROPER(if(X1,X2,X3)) -> IF(proper(X1),proper(X2),proper(X3))
66: PROPER(if(X1,X2,X3)) -> PROPER(X1)
67: PROPER(if(X1,X2,X3)) -> PROPER(X2)
68: PROPER(if(X1,X2,X3)) -> PROPER(X3)
69: PROPER(add(X1,X2)) -> ADD(proper(X1),proper(X2))
70: PROPER(add(X1,X2)) -> PROPER(X1)
71: PROPER(add(X1,X2)) -> PROPER(X2)
72: PROPER(s(X)) -> S(proper(X))
73: PROPER(s(X)) -> PROPER(X)
74: PROPER(first(X1,X2)) -> FIRST(proper(X1),proper(X2))
75: PROPER(first(X1,X2)) -> PROPER(X1)
76: PROPER(first(X1,X2)) -> PROPER(X2)
77: PROPER(cons(X1,X2)) -> CONS(proper(X1),proper(X2))
78: PROPER(cons(X1,X2)) -> PROPER(X1)
79: PROPER(cons(X1,X2)) -> PROPER(X2)
80: PROPER(from(X)) -> FROM(proper(X))
81: PROPER(from(X)) -> PROPER(X)
82: AND(ok(X1),ok(X2)) -> AND(X1,X2)
83: IF(ok(X1),ok(X2),ok(X3)) -> IF(X1,X2,X3)
84: ADD(ok(X1),ok(X2)) -> ADD(X1,X2)
85: S(ok(X)) -> S(X)
86: FIRST(ok(X1),ok(X2)) -> FIRST(X1,X2)
87: CONS(ok(X1),ok(X2)) -> CONS(X1,X2)
88: FROM(ok(X)) -> FROM(X)
89: TOP(mark(X)) -> TOP(proper(X))
90: TOP(mark(X)) -> PROPER(X)
91: TOP(ok(X)) -> TOP(active(X))
92: TOP(ok(X)) -> ACTIVE(X)

The approximated dependency graph contains 10 SCCs:
{59,84},
{57,82},
{87},
{60,61,86},
{88},
{58,83},
{85},
{63,64,66-68,70,71,73,75,76,78,79,81},
{48,50,52,54,56}
and {89,91}.

- Consider the SCC {59,84}.
There are no usable rules.
By taking the polynomial interpretation
[mark](x) = [ok](x) = x + 1
and [ADD](x,y) = x + y + 1,
the rules in {59,84}
are strictly decreasing.

- Consider the SCC {57,82}.
There are no usable rules.
By taking the polynomial interpretation
[mark](x) = [ok](x) = x + 1
and [AND](x,y) = x + y + 1,
the rules in {57,82}
are strictly decreasing.

- Consider the SCC {87}.
There are no usable rules.
By taking the polynomial interpretation
[ok](x) = x + 1
and [CONS](x,y) = x + y + 1,
rule 87
is strictly decreasing.

- Consider the SCC {60,61,86}.
There are no usable rules.
By taking the polynomial interpretation
[mark](x) = [ok](x) = x + 1
and [FIRST](x,y) = x + y + 1,
the rules in {60,61,86}
are strictly decreasing.

- Consider the SCC {88}.
There are no usable rules.
By taking the polynomial interpretation
[FROM](x) = [ok](x) = x + 1,
rule 88
is strictly decreasing.

- Consider the SCC {58,83}.
There are no usable rules.
By taking the polynomial interpretation
[mark](x) = [ok](x) = x + 1
and [IF](x,y,z) = x + y + z + 1,
the rules in {58,83}
are strictly decreasing.

- Consider the SCC {85}.
There are no usable rules.
By taking the polynomial interpretation
[ok](x) = [S](x) = x + 1,
rule 85
is strictly decreasing.

- Consider the SCC {63,64,66-68,70,71,73,75,76,78,79,81}.
There are no usable rules.
By taking the polynomial interpretation
[from](x) = [PROPER](x) = [s](x) = x + 1,
[add](x,y) = [and](x,y) = [cons](x,y) = [first](x,y) = x + y + 1
and [if](x,y,z) = x + y + z + 1,
the rules in {63,64,66-68,70,71,73,75,76,78,79,81}
are strictly decreasing.

- Consider the SCC {48,50,52,54,56}.
There are no usable rules.
By taking the polynomial interpretation
[ACTIVE](x) = x + 1,
[add](x,y) = [and](x,y) = [first](x,y) = x + y + 1
and [if](x,y,z) = x + y + z + 1,
the rules in {48,50,52,54,56}
are strictly decreasing.

- Consider the SCC {89,91}.
The usable rules are {1-37}.
By taking the polynomial interpretation
[0] = [false] = [nil] = [s](x) = [true] = 1,
[active](x) = [cons](x,y) = [ok](x) = [proper](x) = x,
[from](x) = [mark](x) = [TOP](x) = x + 1,
[add](x,y) = [and](x,y) = [first](x,y) = x + y + 1
and [if](x,y,z) = x + y + z + 1,
the rules in {2,6,7,9-37,91}
are weakly decreasing and
the rules in {1,3-5,8,89}
are strictly decreasing.
There is one new SCC.

- Consider the SCC {91}.
The usable rules are {1-19,31-37}.
By taking the polynomial interpretation
[0] = [false] = [mark](x) = [nil] = [true] = 1,
[active](x) = x,
[from](x) = [ok](x) = [s](x) = [TOP](x) = x + 1,
[add](x,y) = [and](x,y) = [cons](x,y) = [first](x,y) = x + y + 1
and [if](x,y,z) = x + y + z + 1,
the rules in {9-14,34,37}
are weakly decreasing and
the rules in {1-8,15-19,31-33,35,36,91}
are strictly decreasing.


Hence the TRS is terminating.