We consider termination of the STRS with no additional rule schemes:

  Signature: *       :: a -> a -> a
             +       :: a -> a -> a
             cons    :: c -> d -> d
             false   :: b
             filter  :: (c -> b) -> d -> d
             filter2 :: b -> (c -> b) -> c -> d -> d
             map     :: (c -> c) -> d -> d
             nil     :: d
             true    :: b

  Rules: *(X, +(Y, U)) -> +(*(X, Y), *(X, U))
         *(+(W, P), V) -> +(*(V, W), *(V, P))
         *(*(X1, Y1), U1) -> *(X1, *(Y1, U1))
         +(+(V1, W1), P1) -> +(V1, +(W1, P1))
         map(F2, nil) -> nil
         map(Z2, cons(U2, V2)) -> cons(Z2(U2), map(Z2, V2))
         filter(I2, nil) -> nil
         filter(J2, cons(X3, Y3)) -> filter2(J2(X3), J2, X3, Y3)
         filter2(true, G3, V3, W3) -> cons(V3, filter(G3, W3))
         filter2(false, J3, X4, Y4) -> filter(J3, Y4)

The system is accessible function passing by a sort ordering that equates all sorts.

We start by computing the initial DP problem D1 = (P1, R, i, c), where:

  P1. (1)  *#(X, +(Y, U)) => *#(X, Y)
      (2)  *#(X, +(Y, U)) => *#(X, U)
      (3)  *#(X, +(Y, U)) => +#(*(X, Y), *(X, U))
      (4)  *#(+(W, P), V) => *#(V, W)
      (5)  *#(+(W, P), V) => *#(V, P)
      (6)  *#(+(W, P), V) => +#(*(V, W), *(V, P))
      (7)  *#(*(X1, Y1), U1) => *#(Y1, U1)
      (8)  *#(*(X1, Y1), U1) => *#(X1, *(Y1, U1))
      (9)  +#(+(V1, W1), P1) => +#(W1, P1)
      (10) +#(+(V1, W1), P1) => +#(V1, +(W1, P1))
      (11) map#(Z2, cons(U2, V2)) => map#(Z2, V2)
      (12) filter#(J2, cons(X3, Y3)) => filter2#(J2(X3), J2, X3, Y3)
      (13) filter2#(true, G3, V3, W3) => filter#(G3, W3)
      (14) filter2#(false, J3, X4, Y4) => filter#(J3, Y4)

***** We apply the Graph Processor on D1 = (P1, R, i, c).

We compute a graph approximation with the following edges:

  1:  1 2 3 4 5 6 7 8 
  2:  1 2 3 4 5 6 7 8 
  3:  9 10 
  4:  1 2 3 4 5 6 7 8 
  5:  1 2 3 4 5 6 7 8 
  6:  9 10 
  7:  1 2 3 4 5 6 7 8 
  8:  1 2 3 4 5 6 7 8 
  9:  9 10 
  10: 9 10 
  11: 11 
  12: 13 14 
  13: 12 
  14: 12 

There are 4 SCCs.

Processor output: { D2 = (P2, R, i, c) ; D3 = (P3, R, i, c) ; D4 = (P4, R, i, c) ; D5 = (P5, R, i, c) }, where:

  P2. (1) +#(+(V1, W1), P1) => +#(W1, P1)
      (2) +#(+(V1, W1), P1) => +#(V1, +(W1, P1))

  P3. (1) *#(X, +(Y, U)) => *#(X, Y)
      (2) *#(X, +(Y, U)) => *#(X, U)
      (3) *#(+(W, P), V) => *#(V, W)
      (4) *#(+(W, P), V) => *#(V, P)
      (5) *#(*(X1, Y1), U1) => *#(Y1, U1)
      (6) *#(*(X1, Y1), U1) => *#(X1, *(Y1, U1))

  P4. (1) map#(Z2, cons(U2, V2)) => map#(Z2, V2)

  P5. (1) filter#(J2, cons(X3, Y3)) => filter2#(J2(X3), J2, X3, Y3)
      (2) filter2#(true, G3, V3, W3) => filter#(G3, W3)
      (3) filter2#(false, J3, X4, Y4) => filter#(J3, Y4)

***** We apply the Subterm Criterion Processor on D2 = (P2, R, i, c).

We use the following projection function:

  nu(+#) = 1

We thus have:

  (1) +(V1, W1) |>| W1
  (2) +(V1, W1) |>| V1

All DPs are strictly oriented, and may be removed.  Hence, this DP problem is finite.

Processor output: { }.

***** We apply the Usable Rules Processor on D3 = (P3, R, i, c).

We obtain 4 usable rules (out of 10 rules in the input problem).

Processor output: { D6 = (P3, R2, i, c) }, where:

  R2. (1) *(X, +(Y, U)) -> +(*(X, Y), *(X, U))
      (2) *(+(W, P), V) -> +(*(V, W), *(V, P))
      (3) *(*(X1, Y1), U1) -> *(X1, *(Y1, U1))
      (4) +(+(V1, W1), P1) -> +(V1, +(W1, P1))

***** We apply the Subterm Criterion Processor on D4 = (P4, R, i, c).

We use the following projection function:

  nu(map#) = 2

We thus have:

  (1) cons(U2, V2) |>| V2

All DPs are strictly oriented, and may be removed.  Hence, this DP problem is finite.

Processor output: { }.

***** We apply the Subterm Criterion Processor on D5 = (P5, R, i, c).

We use the following projection function:

  nu(filter#)  = 2
  nu(filter2#) = 4

We thus have:

  (1) cons(X3, Y3) |>|  Y3
  (2) W3           |>=| W3
  (3) Y4           |>=| Y4

We may remove the strictly oriented DPs.

Processor output: { D7 = (P6, R, i, c) }, where:

  P6. (1) filter2#(true, G3, V3, W3) => filter#(G3, W3)
      (2) filter2#(false, J3, X4, Y4) => filter#(J3, Y4)

***** No progress could be made on DP problem D6 = (P3, R2, i, c).