We consider universal computability of the LCSTRS with only rule scheme Calc:

  Signature: cons :: Int -> intlist -> intlist
             fsum :: (Int -> Int) -> Int -> Int         (private)
             init :: (Int -> Int) -> intlist -> intlist
             map  :: (Int -> Int) -> intlist -> intlist
             nil  :: intlist

  Rules: init(F) -> map([+](fsum(F, 10)))
         map(F, nil) -> nil
         map(F, cons(H, T)) -> cons(F(H), map(F, T)) | H = H
         fsum(F, 0) -> 0
         fsum(F, N) -> F(N) + fsum(F, N - 1) | N != 0

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 UNION R_?, i, c), where:

  P1. (1) init#(F, arg2) => fsum#(F, 10)
      (2) init#(F, arg2) => map#([+](fsum(F, 10)), arg2)
      (3) map#(F, cons(H, T)) => map#(F, T) | H = H
      (4) fsum#(F, N) => fsum#(F, N - 1) | N != 0        (private)

***** We apply the Constraint Modification Processor on D1 = (P1, R UNION R_?, i, c).

We replace fsum#(F, N) => fsum#(F, N - 1) | N != 0 by:

  fsum#(F, N) => fsum#(F, N - 1) | N > 0
  fsum#(F, N) => fsum#(F, N - 1) | N < 0

Processor output: { D2 = (P2, R UNION R_?, i, c) }, where:

  P2. (1) init#(F, arg2) => fsum#(F, 10)
      (2) init#(F, arg2) => map#([+](fsum(F, 10)), arg2)
      (3) map#(F, cons(H, T)) => map#(F, T) | H = H
      (4) fsum#(F, N) => fsum#(F, N - 1) | N > 0         (private)
      (5) fsum#(F, N) => fsum#(F, N - 1) | N < 0         (private)

***** We apply the Reachability Processor on D2 = (P2, R UNION R_?, i, c).

We compute a graph approximation with the following edges:

  ! 1: 4 
  ! 2: 3 
  ! 3: 3 
    4: 4 
    5: 5 

There is one unreachable dependency pair, which is removed.

Processor output: { D3 = (P3, R UNION R_?, i, c) }, where:

  P3. (1) init#(F, arg2) => fsum#(F, 10)
      (2) init#(F, arg2) => map#([+](fsum(F, 10)), arg2)
      (3) map#(F, cons(H, T)) => map#(F, T) | H = H
      (4) fsum#(F, N) => fsum#(F, N - 1) | N > 0         (private)

***** We apply the Graph Processor on D3 = (P3, R UNION R_?, i, c).

We compute a graph approximation with the following edges:

  1: 4 
  2: 3 
  3: 3 
  4: 4 

There are 2 SCCs.

Processor output: { D4 = (P4, R UNION R_?, i, c) ; D5 = (P5, R UNION R_?, i, c) }, where:

  P4. (1) fsum#(F, N) => fsum#(F, N - 1) | N > 0

  P5. (1) map#(F, cons(H, T)) => map#(F, T) | H = H

***** We apply the Integer Function Processor on D4 = (P4, R UNION R_?, i, c).

We use the following integer mapping:

  J(fsum#) = arg_2

We thus have:

  (1) N > 0 |= N > N - 1 (and N >= 0)

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 UNION R_?, i, c).

We use the following projection function:

  nu(map#) = 2

We thus have:

  (1) cons(H, T) |>| T

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

Processor output: { }.