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

  Signature: append      :: c -> c -> c
             cons        :: b -> c -> c
             flatwith    :: (a -> b) -> b -> c
             flatwithsub :: (a -> b) -> c -> c
             leaf        :: a -> b
             nil         :: c
             node        :: c -> b

  Rules: append(nil, X) -> X
         append(cons(Y, U), V) -> cons(Y, append(U, V))
         flatwith(I, leaf(P)) -> cons(I(P), nil)
         flatwith(F1, node(Y1)) -> flatwithsub(F1, Y1)
         flatwithsub(G1, nil) -> nil
         flatwithsub(H1, cons(W1, P1)) -> append(flatwith(H1, W1), flatwithsub(H1, P1))

The system is accessible function passing by a sort ordering with b = c ≻ a.

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

  P1. (1) append#(cons(Y, U), V) => append#(U, V)
      (2) flatwith#(F1, node(Y1)) => flatwithsub#(F1, Y1)
      (3) flatwithsub#(H1, cons(W1, P1)) => flatwith#(H1, W1)
      (4) flatwithsub#(H1, cons(W1, P1)) => flatwithsub#(H1, P1)
      (5) flatwithsub#(H1, cons(W1, P1)) => append#(flatwith(H1, W1), flatwithsub(H1, P1))

***** 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 
  3: 2 
  4: 3 4 5 
  5: 1 

There are 2 SCCs.

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

  P2. (1) append#(cons(Y, U), V) => append#(U, V)

  P3. (1) flatwith#(F1, node(Y1)) => flatwithsub#(F1, Y1)
      (2) flatwithsub#(H1, cons(W1, P1)) => flatwith#(H1, W1)
      (3) flatwithsub#(H1, cons(W1, P1)) => flatwithsub#(H1, P1)

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

We use the following projection function:

  nu(append#) = 1

We thus have:

  (1) cons(Y, U) |>| U

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

Processor output: { }.

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

We use the following projection function:

  nu(flatwith#)    = 2
  nu(flatwithsub#) = 2

We thus have:

  (1) node(Y1)     |>| Y1
  (2) cons(W1, P1) |>| W1
  (3) cons(W1, P1) |>| P1

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

Processor output: { }.