/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
We consider the system theBenchmark.

We are asked to determine termination of the following first-order TRS.

  0 : [] --> o 
  U11 : [o] --> o 
  U21 : [o] --> o 
  U31 : [o] --> o 
  U41 : [o * o] --> o 
  U42 : [o] --> o 
  U51 : [o * o] --> o 
  U52 : [o] --> o 
  U61 : [o * o] --> o 
  U62 : [o] --> o 
  U71 : [o * o * o] --> o 
  U72 : [o * o] --> o 
  U81 : [o] --> o 
  U91 : [o * o * o * o] --> o 
  U92 : [o * o * o * o] --> o 
  U93 : [o * o * o * o] --> o 
  a!6220!6220U11 : [o] --> o 
  a!6220!6220U21 : [o] --> o 
  a!6220!6220U31 : [o] --> o 
  a!6220!6220U41 : [o * o] --> o 
  a!6220!6220U42 : [o] --> o 
  a!6220!6220U51 : [o * o] --> o 
  a!6220!6220U52 : [o] --> o 
  a!6220!6220U61 : [o * o] --> o 
  a!6220!6220U62 : [o] --> o 
  a!6220!6220U71 : [o * o * o] --> o 
  a!6220!6220U72 : [o * o] --> o 
  a!6220!6220U81 : [o] --> o 
  a!6220!6220U91 : [o * o * o * o] --> o 
  a!6220!6220U92 : [o * o * o * o] --> o 
  a!6220!6220U93 : [o * o * o * o] --> o 
  a!6220!6220isNat : [o] --> o 
  a!6220!6220isNatIList : [o] --> o 
  a!6220!6220isNatList : [o] --> o 
  a!6220!6220length : [o] --> o 
  a!6220!6220take : [o * o] --> o 
  a!6220!6220zeros : [] --> o 
  cons : [o * o] --> o 
  isNat : [o] --> o 
  isNatIList : [o] --> o 
  isNatList : [o] --> o 
  length : [o] --> o 
  mark : [o] --> o 
  nil : [] --> o 
  s : [o] --> o 
  take : [o * o] --> o 
  tt : [] --> o 
  zeros : [] --> o 

  a!6220!6220zeros => cons(0, zeros) 
  a!6220!6220U11(tt) => tt 
  a!6220!6220U21(tt) => tt 
  a!6220!6220U31(tt) => tt 
  a!6220!6220U41(tt, X) => a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) => tt 
  a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) => tt 
  a!6220!6220U61(tt, X) => a!6220!6220U62(a!6220!6220isNatIList(X)) 
  a!6220!6220U62(tt) => tt 
  a!6220!6220U71(tt, X, Y) => a!6220!6220U72(a!6220!6220isNat(Y), X) 
  a!6220!6220U72(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220U81(tt) => nil 
  a!6220!6220U91(tt, X, Y, Z) => a!6220!6220U92(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92(tt, X, Y, Z) => a!6220!6220U93(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93(tt, X, Y, Z) => cons(mark(Z), take(Y, X)) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) => a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) => tt 
  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) => tt 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(take(X, Y)) => a!6220!6220U61(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) => 0 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U71(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220take(0, X) => a!6220!6220U81(a!6220!6220isNatIList(X)) 
  a!6220!6220take(s(X), cons(Y, Z)) => a!6220!6220U91(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark(zeros) => a!6220!6220zeros 
  mark(U11(X)) => a!6220!6220U11(mark(X)) 
  mark(U21(X)) => a!6220!6220U21(mark(X)) 
  mark(U31(X)) => a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) => a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) => a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) => a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) => a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(U61(X, Y)) => a!6220!6220U61(mark(X), Y) 
  mark(U62(X)) => a!6220!6220U62(mark(X)) 
  mark(U71(X, Y, Z)) => a!6220!6220U71(mark(X), Y, Z) 
  mark(U72(X, Y)) => a!6220!6220U72(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(length(X)) => a!6220!6220length(mark(X)) 
  mark(U81(X)) => a!6220!6220U81(mark(X)) 
  mark(U91(X, Y, Z, U)) => a!6220!6220U91(mark(X), Y, Z, U) 
  mark(U92(X, Y, Z, U)) => a!6220!6220U92(mark(X), Y, Z, U) 
  mark(U93(X, Y, Z, U)) => a!6220!6220U93(mark(X), Y, Z, U) 
  mark(take(X, Y)) => a!6220!6220take(mark(X), mark(Y)) 
  mark(cons(X, Y)) => cons(mark(X), Y) 
  mark(0) => 0 
  mark(tt) => tt 
  mark(s(X)) => s(mark(X)) 
  mark(nil) => nil 
  a!6220!6220zeros => zeros 
  a!6220!6220U11(X) => U11(X) 
  a!6220!6220U21(X) => U21(X) 
  a!6220!6220U31(X) => U31(X) 
  a!6220!6220U41(X, Y) => U41(X, Y) 
  a!6220!6220U42(X) => U42(X) 
  a!6220!6220isNatIList(X) => isNatIList(X) 
  a!6220!6220U51(X, Y) => U51(X, Y) 
  a!6220!6220U52(X) => U52(X) 
  a!6220!6220isNatList(X) => isNatList(X) 
  a!6220!6220U61(X, Y) => U61(X, Y) 
  a!6220!6220U62(X) => U62(X) 
  a!6220!6220U71(X, Y, Z) => U71(X, Y, Z) 
  a!6220!6220U72(X, Y) => U72(X, Y) 
  a!6220!6220isNat(X) => isNat(X) 
  a!6220!6220length(X) => length(X) 
  a!6220!6220U81(X) => U81(X) 
  a!6220!6220U91(X, Y, Z, U) => U91(X, Y, Z, U) 
  a!6220!6220U92(X, Y, Z, U) => U92(X, Y, Z, U) 
  a!6220!6220U93(X, Y, Z, U) => U93(X, Y, Z, U) 
  a!6220!6220take(X, Y) => take(X, Y) 

We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]).

We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative):

  Dependency Pairs P_0:

    0] a!6220!6220U41#(tt, X) =#> a!6220!6220U42#(a!6220!6220isNatIList(X))   
    1] a!6220!6220U41#(tt, X) =#> a!6220!6220isNatIList#(X)   
    2] a!6220!6220U51#(tt, X) =#> a!6220!6220U52#(a!6220!6220isNatList(X))   
    3] a!6220!6220U51#(tt, X) =#> a!6220!6220isNatList#(X)   
    4] a!6220!6220U61#(tt, X) =#> a!6220!6220U62#(a!6220!6220isNatIList(X))   
    5] a!6220!6220U61#(tt, X) =#> a!6220!6220isNatIList#(X)   
    6] a!6220!6220U71#(tt, X, Y) =#> a!6220!6220U72#(a!6220!6220isNat(Y), X)   
    7] a!6220!6220U71#(tt, X, Y) =#> a!6220!6220isNat#(Y)   
    8] a!6220!6220U72#(tt, X) =#> a!6220!6220length#(mark(X))   
    9] a!6220!6220U72#(tt, X) =#> mark#(X)   
    10] a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
    11] a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220isNat#(Y)   
    12] a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
    13] a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220isNat#(Z)   
    14] a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   
    15] a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatList(X))   
    16] a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatList#(X)   
    17] a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNat(X))   
    18] a!6220!6220isNat#(s(X)) =#> a!6220!6220isNat#(X)   
    19] a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatList(X))   
    20] a!6220!6220isNatIList#(X) =#> a!6220!6220isNatList#(X)   
    21] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220isNat(X), Y)   
    22] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNat#(X)   
    23] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220isNat(X), Y)   
    24] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNat#(X)   
    25] a!6220!6220isNatList#(take(X, Y)) =#> a!6220!6220U61#(a!6220!6220isNat(X), Y)   
    26] a!6220!6220isNatList#(take(X, Y)) =#> a!6220!6220isNat#(X)   
    27] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X)   
    28] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220isNatList#(Y)   
    29] a!6220!6220take#(0, X) =#> a!6220!6220U81#(a!6220!6220isNatIList(X))   
    30] a!6220!6220take#(0, X) =#> a!6220!6220isNatIList#(X)   
    31] a!6220!6220take#(s(X), cons(Y, Z)) =#> a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y)   
    32] a!6220!6220take#(s(X), cons(Y, Z)) =#> a!6220!6220isNatIList#(Z)   
    33] mark#(zeros) =#> a!6220!6220zeros#   
    34] mark#(U11(X)) =#> a!6220!6220U11#(mark(X))   
    35] mark#(U11(X)) =#> mark#(X)   
    36] mark#(U21(X)) =#> a!6220!6220U21#(mark(X))   
    37] mark#(U21(X)) =#> mark#(X)   
    38] mark#(U31(X)) =#> a!6220!6220U31#(mark(X))   
    39] mark#(U31(X)) =#> mark#(X)   
    40] mark#(U41(X, Y)) =#> a!6220!6220U41#(mark(X), Y)   
    41] mark#(U41(X, Y)) =#> mark#(X)   
    42] mark#(U42(X)) =#> a!6220!6220U42#(mark(X))   
    43] mark#(U42(X)) =#> mark#(X)   
    44] mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X)   
    45] mark#(U51(X, Y)) =#> a!6220!6220U51#(mark(X), Y)   
    46] mark#(U51(X, Y)) =#> mark#(X)   
    47] mark#(U52(X)) =#> a!6220!6220U52#(mark(X))   
    48] mark#(U52(X)) =#> mark#(X)   
    49] mark#(isNatList(X)) =#> a!6220!6220isNatList#(X)   
    50] mark#(U61(X, Y)) =#> a!6220!6220U61#(mark(X), Y)   
    51] mark#(U61(X, Y)) =#> mark#(X)   
    52] mark#(U62(X)) =#> a!6220!6220U62#(mark(X))   
    53] mark#(U62(X)) =#> mark#(X)   
    54] mark#(U71(X, Y, Z)) =#> a!6220!6220U71#(mark(X), Y, Z)   
    55] mark#(U71(X, Y, Z)) =#> mark#(X)   
    56] mark#(U72(X, Y)) =#> a!6220!6220U72#(mark(X), Y)   
    57] mark#(U72(X, Y)) =#> mark#(X)   
    58] mark#(isNat(X)) =#> a!6220!6220isNat#(X)   
    59] mark#(length(X)) =#> a!6220!6220length#(mark(X))   
    60] mark#(length(X)) =#> mark#(X)   
    61] mark#(U81(X)) =#> a!6220!6220U81#(mark(X))   
    62] mark#(U81(X)) =#> mark#(X)   
    63] mark#(U91(X, Y, Z, U)) =#> a!6220!6220U91#(mark(X), Y, Z, U)   
    64] mark#(U91(X, Y, Z, U)) =#> mark#(X)   
    65] mark#(U92(X, Y, Z, U)) =#> a!6220!6220U92#(mark(X), Y, Z, U)   
    66] mark#(U92(X, Y, Z, U)) =#> mark#(X)   
    67] mark#(U93(X, Y, Z, U)) =#> a!6220!6220U93#(mark(X), Y, Z, U)   
    68] mark#(U93(X, Y, Z, U)) =#> mark#(X)   
    69] mark#(take(X, Y)) =#> a!6220!6220take#(mark(X), mark(Y))   
    70] mark#(take(X, Y)) =#> mark#(X)   
    71] mark#(take(X, Y)) =#> mark#(Y)   
    72] mark#(cons(X, Y)) =#> mark#(X)   
    73] mark#(s(X)) =#> mark#(X)   

  Rules R_0:

    a!6220!6220zeros => cons(0, zeros) 
    a!6220!6220U11(tt) => tt 
    a!6220!6220U21(tt) => tt 
    a!6220!6220U31(tt) => tt 
    a!6220!6220U41(tt, X) => a!6220!6220U42(a!6220!6220isNatIList(X)) 
    a!6220!6220U42(tt) => tt 
    a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatList(X)) 
    a!6220!6220U52(tt) => tt 
    a!6220!6220U61(tt, X) => a!6220!6220U62(a!6220!6220isNatIList(X)) 
    a!6220!6220U62(tt) => tt 
    a!6220!6220U71(tt, X, Y) => a!6220!6220U72(a!6220!6220isNat(Y), X) 
    a!6220!6220U72(tt, X) => s(a!6220!6220length(mark(X))) 
    a!6220!6220U81(tt) => nil 
    a!6220!6220U91(tt, X, Y, Z) => a!6220!6220U92(a!6220!6220isNat(Y), X, Y, Z) 
    a!6220!6220U92(tt, X, Y, Z) => a!6220!6220U93(a!6220!6220isNat(Z), X, Y, Z) 
    a!6220!6220U93(tt, X, Y, Z) => cons(mark(Z), take(Y, X)) 
    a!6220!6220isNat(0) => tt 
    a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatList(X)) 
    a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNat(X)) 
    a!6220!6220isNatIList(X) => a!6220!6220U31(a!6220!6220isNatList(X)) 
    a!6220!6220isNatIList(zeros) => tt 
    a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNat(X), Y) 
    a!6220!6220isNatList(nil) => tt 
    a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNat(X), Y) 
    a!6220!6220isNatList(take(X, Y)) => a!6220!6220U61(a!6220!6220isNat(X), Y) 
    a!6220!6220length(nil) => 0 
    a!6220!6220length(cons(X, Y)) => a!6220!6220U71(a!6220!6220isNatList(Y), Y, X) 
    a!6220!6220take(0, X) => a!6220!6220U81(a!6220!6220isNatIList(X)) 
    a!6220!6220take(s(X), cons(Y, Z)) => a!6220!6220U91(a!6220!6220isNatIList(Z), Z, X, Y) 
    mark(zeros) => a!6220!6220zeros 
    mark(U11(X)) => a!6220!6220U11(mark(X)) 
    mark(U21(X)) => a!6220!6220U21(mark(X)) 
    mark(U31(X)) => a!6220!6220U31(mark(X)) 
    mark(U41(X, Y)) => a!6220!6220U41(mark(X), Y) 
    mark(U42(X)) => a!6220!6220U42(mark(X)) 
    mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
    mark(U51(X, Y)) => a!6220!6220U51(mark(X), Y) 
    mark(U52(X)) => a!6220!6220U52(mark(X)) 
    mark(isNatList(X)) => a!6220!6220isNatList(X) 
    mark(U61(X, Y)) => a!6220!6220U61(mark(X), Y) 
    mark(U62(X)) => a!6220!6220U62(mark(X)) 
    mark(U71(X, Y, Z)) => a!6220!6220U71(mark(X), Y, Z) 
    mark(U72(X, Y)) => a!6220!6220U72(mark(X), Y) 
    mark(isNat(X)) => a!6220!6220isNat(X) 
    mark(length(X)) => a!6220!6220length(mark(X)) 
    mark(U81(X)) => a!6220!6220U81(mark(X)) 
    mark(U91(X, Y, Z, U)) => a!6220!6220U91(mark(X), Y, Z, U) 
    mark(U92(X, Y, Z, U)) => a!6220!6220U92(mark(X), Y, Z, U) 
    mark(U93(X, Y, Z, U)) => a!6220!6220U93(mark(X), Y, Z, U) 
    mark(take(X, Y)) => a!6220!6220take(mark(X), mark(Y)) 
    mark(cons(X, Y)) => cons(mark(X), Y) 
    mark(0) => 0 
    mark(tt) => tt 
    mark(s(X)) => s(mark(X)) 
    mark(nil) => nil 
    a!6220!6220zeros => zeros 
    a!6220!6220U11(X) => U11(X) 
    a!6220!6220U21(X) => U21(X) 
    a!6220!6220U31(X) => U31(X) 
    a!6220!6220U41(X, Y) => U41(X, Y) 
    a!6220!6220U42(X) => U42(X) 
    a!6220!6220isNatIList(X) => isNatIList(X) 
    a!6220!6220U51(X, Y) => U51(X, Y) 
    a!6220!6220U52(X) => U52(X) 
    a!6220!6220isNatList(X) => isNatList(X) 
    a!6220!6220U61(X, Y) => U61(X, Y) 
    a!6220!6220U62(X) => U62(X) 
    a!6220!6220U71(X, Y, Z) => U71(X, Y, Z) 
    a!6220!6220U72(X, Y) => U72(X, Y) 
    a!6220!6220isNat(X) => isNat(X) 
    a!6220!6220length(X) => length(X) 
    a!6220!6220U81(X) => U81(X) 
    a!6220!6220U91(X, Y, Z, U) => U91(X, Y, Z, U) 
    a!6220!6220U92(X, Y, Z, U) => U92(X, Y, Z, U) 
    a!6220!6220U93(X, Y, Z, U) => U93(X, Y, Z, U) 
    a!6220!6220take(X, Y) => take(X, Y) 

Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_0, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 :  
    * 1 : 19, 20, 21, 22 
    * 2 :  
    * 3 : 23, 24, 25, 26 
    * 4 :  
    * 5 : 19, 20, 21, 22 
    * 6 : 8, 9 
    * 7 : 15, 16, 17, 18 
    * 8 : 27, 28 
    * 9 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 10 : 12, 13 
    * 11 : 15, 16, 17, 18 
    * 12 : 14 
    * 13 : 15, 16, 17, 18 
    * 14 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 15 :  
    * 16 : 23, 24, 25, 26 
    * 17 :  
    * 18 : 15, 16, 17, 18 
    * 19 :  
    * 20 : 23, 24, 25, 26 
    * 21 : 0, 1 
    * 22 : 15, 16, 17, 18 
    * 23 : 2, 3 
    * 24 : 15, 16, 17, 18 
    * 25 : 4, 5 
    * 26 : 15, 16, 17, 18 
    * 27 : 6, 7 
    * 28 : 23, 24, 25, 26 
    * 29 :  
    * 30 : 19, 20, 21, 22 
    * 31 : 10, 11 
    * 32 : 19, 20, 21, 22 
    * 33 :  
    * 34 :  
    * 35 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 36 :  
    * 37 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 38 :  
    * 39 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 40 : 0, 1 
    * 41 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 42 :  
    * 43 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 44 : 19, 20, 21, 22 
    * 45 : 2, 3 
    * 46 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 47 :  
    * 48 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 49 : 23, 24, 25, 26 
    * 50 : 4, 5 
    * 51 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 52 :  
    * 53 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 54 : 6, 7 
    * 55 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 56 : 8, 9 
    * 57 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 58 : 15, 16, 17, 18 
    * 59 : 27, 28 
    * 60 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 61 :  
    * 62 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 63 : 10, 11 
    * 64 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 65 : 12, 13 
    * 66 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 67 : 14 
    * 68 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 69 : 29, 30, 31, 32 
    * 70 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 71 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 72 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 
    * 73 : 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73 

This graph has the following strongly connected components:

  P_1:

    a!6220!6220U41#(tt, X) =#> a!6220!6220isNatIList#(X)   
    a!6220!6220U51#(tt, X) =#> a!6220!6220isNatList#(X)   
    a!6220!6220U61#(tt, X) =#> a!6220!6220isNatIList#(X)   
    a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatList#(X)   
    a!6220!6220isNat#(s(X)) =#> a!6220!6220isNat#(X)   
    a!6220!6220isNatIList#(X) =#> a!6220!6220isNatList#(X)   
    a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220isNat(X), Y)   
    a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNat#(X)   
    a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220isNat(X), Y)   
    a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNat#(X)   
    a!6220!6220isNatList#(take(X, Y)) =#> a!6220!6220U61#(a!6220!6220isNat(X), Y)   
    a!6220!6220isNatList#(take(X, Y)) =#> a!6220!6220isNat#(X)   

  P_2:

    a!6220!6220U71#(tt, X, Y) =#> a!6220!6220U72#(a!6220!6220isNat(Y), X)   
    a!6220!6220U72#(tt, X) =#> a!6220!6220length#(mark(X))   
    a!6220!6220U72#(tt, X) =#> mark#(X)   
    a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
    a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
    a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   
    a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X)   
    a!6220!6220take#(s(X), cons(Y, Z)) =#> a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y)   
    mark#(U11(X)) =#> mark#(X)   
    mark#(U21(X)) =#> mark#(X)   
    mark#(U31(X)) =#> mark#(X)   
    mark#(U41(X, Y)) =#> mark#(X)   
    mark#(U42(X)) =#> mark#(X)   
    mark#(U51(X, Y)) =#> mark#(X)   
    mark#(U52(X)) =#> mark#(X)   
    mark#(U61(X, Y)) =#> mark#(X)   
    mark#(U62(X)) =#> mark#(X)   
    mark#(U71(X, Y, Z)) =#> a!6220!6220U71#(mark(X), Y, Z)   
    mark#(U71(X, Y, Z)) =#> mark#(X)   
    mark#(U72(X, Y)) =#> a!6220!6220U72#(mark(X), Y)   
    mark#(U72(X, Y)) =#> mark#(X)   
    mark#(length(X)) =#> a!6220!6220length#(mark(X))   
    mark#(length(X)) =#> mark#(X)   
    mark#(U81(X)) =#> mark#(X)   
    mark#(U91(X, Y, Z, U)) =#> a!6220!6220U91#(mark(X), Y, Z, U)   
    mark#(U91(X, Y, Z, U)) =#> mark#(X)   
    mark#(U92(X, Y, Z, U)) =#> a!6220!6220U92#(mark(X), Y, Z, U)   
    mark#(U92(X, Y, Z, U)) =#> mark#(X)   
    mark#(U93(X, Y, Z, U)) =#> a!6220!6220U93#(mark(X), Y, Z, U)   
    mark#(U93(X, Y, Z, U)) =#> mark#(X)   
    mark#(take(X, Y)) =#> a!6220!6220take#(mark(X), mark(Y))   
    mark#(take(X, Y)) =#> mark#(X)   
    mark#(take(X, Y)) =#> mark#(Y)   
    mark#(cons(X, Y)) =#> mark#(X)   
    mark#(s(X)) =#> mark#(X)   

By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f) and (P_2, R_0, m, f).

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_2, R_0, minimal, formative).

We will use the reduction pair processor [Kop12, Thm. 7.16].  It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  a!6220!6220U71#(tt, X, Y) >? a!6220!6220U72#(a!6220!6220isNat(Y), X) 
  a!6220!6220U72#(tt, X) >? a!6220!6220length#(mark(X)) 
  a!6220!6220U72#(tt, X) >? mark#(X) 
  a!6220!6220U91#(tt, X, Y, Z) >? a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92#(tt, X, Y, Z) >? a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93#(tt, X, Y, Z) >? mark#(Z) 
  a!6220!6220length#(cons(X, Y)) >? a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220take#(s(X), cons(Y, Z)) >? a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark#(U11(X)) >? mark#(X) 
  mark#(U21(X)) >? mark#(X) 
  mark#(U31(X)) >? mark#(X) 
  mark#(U41(X, Y)) >? mark#(X) 
  mark#(U42(X)) >? mark#(X) 
  mark#(U51(X, Y)) >? mark#(X) 
  mark#(U52(X)) >? mark#(X) 
  mark#(U61(X, Y)) >? mark#(X) 
  mark#(U62(X)) >? mark#(X) 
  mark#(U71(X, Y, Z)) >? a!6220!6220U71#(mark(X), Y, Z) 
  mark#(U71(X, Y, Z)) >? mark#(X) 
  mark#(U72(X, Y)) >? a!6220!6220U72#(mark(X), Y) 
  mark#(U72(X, Y)) >? mark#(X) 
  mark#(length(X)) >? a!6220!6220length#(mark(X)) 
  mark#(length(X)) >? mark#(X) 
  mark#(U81(X)) >? mark#(X) 
  mark#(U91(X, Y, Z, U)) >? a!6220!6220U91#(mark(X), Y, Z, U) 
  mark#(U91(X, Y, Z, U)) >? mark#(X) 
  mark#(U92(X, Y, Z, U)) >? a!6220!6220U92#(mark(X), Y, Z, U) 
  mark#(U92(X, Y, Z, U)) >? mark#(X) 
  mark#(U93(X, Y, Z, U)) >? a!6220!6220U93#(mark(X), Y, Z, U) 
  mark#(U93(X, Y, Z, U)) >? mark#(X) 
  mark#(take(X, Y)) >? a!6220!6220take#(mark(X), mark(Y)) 
  mark#(take(X, Y)) >? mark#(X) 
  mark#(take(X, Y)) >? mark#(Y) 
  mark#(cons(X, Y)) >? mark#(X) 
  mark#(s(X)) >? mark#(X) 
  a!6220!6220zeros >= cons(0, zeros) 
  a!6220!6220U11(tt) >= tt 
  a!6220!6220U21(tt) >= tt 
  a!6220!6220U31(tt) >= tt 
  a!6220!6220U41(tt, X) >= a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >= tt 
  a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >= tt 
  a!6220!6220U61(tt, X) >= a!6220!6220U62(a!6220!6220isNatIList(X)) 
  a!6220!6220U62(tt) >= tt 
  a!6220!6220U71(tt, X, Y) >= a!6220!6220U72(a!6220!6220isNat(Y), X) 
  a!6220!6220U72(tt, X) >= s(a!6220!6220length(mark(X))) 
  a!6220!6220U81(tt) >= nil 
  a!6220!6220U91(tt, X, Y, Z) >= a!6220!6220U92(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92(tt, X, Y, Z) >= a!6220!6220U93(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93(tt, X, Y, Z) >= cons(mark(Z), take(Y, X)) 
  a!6220!6220isNat(0) >= tt 
  a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >= a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >= tt 
  a!6220!6220isNatIList(cons(X, Y)) >= a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) >= tt 
  a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(take(X, Y)) >= a!6220!6220U61(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) >= 0 
  a!6220!6220length(cons(X, Y)) >= a!6220!6220U71(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220take(0, X) >= a!6220!6220U81(a!6220!6220isNatIList(X)) 
  a!6220!6220take(s(X), cons(Y, Z)) >= a!6220!6220U91(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark(zeros) >= a!6220!6220zeros 
  mark(U11(X)) >= a!6220!6220U11(mark(X)) 
  mark(U21(X)) >= a!6220!6220U21(mark(X)) 
  mark(U31(X)) >= a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >= a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >= a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >= a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >= a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >= a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >= a!6220!6220isNatList(X) 
  mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) 
  mark(U62(X)) >= a!6220!6220U62(mark(X)) 
  mark(U71(X, Y, Z)) >= a!6220!6220U71(mark(X), Y, Z) 
  mark(U72(X, Y)) >= a!6220!6220U72(mark(X), Y) 
  mark(isNat(X)) >= a!6220!6220isNat(X) 
  mark(length(X)) >= a!6220!6220length(mark(X)) 
  mark(U81(X)) >= a!6220!6220U81(mark(X)) 
  mark(U91(X, Y, Z, U)) >= a!6220!6220U91(mark(X), Y, Z, U) 
  mark(U92(X, Y, Z, U)) >= a!6220!6220U92(mark(X), Y, Z, U) 
  mark(U93(X, Y, Z, U)) >= a!6220!6220U93(mark(X), Y, Z, U) 
  mark(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y)) 
  mark(cons(X, Y)) >= cons(mark(X), Y) 
  mark(0) >= 0 
  mark(tt) >= tt 
  mark(s(X)) >= s(mark(X)) 
  mark(nil) >= nil 
  a!6220!6220zeros >= zeros 
  a!6220!6220U11(X) >= U11(X) 
  a!6220!6220U21(X) >= U21(X) 
  a!6220!6220U31(X) >= U31(X) 
  a!6220!6220U41(X, Y) >= U41(X, Y) 
  a!6220!6220U42(X) >= U42(X) 
  a!6220!6220isNatIList(X) >= isNatIList(X) 
  a!6220!6220U51(X, Y) >= U51(X, Y) 
  a!6220!6220U52(X) >= U52(X) 
  a!6220!6220isNatList(X) >= isNatList(X) 
  a!6220!6220U61(X, Y) >= U61(X, Y) 
  a!6220!6220U62(X) >= U62(X) 
  a!6220!6220U71(X, Y, Z) >= U71(X, Y, Z) 
  a!6220!6220U72(X, Y) >= U72(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 
  a!6220!6220length(X) >= length(X) 
  a!6220!6220U81(X) >= U81(X) 
  a!6220!6220U91(X, Y, Z, U) >= U91(X, Y, Z, U) 
  a!6220!6220U92(X, Y, Z, U) >= U92(X, Y, Z, U) 
  a!6220!6220U93(X, Y, Z, U) >= U93(X, Y, Z, U) 
  a!6220!6220take(X, Y) >= take(X, Y) 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0.2y0 
  U21 = \y0.y0 
  U31 = \y0.y0 
  U41 = \y0y1.y0 
  U42 = \y0.y0 
  U51 = \y0y1.2y0 
  U52 = \y0.2y0 
  U61 = \y0y1.2y0 
  U62 = \y0.2y0 
  U71 = \y0y1y2.1 + y0 + y1 
  U72 = \y0y1.1 + y0 + y1 
  U81 = \y0.2y0 
  U91 = \y0y1y2y3.y0 + y1 + y2 + y3 
  U92 = \y0y1y2y3.y0 + y1 + y2 + y3 
  U93 = \y0y1y2y3.y0 + y1 + y2 + y3 
  a!6220!6220U11 = \y0.2y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.y0 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.2y0 
  a!6220!6220U52 = \y0.2y0 
  a!6220!6220U61 = \y0y1.2y0 
  a!6220!6220U62 = \y0.2y0 
  a!6220!6220U71 = \y0y1y2.1 + y0 + y1 
  a!6220!6220U71# = \y0y1y2.y1 
  a!6220!6220U72 = \y0y1.1 + y0 + y1 
  a!6220!6220U72# = \y0y1.y1 
  a!6220!6220U81 = \y0.2y0 
  a!6220!6220U91 = \y0y1y2y3.y0 + y1 + y2 + y3 
  a!6220!6220U91# = \y0y1y2y3.y3 
  a!6220!6220U92 = \y0y1y2y3.y0 + y1 + y2 + y3 
  a!6220!6220U92# = \y0y1y2y3.y3 
  a!6220!6220U93 = \y0y1y2y3.y0 + y1 + y2 + y3 
  a!6220!6220U93# = \y0y1y2y3.y3 
  a!6220!6220isNat = \y0.0 
  a!6220!6220isNatIList = \y0.0 
  a!6220!6220isNatList = \y0.0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220length# = \y0.y0 
  a!6220!6220take = \y0y1.y0 + y1 
  a!6220!6220take# = \y0y1.y1 
  a!6220!6220zeros = 0 
  cons = \y0y1.y0 + y1 
  isNat = \y0.0 
  isNatIList = \y0.0 
  isNatList = \y0.0 
  length = \y0.1 + y0 
  mark = \y0.y0 
  mark# = \y0.y0 
  nil = 0 
  s = \y0.y0 
  take = \y0y1.y0 + y1 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220U71#(tt, _x0, _x1)]] = x0 >= x0 = [[a!6220!6220U72#(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U72#(tt, _x0)]] = x0 >= x0 = [[a!6220!6220length#(mark(_x0))]] 
  [[a!6220!6220U72#(tt, _x0)]] = x0 >= x0 = [[mark#(_x0)]] 
  [[a!6220!6220U91#(tt, _x0, _x1, _x2)]] = x2 >= x2 = [[a!6220!6220U92#(a!6220!6220isNat(_x1), _x0, _x1, _x2)]] 
  [[a!6220!6220U92#(tt, _x0, _x1, _x2)]] = x2 >= x2 = [[a!6220!6220U93#(a!6220!6220isNat(_x2), _x0, _x1, _x2)]] 
  [[a!6220!6220U93#(tt, _x0, _x1, _x2)]] = x2 >= x2 = [[mark#(_x2)]] 
  [[a!6220!6220length#(cons(_x0, _x1))]] = x0 + x1 >= x1 = [[a!6220!6220U71#(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[a!6220!6220take#(s(_x0), cons(_x1, _x2))]] = x1 + x2 >= x1 = [[a!6220!6220U91#(a!6220!6220isNatIList(_x2), _x2, _x0, _x1)]] 
  [[mark#(U11(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U21(_x0))]] = x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U31(_x0))]] = x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U41(_x0, _x1))]] = x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U42(_x0))]] = x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U51(_x0, _x1))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U52(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U61(_x0, _x1))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U62(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U71(_x0, _x1, _x2))]] = 1 + x0 + x1 > x1 = [[a!6220!6220U71#(mark(_x0), _x1, _x2)]] 
  [[mark#(U71(_x0, _x1, _x2))]] = 1 + x0 + x1 > x0 = [[mark#(_x0)]] 
  [[mark#(U72(_x0, _x1))]] = 1 + x0 + x1 > x1 = [[a!6220!6220U72#(mark(_x0), _x1)]] 
  [[mark#(U72(_x0, _x1))]] = 1 + x0 + x1 > x0 = [[mark#(_x0)]] 
  [[mark#(length(_x0))]] = 1 + x0 > x0 = [[a!6220!6220length#(mark(_x0))]] 
  [[mark#(length(_x0))]] = 1 + x0 > x0 = [[mark#(_x0)]] 
  [[mark#(U81(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] 
  [[mark#(U91(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x3 = [[a!6220!6220U91#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U91(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 = [[mark#(_x0)]] 
  [[mark#(U92(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x3 = [[a!6220!6220U92#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U92(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 = [[mark#(_x0)]] 
  [[mark#(U93(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x3 = [[a!6220!6220U93#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U93(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 = [[mark#(_x0)]] 
  [[mark#(take(_x0, _x1))]] = x0 + x1 >= x1 = [[a!6220!6220take#(mark(_x0), mark(_x1))]] 
  [[mark#(take(_x0, _x1))]] = x0 + x1 >= x0 = [[mark#(_x0)]] 
  [[mark#(take(_x0, _x1))]] = x0 + x1 >= x1 = [[mark#(_x1)]] 
  [[mark#(cons(_x0, _x1))]] = x0 + x1 >= x0 = [[mark#(_x0)]] 
  [[mark#(s(_x0))]] = x0 >= x0 = [[mark#(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U62(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U62(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U71(tt, _x0, _x1)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U72(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U72(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220U81(tt)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220U91(tt, _x0, _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a!6220!6220U92(a!6220!6220isNat(_x1), _x0, _x1, _x2)]] 
  [[a!6220!6220U92(tt, _x0, _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a!6220!6220U93(a!6220!6220isNat(_x2), _x0, _x1, _x2)]] 
  [[a!6220!6220U93(tt, _x0, _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[cons(mark(_x2), take(_x1, _x0))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 0 >= 0 = [[a!6220!6220U11(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNat(s(_x0))]] = 0 >= 0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(nil)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(take(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U61(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(nil)]] = 1 >= 0 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x1 = [[a!6220!6220U71(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[a!6220!6220take(0, _x0)]] = x0 >= 0 = [[a!6220!6220U81(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220take(s(_x0), cons(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a!6220!6220U91(a!6220!6220isNatIList(_x2), _x2, _x0, _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = x0 >= x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = x0 >= x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U61(mark(_x0), _x1)]] 
  [[mark(U62(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U62(mark(_x0))]] 
  [[mark(U71(_x0, _x1, _x2))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[a!6220!6220U71(mark(_x0), _x1, _x2)]] 
  [[mark(U72(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[a!6220!6220U72(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 0 >= 0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U81(mark(_x0))]] 
  [[mark(U91(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[a!6220!6220U91(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U92(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[a!6220!6220U92(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U93(_x0, _x1, _x2, _x3))]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[a!6220!6220U93(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(take(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220take(mark(_x0), mark(_x1))]] 
  [[mark(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = x0 >= x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0)]] = 2x0 >= 2x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = x0 >= x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 >= x0 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = 2x0 >= 2x0 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = 2x0 >= 2x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = 0 >= 0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1)]] = 2x0 >= 2x0 = [[U61(_x0, _x1)]] 
  [[a!6220!6220U62(_x0)]] = 2x0 >= 2x0 = [[U62(_x0)]] 
  [[a!6220!6220U71(_x0, _x1, _x2)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U71(_x0, _x1, _x2)]] 
  [[a!6220!6220U72(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U72(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 0 >= 0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 >= 1 + x0 = [[length(_x0)]] 
  [[a!6220!6220U81(_x0)]] = 2x0 >= 2x0 = [[U81(_x0)]] 
  [[a!6220!6220U91(_x0, _x1, _x2, _x3)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[U91(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U92(_x0, _x1, _x2, _x3)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[U92(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U93(_x0, _x1, _x2, _x3)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[U93(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220take(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[take(_x0, _x1)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_0, minimal, formative) by (P_3, R_0, minimal, formative), where P_3 consists of:

  a!6220!6220U71#(tt, X, Y) =#> a!6220!6220U72#(a!6220!6220isNat(Y), X)   
  a!6220!6220U72#(tt, X) =#> a!6220!6220length#(mark(X))   
  a!6220!6220U72#(tt, X) =#> mark#(X)   
  a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
  a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
  a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   
  a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X)   
  a!6220!6220take#(s(X), cons(Y, Z)) =#> a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y)   
  mark#(U11(X)) =#> mark#(X)   
  mark#(U21(X)) =#> mark#(X)   
  mark#(U31(X)) =#> mark#(X)   
  mark#(U41(X, Y)) =#> mark#(X)   
  mark#(U42(X)) =#> mark#(X)   
  mark#(U51(X, Y)) =#> mark#(X)   
  mark#(U52(X)) =#> mark#(X)   
  mark#(U61(X, Y)) =#> mark#(X)   
  mark#(U62(X)) =#> mark#(X)   
  mark#(U81(X)) =#> mark#(X)   
  mark#(U91(X, Y, Z, U)) =#> a!6220!6220U91#(mark(X), Y, Z, U)   
  mark#(U91(X, Y, Z, U)) =#> mark#(X)   
  mark#(U92(X, Y, Z, U)) =#> a!6220!6220U92#(mark(X), Y, Z, U)   
  mark#(U92(X, Y, Z, U)) =#> mark#(X)   
  mark#(U93(X, Y, Z, U)) =#> a!6220!6220U93#(mark(X), Y, Z, U)   
  mark#(U93(X, Y, Z, U)) =#> mark#(X)   
  mark#(take(X, Y)) =#> a!6220!6220take#(mark(X), mark(Y))   
  mark#(take(X, Y)) =#> mark#(X)   
  mark#(take(X, Y)) =#> mark#(Y)   
  mark#(cons(X, Y)) =#> mark#(X)   
  mark#(s(X)) =#> mark#(X)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_3, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 : 1, 2 
    * 1 : 6 
    * 2 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 3 : 4 
    * 4 : 5 
    * 5 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 6 : 0 
    * 7 : 3 
    * 8 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 9 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 10 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 11 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 12 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 13 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 14 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 15 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 16 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 17 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 18 : 3 
    * 19 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 20 : 4 
    * 21 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 22 : 5 
    * 23 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 24 : 7 
    * 25 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 26 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 27 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 28 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 

This graph has the following strongly connected components:

  P_4:

    a!6220!6220U71#(tt, X, Y) =#> a!6220!6220U72#(a!6220!6220isNat(Y), X)   
    a!6220!6220U72#(tt, X) =#> a!6220!6220length#(mark(X))   
    a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X)   

  P_5:

    a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
    a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
    a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   
    a!6220!6220take#(s(X), cons(Y, Z)) =#> a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y)   
    mark#(U11(X)) =#> mark#(X)   
    mark#(U21(X)) =#> mark#(X)   
    mark#(U31(X)) =#> mark#(X)   
    mark#(U41(X, Y)) =#> mark#(X)   
    mark#(U42(X)) =#> mark#(X)   
    mark#(U51(X, Y)) =#> mark#(X)   
    mark#(U52(X)) =#> mark#(X)   
    mark#(U61(X, Y)) =#> mark#(X)   
    mark#(U62(X)) =#> mark#(X)   
    mark#(U81(X)) =#> mark#(X)   
    mark#(U91(X, Y, Z, U)) =#> a!6220!6220U91#(mark(X), Y, Z, U)   
    mark#(U91(X, Y, Z, U)) =#> mark#(X)   
    mark#(U92(X, Y, Z, U)) =#> a!6220!6220U92#(mark(X), Y, Z, U)   
    mark#(U92(X, Y, Z, U)) =#> mark#(X)   
    mark#(U93(X, Y, Z, U)) =#> a!6220!6220U93#(mark(X), Y, Z, U)   
    mark#(U93(X, Y, Z, U)) =#> mark#(X)   
    mark#(take(X, Y)) =#> a!6220!6220take#(mark(X), mark(Y))   
    mark#(take(X, Y)) =#> mark#(X)   
    mark#(take(X, Y)) =#> mark#(Y)   
    mark#(cons(X, Y)) =#> mark#(X)   
    mark#(s(X)) =#> mark#(X)   

By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_3, R_0, m, f) by (P_4, R_0, m, f) and (P_5, R_0, m, f).

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_5, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_5, R_0, minimal, formative).

We will use the reduction pair processor [Kop12, Thm. 7.16].  It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  a!6220!6220U91#(tt, X, Y, Z) >? a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92#(tt, X, Y, Z) >? a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93#(tt, X, Y, Z) >? mark#(Z) 
  a!6220!6220take#(s(X), cons(Y, Z)) >? a!6220!6220U91#(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark#(U11(X)) >? mark#(X) 
  mark#(U21(X)) >? mark#(X) 
  mark#(U31(X)) >? mark#(X) 
  mark#(U41(X, Y)) >? mark#(X) 
  mark#(U42(X)) >? mark#(X) 
  mark#(U51(X, Y)) >? mark#(X) 
  mark#(U52(X)) >? mark#(X) 
  mark#(U61(X, Y)) >? mark#(X) 
  mark#(U62(X)) >? mark#(X) 
  mark#(U81(X)) >? mark#(X) 
  mark#(U91(X, Y, Z, U)) >? a!6220!6220U91#(mark(X), Y, Z, U) 
  mark#(U91(X, Y, Z, U)) >? mark#(X) 
  mark#(U92(X, Y, Z, U)) >? a!6220!6220U92#(mark(X), Y, Z, U) 
  mark#(U92(X, Y, Z, U)) >? mark#(X) 
  mark#(U93(X, Y, Z, U)) >? a!6220!6220U93#(mark(X), Y, Z, U) 
  mark#(U93(X, Y, Z, U)) >? mark#(X) 
  mark#(take(X, Y)) >? a!6220!6220take#(mark(X), mark(Y)) 
  mark#(take(X, Y)) >? mark#(X) 
  mark#(take(X, Y)) >? mark#(Y) 
  mark#(cons(X, Y)) >? mark#(X) 
  mark#(s(X)) >? mark#(X) 
  a!6220!6220zeros >= cons(0, zeros) 
  a!6220!6220U11(tt) >= tt 
  a!6220!6220U21(tt) >= tt 
  a!6220!6220U31(tt) >= tt 
  a!6220!6220U41(tt, X) >= a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >= tt 
  a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >= tt 
  a!6220!6220U61(tt, X) >= a!6220!6220U62(a!6220!6220isNatIList(X)) 
  a!6220!6220U62(tt) >= tt 
  a!6220!6220U71(tt, X, Y) >= a!6220!6220U72(a!6220!6220isNat(Y), X) 
  a!6220!6220U72(tt, X) >= s(a!6220!6220length(mark(X))) 
  a!6220!6220U81(tt) >= nil 
  a!6220!6220U91(tt, X, Y, Z) >= a!6220!6220U92(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92(tt, X, Y, Z) >= a!6220!6220U93(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93(tt, X, Y, Z) >= cons(mark(Z), take(Y, X)) 
  a!6220!6220isNat(0) >= tt 
  a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >= a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >= tt 
  a!6220!6220isNatIList(cons(X, Y)) >= a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) >= tt 
  a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(take(X, Y)) >= a!6220!6220U61(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) >= 0 
  a!6220!6220length(cons(X, Y)) >= a!6220!6220U71(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220take(0, X) >= a!6220!6220U81(a!6220!6220isNatIList(X)) 
  a!6220!6220take(s(X), cons(Y, Z)) >= a!6220!6220U91(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark(zeros) >= a!6220!6220zeros 
  mark(U11(X)) >= a!6220!6220U11(mark(X)) 
  mark(U21(X)) >= a!6220!6220U21(mark(X)) 
  mark(U31(X)) >= a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >= a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >= a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >= a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >= a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >= a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >= a!6220!6220isNatList(X) 
  mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) 
  mark(U62(X)) >= a!6220!6220U62(mark(X)) 
  mark(U71(X, Y, Z)) >= a!6220!6220U71(mark(X), Y, Z) 
  mark(U72(X, Y)) >= a!6220!6220U72(mark(X), Y) 
  mark(isNat(X)) >= a!6220!6220isNat(X) 
  mark(length(X)) >= a!6220!6220length(mark(X)) 
  mark(U81(X)) >= a!6220!6220U81(mark(X)) 
  mark(U91(X, Y, Z, U)) >= a!6220!6220U91(mark(X), Y, Z, U) 
  mark(U92(X, Y, Z, U)) >= a!6220!6220U92(mark(X), Y, Z, U) 
  mark(U93(X, Y, Z, U)) >= a!6220!6220U93(mark(X), Y, Z, U) 
  mark(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y)) 
  mark(cons(X, Y)) >= cons(mark(X), Y) 
  mark(0) >= 0 
  mark(tt) >= tt 
  mark(s(X)) >= s(mark(X)) 
  mark(nil) >= nil 
  a!6220!6220zeros >= zeros 
  a!6220!6220U11(X) >= U11(X) 
  a!6220!6220U21(X) >= U21(X) 
  a!6220!6220U31(X) >= U31(X) 
  a!6220!6220U41(X, Y) >= U41(X, Y) 
  a!6220!6220U42(X) >= U42(X) 
  a!6220!6220isNatIList(X) >= isNatIList(X) 
  a!6220!6220U51(X, Y) >= U51(X, Y) 
  a!6220!6220U52(X) >= U52(X) 
  a!6220!6220isNatList(X) >= isNatList(X) 
  a!6220!6220U61(X, Y) >= U61(X, Y) 
  a!6220!6220U62(X) >= U62(X) 
  a!6220!6220U71(X, Y, Z) >= U71(X, Y, Z) 
  a!6220!6220U72(X, Y) >= U72(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 
  a!6220!6220length(X) >= length(X) 
  a!6220!6220U81(X) >= U81(X) 
  a!6220!6220U91(X, Y, Z, U) >= U91(X, Y, Z, U) 
  a!6220!6220U92(X, Y, Z, U) >= U92(X, Y, Z, U) 
  a!6220!6220U93(X, Y, Z, U) >= U93(X, Y, Z, U) 
  a!6220!6220take(X, Y) >= take(X, Y) 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0.y0 
  U21 = \y0.y0 
  U31 = \y0.y0 
  U41 = \y0y1.y0 
  U42 = \y0.y0 
  U51 = \y0y1.y0 
  U52 = \y0.y0 
  U61 = \y0y1.2y0 
  U62 = \y0.y0 
  U71 = \y0y1y2.0 
  U72 = \y0y1.0 
  U81 = \y0.y0 
  U91 = \y0y1y2y3.y0 + 2y3 
  U92 = \y0y1y2y3.y0 + y3 
  U93 = \y0y1y2y3.y3 + 2y0 
  a!6220!6220U11 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.y0 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1.2y0 
  a!6220!6220U62 = \y0.y0 
  a!6220!6220U71 = \y0y1y2.0 
  a!6220!6220U72 = \y0y1.0 
  a!6220!6220U81 = \y0.y0 
  a!6220!6220U91 = \y0y1y2y3.y0 + 2y3 
  a!6220!6220U91# = \y0y1y2y3.2y3 
  a!6220!6220U92 = \y0y1y2y3.y0 + 2y3 
  a!6220!6220U92# = \y0y1y2y3.2y3 
  a!6220!6220U93 = \y0y1y2y3.2y0 + 2y3 
  a!6220!6220U93# = \y0y1y2y3.2y3 
  a!6220!6220isNat = \y0.0 
  a!6220!6220isNatIList = \y0.0 
  a!6220!6220isNatList = \y0.0 
  a!6220!6220length = \y0.0 
  a!6220!6220take = \y0y1.1 + 2y0 + 2y1 
  a!6220!6220take# = \y0y1.1 + 2y1 
  a!6220!6220zeros = 0 
  cons = \y0y1.y0 
  isNat = \y0.0 
  isNatIList = \y0.0 
  isNatList = \y0.0 
  length = \y0.0 
  mark = \y0.2y0 
  mark# = \y0.2y0 
  nil = 0 
  s = \y0.y0 
  take = \y0y1.1 + 2y0 + 2y1 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220U91#(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[a!6220!6220U92#(a!6220!6220isNat(_x1), _x0, _x1, _x2)]] 
  [[a!6220!6220U92#(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[a!6220!6220U93#(a!6220!6220isNat(_x2), _x0, _x1, _x2)]] 
  [[a!6220!6220U93#(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[mark#(_x2)]] 
  [[a!6220!6220take#(s(_x0), cons(_x1, _x2))]] = 1 + 2x1 > 2x1 = [[a!6220!6220U91#(a!6220!6220isNatIList(_x2), _x2, _x0, _x1)]] 
  [[mark#(U11(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U21(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U31(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U41(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U42(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U51(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U52(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U61(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U62(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U81(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U91(_x0, _x1, _x2, _x3))]] = 2x0 + 4x3 >= 2x3 = [[a!6220!6220U91#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U91(_x0, _x1, _x2, _x3))]] = 2x0 + 4x3 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U92(_x0, _x1, _x2, _x3))]] = 2x0 + 2x3 >= 2x3 = [[a!6220!6220U92#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U92(_x0, _x1, _x2, _x3))]] = 2x0 + 2x3 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(U93(_x0, _x1, _x2, _x3))]] = 2x3 + 4x0 >= 2x3 = [[a!6220!6220U93#(mark(_x0), _x1, _x2, _x3)]] 
  [[mark#(U93(_x0, _x1, _x2, _x3))]] = 2x3 + 4x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(take(_x0, _x1))]] = 2 + 4x0 + 4x1 > 1 + 4x1 = [[a!6220!6220take#(mark(_x0), mark(_x1))]] 
  [[mark#(take(_x0, _x1))]] = 2 + 4x0 + 4x1 > 2x0 = [[mark#(_x0)]] 
  [[mark#(take(_x0, _x1))]] = 2 + 4x0 + 4x1 > 2x1 = [[mark#(_x1)]] 
  [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U62(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U62(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U71(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U72(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U72(tt, _x0)]] = 0 >= 0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220U81(tt)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220U91(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[a!6220!6220U92(a!6220!6220isNat(_x1), _x0, _x1, _x2)]] 
  [[a!6220!6220U92(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[a!6220!6220U93(a!6220!6220isNat(_x2), _x0, _x1, _x2)]] 
  [[a!6220!6220U93(tt, _x0, _x1, _x2)]] = 2x2 >= 2x2 = [[cons(mark(_x2), take(_x1, _x0))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 0 >= 0 = [[a!6220!6220U11(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNat(s(_x0))]] = 0 >= 0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(nil)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(take(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U61(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(nil)]] = 0 >= 0 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U71(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[a!6220!6220take(0, _x0)]] = 1 + 2x0 >= 0 = [[a!6220!6220U81(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220take(s(_x0), cons(_x1, _x2))]] = 1 + 2x0 + 2x1 >= 2x1 = [[a!6220!6220U91(a!6220!6220isNatIList(_x2), _x2, _x0, _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1))]] = 4x0 >= 4x0 = [[a!6220!6220U61(mark(_x0), _x1)]] 
  [[mark(U62(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U62(mark(_x0))]] 
  [[mark(U71(_x0, _x1, _x2))]] = 0 >= 0 = [[a!6220!6220U71(mark(_x0), _x1, _x2)]] 
  [[mark(U72(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U72(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 0 >= 0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 0 >= 0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U81(mark(_x0))]] 
  [[mark(U91(_x0, _x1, _x2, _x3))]] = 2x0 + 4x3 >= 2x0 + 2x3 = [[a!6220!6220U91(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U92(_x0, _x1, _x2, _x3))]] = 2x0 + 2x3 >= 2x0 + 2x3 = [[a!6220!6220U92(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U93(_x0, _x1, _x2, _x3))]] = 2x3 + 4x0 >= 2x3 + 4x0 = [[a!6220!6220U93(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(take(_x0, _x1))]] = 2 + 4x0 + 4x1 >= 1 + 4x0 + 4x1 = [[a!6220!6220take(mark(_x0), mark(_x1))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0)]] = x0 >= x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = x0 >= x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 >= x0 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 >= x0 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = 0 >= 0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1)]] = 2x0 >= 2x0 = [[U61(_x0, _x1)]] 
  [[a!6220!6220U62(_x0)]] = x0 >= x0 = [[U62(_x0)]] 
  [[a!6220!6220U71(_x0, _x1, _x2)]] = 0 >= 0 = [[U71(_x0, _x1, _x2)]] 
  [[a!6220!6220U72(_x0, _x1)]] = 0 >= 0 = [[U72(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 0 >= 0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = 0 >= 0 = [[length(_x0)]] 
  [[a!6220!6220U81(_x0)]] = x0 >= x0 = [[U81(_x0)]] 
  [[a!6220!6220U91(_x0, _x1, _x2, _x3)]] = x0 + 2x3 >= x0 + 2x3 = [[U91(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U92(_x0, _x1, _x2, _x3)]] = x0 + 2x3 >= x0 + x3 = [[U92(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U93(_x0, _x1, _x2, _x3)]] = 2x0 + 2x3 >= x3 + 2x0 = [[U93(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220take(_x0, _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[take(_x0, _x1)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_5, R_0, minimal, formative) by (P_6, R_0, minimal, formative), where P_6 consists of:

  a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
  a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
  a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   
  mark#(U11(X)) =#> mark#(X)   
  mark#(U21(X)) =#> mark#(X)   
  mark#(U31(X)) =#> mark#(X)   
  mark#(U41(X, Y)) =#> mark#(X)   
  mark#(U42(X)) =#> mark#(X)   
  mark#(U51(X, Y)) =#> mark#(X)   
  mark#(U52(X)) =#> mark#(X)   
  mark#(U61(X, Y)) =#> mark#(X)   
  mark#(U62(X)) =#> mark#(X)   
  mark#(U81(X)) =#> mark#(X)   
  mark#(U91(X, Y, Z, U)) =#> a!6220!6220U91#(mark(X), Y, Z, U)   
  mark#(U91(X, Y, Z, U)) =#> mark#(X)   
  mark#(U92(X, Y, Z, U)) =#> a!6220!6220U92#(mark(X), Y, Z, U)   
  mark#(U92(X, Y, Z, U)) =#> mark#(X)   
  mark#(U93(X, Y, Z, U)) =#> a!6220!6220U93#(mark(X), Y, Z, U)   
  mark#(U93(X, Y, Z, U)) =#> mark#(X)   
  mark#(cons(X, Y)) =#> mark#(X)   
  mark#(s(X)) =#> mark#(X)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_6, R_0, minimal, formative).

We apply the subterm criterion with the following projection function:

  nu(a!6220!6220U91#) = 4 
  nu(a!6220!6220U92#) = 4 
  nu(a!6220!6220U93#) = 4 
  nu(mark#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(a!6220!6220U91#(tt, X, Y, Z)) = Z = Z = nu(a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)) 
  nu(a!6220!6220U92#(tt, X, Y, Z)) = Z = Z = nu(a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)) 
  nu(a!6220!6220U93#(tt, X, Y, Z)) = Z = Z = nu(mark#(Z)) 
  nu(mark#(U11(X))) = U11(X) |> X = nu(mark#(X)) 
  nu(mark#(U21(X))) = U21(X) |> X = nu(mark#(X)) 
  nu(mark#(U31(X))) = U31(X) |> X = nu(mark#(X)) 
  nu(mark#(U41(X, Y))) = U41(X, Y) |> X = nu(mark#(X)) 
  nu(mark#(U42(X))) = U42(X) |> X = nu(mark#(X)) 
  nu(mark#(U51(X, Y))) = U51(X, Y) |> X = nu(mark#(X)) 
  nu(mark#(U52(X))) = U52(X) |> X = nu(mark#(X)) 
  nu(mark#(U61(X, Y))) = U61(X, Y) |> X = nu(mark#(X)) 
  nu(mark#(U62(X))) = U62(X) |> X = nu(mark#(X)) 
  nu(mark#(U81(X))) = U81(X) |> X = nu(mark#(X)) 
  nu(mark#(U91(X, Y, Z, U))) = U91(X, Y, Z, U) |> U = nu(a!6220!6220U91#(mark(X), Y, Z, U)) 
  nu(mark#(U91(X, Y, Z, U))) = U91(X, Y, Z, U) |> X = nu(mark#(X)) 
  nu(mark#(U92(X, Y, Z, U))) = U92(X, Y, Z, U) |> U = nu(a!6220!6220U92#(mark(X), Y, Z, U)) 
  nu(mark#(U92(X, Y, Z, U))) = U92(X, Y, Z, U) |> X = nu(mark#(X)) 
  nu(mark#(U93(X, Y, Z, U))) = U93(X, Y, Z, U) |> U = nu(a!6220!6220U93#(mark(X), Y, Z, U)) 
  nu(mark#(U93(X, Y, Z, U))) = U93(X, Y, Z, U) |> X = nu(mark#(X)) 
  nu(mark#(cons(X, Y))) = cons(X, Y) |> X = nu(mark#(X)) 
  nu(mark#(s(X))) = s(X) |> X = nu(mark#(X)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, R_0, minimal, f) by (P_7, R_0, minimal, f), where P_7 contains:

  a!6220!6220U91#(tt, X, Y, Z) =#> a!6220!6220U92#(a!6220!6220isNat(Y), X, Y, Z)   
  a!6220!6220U92#(tt, X, Y, Z) =#> a!6220!6220U93#(a!6220!6220isNat(Z), X, Y, Z)   
  a!6220!6220U93#(tt, X, Y, Z) =#> mark#(Z)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_7, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 : 1 
    * 1 : 2 
    * 2 :  

This graph has no strongly connected components.  By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_4, R_0, minimal, formative).

We will use the reduction pair processor [Kop12, Thm. 7.16].  It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  a!6220!6220U71#(tt, X, Y) >? a!6220!6220U72#(a!6220!6220isNat(Y), X) 
  a!6220!6220U72#(tt, X) >? a!6220!6220length#(mark(X)) 
  a!6220!6220length#(cons(X, Y)) >? a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220zeros >= cons(0, zeros) 
  a!6220!6220U11(tt) >= tt 
  a!6220!6220U21(tt) >= tt 
  a!6220!6220U31(tt) >= tt 
  a!6220!6220U41(tt, X) >= a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >= tt 
  a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >= tt 
  a!6220!6220U61(tt, X) >= a!6220!6220U62(a!6220!6220isNatIList(X)) 
  a!6220!6220U62(tt) >= tt 
  a!6220!6220U71(tt, X, Y) >= a!6220!6220U72(a!6220!6220isNat(Y), X) 
  a!6220!6220U72(tt, X) >= s(a!6220!6220length(mark(X))) 
  a!6220!6220U81(tt) >= nil 
  a!6220!6220U91(tt, X, Y, Z) >= a!6220!6220U92(a!6220!6220isNat(Y), X, Y, Z) 
  a!6220!6220U92(tt, X, Y, Z) >= a!6220!6220U93(a!6220!6220isNat(Z), X, Y, Z) 
  a!6220!6220U93(tt, X, Y, Z) >= cons(mark(Z), take(Y, X)) 
  a!6220!6220isNat(0) >= tt 
  a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >= a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >= tt 
  a!6220!6220isNatIList(cons(X, Y)) >= a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) >= tt 
  a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(take(X, Y)) >= a!6220!6220U61(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) >= 0 
  a!6220!6220length(cons(X, Y)) >= a!6220!6220U71(a!6220!6220isNatList(Y), Y, X) 
  a!6220!6220take(0, X) >= a!6220!6220U81(a!6220!6220isNatIList(X)) 
  a!6220!6220take(s(X), cons(Y, Z)) >= a!6220!6220U91(a!6220!6220isNatIList(Z), Z, X, Y) 
  mark(zeros) >= a!6220!6220zeros 
  mark(U11(X)) >= a!6220!6220U11(mark(X)) 
  mark(U21(X)) >= a!6220!6220U21(mark(X)) 
  mark(U31(X)) >= a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >= a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >= a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >= a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >= a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >= a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >= a!6220!6220isNatList(X) 
  mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) 
  mark(U62(X)) >= a!6220!6220U62(mark(X)) 
  mark(U71(X, Y, Z)) >= a!6220!6220U71(mark(X), Y, Z) 
  mark(U72(X, Y)) >= a!6220!6220U72(mark(X), Y) 
  mark(isNat(X)) >= a!6220!6220isNat(X) 
  mark(length(X)) >= a!6220!6220length(mark(X)) 
  mark(U81(X)) >= a!6220!6220U81(mark(X)) 
  mark(U91(X, Y, Z, U)) >= a!6220!6220U91(mark(X), Y, Z, U) 
  mark(U92(X, Y, Z, U)) >= a!6220!6220U92(mark(X), Y, Z, U) 
  mark(U93(X, Y, Z, U)) >= a!6220!6220U93(mark(X), Y, Z, U) 
  mark(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y)) 
  mark(cons(X, Y)) >= cons(mark(X), Y) 
  mark(0) >= 0 
  mark(tt) >= tt 
  mark(s(X)) >= s(mark(X)) 
  mark(nil) >= nil 
  a!6220!6220zeros >= zeros 
  a!6220!6220U11(X) >= U11(X) 
  a!6220!6220U21(X) >= U21(X) 
  a!6220!6220U31(X) >= U31(X) 
  a!6220!6220U41(X, Y) >= U41(X, Y) 
  a!6220!6220U42(X) >= U42(X) 
  a!6220!6220isNatIList(X) >= isNatIList(X) 
  a!6220!6220U51(X, Y) >= U51(X, Y) 
  a!6220!6220U52(X) >= U52(X) 
  a!6220!6220isNatList(X) >= isNatList(X) 
  a!6220!6220U61(X, Y) >= U61(X, Y) 
  a!6220!6220U62(X) >= U62(X) 
  a!6220!6220U71(X, Y, Z) >= U71(X, Y, Z) 
  a!6220!6220U72(X, Y) >= U72(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 
  a!6220!6220length(X) >= length(X) 
  a!6220!6220U81(X) >= U81(X) 
  a!6220!6220U91(X, Y, Z, U) >= U91(X, Y, Z, U) 
  a!6220!6220U92(X, Y, Z, U) >= U92(X, Y, Z, U) 
  a!6220!6220U93(X, Y, Z, U) >= U93(X, Y, Z, U) 
  a!6220!6220take(X, Y) >= take(X, Y) 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  0 = 2 
  U11 = \y0.y0 
  U21 = \y0.2y0 
  U31 = \y0.1 
  U41 = \y0y1.1 
  U42 = \y0.1 
  U51 = \y0y1.2y1 
  U52 = \y0.y0 
  U61 = \y0y1.y0 
  U62 = \y0.y0 
  U71 = \y0y1y2.3y1 
  U72 = \y0y1.3y1 
  U81 = \y0.1 + y0 
  U91 = \y0y1y2y3.3y2 
  U92 = \y0y1y2y3.3y2 
  U93 = \y0y1y2y3.3y2 
  a!6220!6220U11 = \y0.y0 
  a!6220!6220U21 = \y0.2y0 
  a!6220!6220U31 = \y0.1 
  a!6220!6220U41 = \y0y1.1 
  a!6220!6220U42 = \y0.1 
  a!6220!6220U51 = \y0y1.2y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1.y0 
  a!6220!6220U62 = \y0.y0 
  a!6220!6220U71 = \y0y1y2.3y1 
  a!6220!6220U71# = \y0y1y2.2y0 + 2y1 
  a!6220!6220U72 = \y0y1.3y1 
  a!6220!6220U72# = \y0y1.2y1 
  a!6220!6220U81 = \y0.1 + y0 
  a!6220!6220U91 = \y0y1y2y3.3y2 
  a!6220!6220U92 = \y0y1y2y3.3y2 
  a!6220!6220U93 = \y0y1y2y3.3y2 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.1 
  a!6220!6220isNatList = \y0.2y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220length# = \y0.2y0 
  a!6220!6220take = \y0y1.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.3y1 
  isNat = \y0.2y0 
  isNatIList = \y0.1 
  isNatList = \y0.2y0 
  length = \y0.y0 
  mark = \y0.y0 
  nil = 2 
  s = \y0.3y0 
  take = \y0y1.y0 
  tt = 1 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220U71#(tt, _x0, _x1)]] = 2 + 2x0 > 2x0 = [[a!6220!6220U72#(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U72#(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220length#(mark(_x0))]] 
  [[a!6220!6220length#(cons(_x0, _x1))]] = 6x1 >= 6x1 = [[a!6220!6220U71#(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U21(tt)]] = 2 >= 1 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U61(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U62(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U62(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U71(tt, _x0, _x1)]] = 3x0 >= 3x0 = [[a!6220!6220U72(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U72(tt, _x0)]] = 3x0 >= 3x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220U81(tt)]] = 2 >= 2 = [[nil]] 
  [[a!6220!6220U91(tt, _x0, _x1, _x2)]] = 3x1 >= 3x1 = [[a!6220!6220U92(a!6220!6220isNat(_x1), _x0, _x1, _x2)]] 
  [[a!6220!6220U92(tt, _x0, _x1, _x2)]] = 3x1 >= 3x1 = [[a!6220!6220U93(a!6220!6220isNat(_x2), _x0, _x1, _x2)]] 
  [[a!6220!6220U93(tt, _x0, _x1, _x2)]] = 3x1 >= 3x1 = [[cons(mark(_x2), take(_x1, _x0))]] 
  [[a!6220!6220isNat(0)]] = 4 >= 1 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U11(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNat(s(_x0))]] = 6x0 >= 4x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 >= 1 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(nil)]] = 4 >= 1 = [[tt]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 6x1 >= 2x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(take(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U61(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(nil)]] = 2 >= 2 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 3x1 >= 3x1 = [[a!6220!6220U71(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[a!6220!6220take(0, _x0)]] = 2 >= 2 = [[a!6220!6220U81(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220take(s(_x0), cons(_x1, _x2))]] = 3x0 >= 3x0 = [[a!6220!6220U91(a!6220!6220isNatIList(_x2), _x2, _x0, _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = x0 >= x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 1 >= 1 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 1 >= 1 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x1 >= 2x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1))]] = x0 >= x0 = [[a!6220!6220U61(mark(_x0), _x1)]] 
  [[mark(U62(_x0))]] = x0 >= x0 = [[a!6220!6220U62(mark(_x0))]] 
  [[mark(U71(_x0, _x1, _x2))]] = 3x1 >= 3x1 = [[a!6220!6220U71(mark(_x0), _x1, _x2)]] 
  [[mark(U72(_x0, _x1))]] = 3x1 >= 3x1 = [[a!6220!6220U72(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = x0 >= x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(U81(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U81(mark(_x0))]] 
  [[mark(U91(_x0, _x1, _x2, _x3))]] = 3x2 >= 3x2 = [[a!6220!6220U91(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U92(_x0, _x1, _x2, _x3))]] = 3x2 >= 3x2 = [[a!6220!6220U92(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(U93(_x0, _x1, _x2, _x3))]] = 3x2 >= 3x2 = [[a!6220!6220U93(mark(_x0), _x1, _x2, _x3)]] 
  [[mark(take(_x0, _x1))]] = x0 >= x0 = [[a!6220!6220take(mark(_x0), mark(_x1))]] 
  [[mark(cons(_x0, _x1))]] = 3x1 >= 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 2 >= 2 = [[0]] 
  [[mark(tt)]] = 1 >= 1 = [[tt]] 
  [[mark(s(_x0))]] = 3x0 >= 3x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 2 >= 2 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0)]] = x0 >= x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = 2x0 >= 2x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 1 >= 1 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 1 >= 1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = 1 >= 1 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 >= 1 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = 2x1 >= 2x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = 2x0 >= 2x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1)]] = x0 >= x0 = [[U61(_x0, _x1)]] 
  [[a!6220!6220U62(_x0)]] = x0 >= x0 = [[U62(_x0)]] 
  [[a!6220!6220U71(_x0, _x1, _x2)]] = 3x1 >= 3x1 = [[U71(_x0, _x1, _x2)]] 
  [[a!6220!6220U72(_x0, _x1)]] = 3x1 >= 3x1 = [[U72(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= 2x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 
  [[a!6220!6220U81(_x0)]] = 1 + x0 >= 1 + x0 = [[U81(_x0)]] 
  [[a!6220!6220U91(_x0, _x1, _x2, _x3)]] = 3x2 >= 3x2 = [[U91(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U92(_x0, _x1, _x2, _x3)]] = 3x2 >= 3x2 = [[U92(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220U93(_x0, _x1, _x2, _x3)]] = 3x2 >= 3x2 = [[U93(_x0, _x1, _x2, _x3)]] 
  [[a!6220!6220take(_x0, _x1)]] = x0 >= x0 = [[take(_x0, _x1)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_4, R_0, minimal, formative) by (P_8, R_0, minimal, formative), where P_8 consists of:

  a!6220!6220U72#(tt, X) =#> a!6220!6220length#(mark(X))   
  a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U71#(a!6220!6220isNatList(Y), Y, X)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_8, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 : 1 
    * 1 :  

This graph has no strongly connected components.  By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem.

Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_1, R_0, minimal, formative).

We apply the subterm criterion with the following projection function:

  nu(a!6220!6220U41#) = 2 
  nu(a!6220!6220U51#) = 2 
  nu(a!6220!6220U61#) = 2 
  nu(a!6220!6220isNatIList#) = 1 
  nu(a!6220!6220isNatList#) = 1 
  nu(a!6220!6220isNat#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(a!6220!6220U41#(tt, X)) = X = X = nu(a!6220!6220isNatIList#(X)) 
  nu(a!6220!6220U51#(tt, X)) = X = X = nu(a!6220!6220isNatList#(X)) 
  nu(a!6220!6220U61#(tt, X)) = X = X = nu(a!6220!6220isNatIList#(X)) 
  nu(a!6220!6220isNat#(length(X))) = length(X) |> X = nu(a!6220!6220isNatList#(X)) 
  nu(a!6220!6220isNat#(s(X))) = s(X) |> X = nu(a!6220!6220isNat#(X)) 
  nu(a!6220!6220isNatIList#(X)) = X = X = nu(a!6220!6220isNatList#(X)) 
  nu(a!6220!6220isNatIList#(cons(X, Y))) = cons(X, Y) |> Y = nu(a!6220!6220U41#(a!6220!6220isNat(X), Y)) 
  nu(a!6220!6220isNatIList#(cons(X, Y))) = cons(X, Y) |> X = nu(a!6220!6220isNat#(X)) 
  nu(a!6220!6220isNatList#(cons(X, Y))) = cons(X, Y) |> Y = nu(a!6220!6220U51#(a!6220!6220isNat(X), Y)) 
  nu(a!6220!6220isNatList#(cons(X, Y))) = cons(X, Y) |> X = nu(a!6220!6220isNat#(X)) 
  nu(a!6220!6220isNatList#(take(X, Y))) = take(X, Y) |> Y = nu(a!6220!6220U61#(a!6220!6220isNat(X), Y)) 
  nu(a!6220!6220isNatList#(take(X, Y))) = take(X, Y) |> X = nu(a!6220!6220isNat#(X)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by (P_9, R_0, minimal, f), where P_9 contains:

  a!6220!6220U41#(tt, X) =#> a!6220!6220isNatIList#(X)   
  a!6220!6220U51#(tt, X) =#> a!6220!6220isNatList#(X)   
  a!6220!6220U61#(tt, X) =#> a!6220!6220isNatIList#(X)   
  a!6220!6220isNatIList#(X) =#> a!6220!6220isNatList#(X)   

Thus, the original system is terminating if (P_9, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_9, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 : 3 
    * 1 :  
    * 2 : 3 
    * 3 :  

This graph has no strongly connected components.  By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem.

As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.


+++ Citations +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
[KusIsoSakBla09]  K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui.  Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems.  In volume 92(10) of IEICE Transactions on Information and Systems.  2007--2015, 2009.