/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] --> o U12 : [o * o] --> o U13 : [o] --> o U21 : [o * o] --> o U22 : [o * o] --> o U23 : [o] --> o U31 : [o * o] --> o U32 : [o * o] --> o U33 : [o] --> o U41 : [o * o * o] --> o U42 : [o * o * o] --> o U43 : [o * o * o] --> o U44 : [o * o * o] --> o U45 : [o * o] --> o U46 : [o] --> o U51 : [o * o] --> o U52 : [o] --> o U61 : [o] --> o U71 : [o] --> o U81 : [o * o * o] --> o U82 : [o * o * o] --> o U83 : [o * o * o] --> o U84 : [o * o * o] --> o U85 : [o * o] --> o U86 : [o] --> o U91 : [o * o * o] --> o U92 : [o * o * o] --> o U93 : [o * o * o] --> o U94 : [o * o] --> o a!6220!6220U11 : [o * o] --> o a!6220!6220U12 : [o * o] --> o a!6220!6220U13 : [o] --> o a!6220!6220U21 : [o * o] --> o a!6220!6220U22 : [o * o] --> o a!6220!6220U23 : [o] --> o a!6220!6220U31 : [o * o] --> o a!6220!6220U32 : [o * o] --> o a!6220!6220U33 : [o] --> o a!6220!6220U41 : [o * o * o] --> o a!6220!6220U42 : [o * o * o] --> o a!6220!6220U43 : [o * o * o] --> o a!6220!6220U44 : [o * o * o] --> o a!6220!6220U45 : [o * o] --> o a!6220!6220U46 : [o] --> o a!6220!6220U51 : [o * o] --> o a!6220!6220U52 : [o] --> o a!6220!6220U61 : [o] --> o a!6220!6220U71 : [o] --> o a!6220!6220U81 : [o * o * o] --> o a!6220!6220U82 : [o * o * o] --> o a!6220!6220U83 : [o * o * o] --> o a!6220!6220U84 : [o * o * o] --> o a!6220!6220U85 : [o * o] --> o a!6220!6220U86 : [o] --> o a!6220!6220U91 : [o * o * o] --> o a!6220!6220U92 : [o * o * o] --> o a!6220!6220U93 : [o * o * o] --> o a!6220!6220U94 : [o * o] --> o a!6220!6220isNat : [o] --> o a!6220!6220isNatIList : [o] --> o a!6220!6220isNatIListKind : [o] --> o a!6220!6220isNatKind : [o] --> o a!6220!6220isNatList : [o] --> o a!6220!6220length : [o] --> o a!6220!6220zeros : [] --> o cons : [o * o] --> o isNat : [o] --> o isNatIList : [o] --> o isNatIListKind : [o] --> o isNatKind : [o] --> o isNatList : [o] --> o length : [o] --> o mark : [o] --> o nil : [] --> o s : [o] --> o tt : [] --> o zeros : [] --> o a!6220!6220zeros => cons(0, zeros) a!6220!6220U11(tt, X) => a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) => a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) => tt a!6220!6220U21(tt, X) => a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) => a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) => tt a!6220!6220U31(tt, X) => a!6220!6220U32(a!6220!6220isNatIListKind(X), X) a!6220!6220U32(tt, X) => a!6220!6220U33(a!6220!6220isNatList(X)) a!6220!6220U33(tt) => tt a!6220!6220U41(tt, X, Y) => a!6220!6220U42(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42(tt, X, Y) => a!6220!6220U43(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43(tt, X, Y) => a!6220!6220U44(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44(tt, X, Y) => a!6220!6220U45(a!6220!6220isNat(X), Y) a!6220!6220U45(tt, X) => a!6220!6220U46(a!6220!6220isNatIList(X)) a!6220!6220U46(tt) => tt a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) => tt a!6220!6220U61(tt) => tt a!6220!6220U71(tt) => tt a!6220!6220U81(tt, X, Y) => a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) => a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) => a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) => a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) => a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) => tt a!6220!6220U91(tt, X, Y) => a!6220!6220U92(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92(tt, X, Y) => a!6220!6220U93(a!6220!6220isNat(Y), X, Y) a!6220!6220U93(tt, X, Y) => a!6220!6220U94(a!6220!6220isNatKind(Y), X) a!6220!6220U94(tt, X) => s(a!6220!6220length(mark(X))) a!6220!6220isNat(0) => tt a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIList(X) => a!6220!6220U31(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList(zeros) => tt a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNatKind(X), X, Y) a!6220!6220isNatIListKind(nil) => tt a!6220!6220isNatIListKind(zeros) => tt a!6220!6220isNatIListKind(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) => tt a!6220!6220isNatKind(length(X)) => a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) => a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) => tt a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220length(nil) => 0 a!6220!6220length(cons(X, Y)) => a!6220!6220U91(a!6220!6220isNatList(Y), Y, X) mark(zeros) => a!6220!6220zeros mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) mark(U12(X, Y)) => a!6220!6220U12(mark(X), Y) mark(isNatIListKind(X)) => a!6220!6220isNatIListKind(X) mark(U13(X)) => a!6220!6220U13(mark(X)) mark(isNatList(X)) => a!6220!6220isNatList(X) mark(U21(X, Y)) => a!6220!6220U21(mark(X), Y) mark(U22(X, Y)) => a!6220!6220U22(mark(X), Y) mark(isNatKind(X)) => a!6220!6220isNatKind(X) mark(U23(X)) => a!6220!6220U23(mark(X)) mark(isNat(X)) => a!6220!6220isNat(X) mark(U31(X, Y)) => a!6220!6220U31(mark(X), Y) mark(U32(X, Y)) => a!6220!6220U32(mark(X), Y) mark(U33(X)) => a!6220!6220U33(mark(X)) mark(U41(X, Y, Z)) => a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y, Z)) => a!6220!6220U42(mark(X), Y, Z) mark(U43(X, Y, Z)) => a!6220!6220U43(mark(X), Y, Z) mark(U44(X, Y, Z)) => a!6220!6220U44(mark(X), Y, Z) mark(U45(X, Y)) => a!6220!6220U45(mark(X), Y) mark(U46(X)) => a!6220!6220U46(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(U61(X)) => a!6220!6220U61(mark(X)) mark(U71(X)) => a!6220!6220U71(mark(X)) mark(U81(X, Y, Z)) => a!6220!6220U81(mark(X), Y, Z) mark(U82(X, Y, Z)) => a!6220!6220U82(mark(X), Y, Z) mark(U83(X, Y, Z)) => a!6220!6220U83(mark(X), Y, Z) mark(U84(X, Y, Z)) => a!6220!6220U84(mark(X), Y, Z) mark(U85(X, Y)) => a!6220!6220U85(mark(X), Y) mark(U86(X)) => a!6220!6220U86(mark(X)) mark(U91(X, Y, Z)) => a!6220!6220U91(mark(X), Y, Z) mark(U92(X, Y, Z)) => a!6220!6220U92(mark(X), Y, Z) mark(U93(X, Y, Z)) => a!6220!6220U93(mark(X), Y, Z) mark(U94(X, Y)) => a!6220!6220U94(mark(X), Y) mark(length(X)) => a!6220!6220length(mark(X)) 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, Y) => U11(X, Y) a!6220!6220U12(X, Y) => U12(X, Y) a!6220!6220isNatIListKind(X) => isNatIListKind(X) a!6220!6220U13(X) => U13(X) a!6220!6220isNatList(X) => isNatList(X) a!6220!6220U21(X, Y) => U21(X, Y) a!6220!6220U22(X, Y) => U22(X, Y) a!6220!6220isNatKind(X) => isNatKind(X) a!6220!6220U23(X) => U23(X) a!6220!6220isNat(X) => isNat(X) a!6220!6220U31(X, Y) => U31(X, Y) a!6220!6220U32(X, Y) => U32(X, Y) a!6220!6220U33(X) => U33(X) a!6220!6220U41(X, Y, Z) => U41(X, Y, Z) a!6220!6220U42(X, Y, Z) => U42(X, Y, Z) a!6220!6220U43(X, Y, Z) => U43(X, Y, Z) a!6220!6220U44(X, Y, Z) => U44(X, Y, Z) a!6220!6220U45(X, Y) => U45(X, Y) a!6220!6220U46(X) => U46(X) a!6220!6220isNatIList(X) => isNatIList(X) a!6220!6220U51(X, Y) => U51(X, Y) a!6220!6220U52(X) => U52(X) a!6220!6220U61(X) => U61(X) a!6220!6220U71(X) => U71(X) a!6220!6220U81(X, Y, Z) => U81(X, Y, Z) a!6220!6220U82(X, Y, Z) => U82(X, Y, Z) a!6220!6220U83(X, Y, Z) => U83(X, Y, Z) a!6220!6220U84(X, Y, Z) => U84(X, Y, Z) a!6220!6220U85(X, Y) => U85(X, Y) a!6220!6220U86(X) => U86(X) a!6220!6220U91(X, Y, Z) => U91(X, Y, Z) a!6220!6220U92(X, Y, Z) => U92(X, Y, Z) a!6220!6220U93(X, Y, Z) => U93(X, Y, Z) a!6220!6220U94(X, Y) => U94(X, Y) a!6220!6220length(X) => length(X) 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!6220U11#(tt, X) =#> a!6220!6220U12#(a!6220!6220isNatIListKind(X), X) 1] a!6220!6220U11#(tt, X) =#> a!6220!6220isNatIListKind#(X) 2] a!6220!6220U12#(tt, X) =#> a!6220!6220U13#(a!6220!6220isNatList(X)) 3] a!6220!6220U12#(tt, X) =#> a!6220!6220isNatList#(X) 4] a!6220!6220U21#(tt, X) =#> a!6220!6220U22#(a!6220!6220isNatKind(X), X) 5] a!6220!6220U21#(tt, X) =#> a!6220!6220isNatKind#(X) 6] a!6220!6220U22#(tt, X) =#> a!6220!6220U23#(a!6220!6220isNat(X)) 7] a!6220!6220U22#(tt, X) =#> a!6220!6220isNat#(X) 8] a!6220!6220U31#(tt, X) =#> a!6220!6220U32#(a!6220!6220isNatIListKind(X), X) 9] a!6220!6220U31#(tt, X) =#> a!6220!6220isNatIListKind#(X) 10] a!6220!6220U32#(tt, X) =#> a!6220!6220U33#(a!6220!6220isNatList(X)) 11] a!6220!6220U32#(tt, X) =#> a!6220!6220isNatList#(X) 12] a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNatKind(X), X, Y) 13] a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNatKind#(X) 14] a!6220!6220U42#(tt, X, Y) =#> a!6220!6220U43#(a!6220!6220isNatIListKind(Y), X, Y) 15] a!6220!6220U42#(tt, X, Y) =#> a!6220!6220isNatIListKind#(Y) 16] a!6220!6220U43#(tt, X, Y) =#> a!6220!6220U44#(a!6220!6220isNatIListKind(Y), X, Y) 17] a!6220!6220U43#(tt, X, Y) =#> a!6220!6220isNatIListKind#(Y) 18] a!6220!6220U44#(tt, X, Y) =#> a!6220!6220U45#(a!6220!6220isNat(X), Y) 19] a!6220!6220U44#(tt, X, Y) =#> a!6220!6220isNat#(X) 20] a!6220!6220U45#(tt, X) =#> a!6220!6220U46#(a!6220!6220isNatIList(X)) 21] a!6220!6220U45#(tt, X) =#> a!6220!6220isNatIList#(X) 22] a!6220!6220U51#(tt, X) =#> a!6220!6220U52#(a!6220!6220isNatIListKind(X)) 23] a!6220!6220U51#(tt, X) =#> a!6220!6220isNatIListKind#(X) 24] a!6220!6220U81#(tt, X, Y) =#> a!6220!6220U82#(a!6220!6220isNatKind(X), X, Y) 25] a!6220!6220U81#(tt, X, Y) =#> a!6220!6220isNatKind#(X) 26] a!6220!6220U82#(tt, X, Y) =#> a!6220!6220U83#(a!6220!6220isNatIListKind(Y), X, Y) 27] a!6220!6220U82#(tt, X, Y) =#> a!6220!6220isNatIListKind#(Y) 28] a!6220!6220U83#(tt, X, Y) =#> a!6220!6220U84#(a!6220!6220isNatIListKind(Y), X, Y) 29] a!6220!6220U83#(tt, X, Y) =#> a!6220!6220isNatIListKind#(Y) 30] a!6220!6220U84#(tt, X, Y) =#> a!6220!6220U85#(a!6220!6220isNat(X), Y) 31] a!6220!6220U84#(tt, X, Y) =#> a!6220!6220isNat#(X) 32] a!6220!6220U85#(tt, X) =#> a!6220!6220U86#(a!6220!6220isNatList(X)) 33] a!6220!6220U85#(tt, X) =#> a!6220!6220isNatList#(X) 34] a!6220!6220U91#(tt, X, Y) =#> a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) 35] a!6220!6220U91#(tt, X, Y) =#> a!6220!6220isNatIListKind#(X) 36] a!6220!6220U92#(tt, X, Y) =#> a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) 37] a!6220!6220U92#(tt, X, Y) =#> a!6220!6220isNat#(Y) 38] a!6220!6220U93#(tt, X, Y) =#> a!6220!6220U94#(a!6220!6220isNatKind(Y), X) 39] a!6220!6220U93#(tt, X, Y) =#> a!6220!6220isNatKind#(Y) 40] a!6220!6220U94#(tt, X) =#> a!6220!6220length#(mark(X)) 41] a!6220!6220U94#(tt, X) =#> mark#(X) 42] a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) 43] a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatIListKind#(X) 44] a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) 45] a!6220!6220isNat#(s(X)) =#> a!6220!6220isNatKind#(X) 46] a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) 47] a!6220!6220isNatIList#(X) =#> a!6220!6220isNatIListKind#(X) 48] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220isNatKind(X), X, Y) 49] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 50] a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220isNatKind(X), Y) 51] a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 52] a!6220!6220isNatKind#(length(X)) =#> a!6220!6220U61#(a!6220!6220isNatIListKind(X)) 53] a!6220!6220isNatKind#(length(X)) =#> a!6220!6220isNatIListKind#(X) 54] a!6220!6220isNatKind#(s(X)) =#> a!6220!6220U71#(a!6220!6220isNatKind(X)) 55] a!6220!6220isNatKind#(s(X)) =#> a!6220!6220isNatKind#(X) 56] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U81#(a!6220!6220isNatKind(X), X, Y) 57] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 58] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) 59] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220isNatList#(Y) 60] mark#(zeros) =#> a!6220!6220zeros# 61] mark#(U11(X, Y)) =#> a!6220!6220U11#(mark(X), Y) 62] mark#(U11(X, Y)) =#> mark#(X) 63] mark#(U12(X, Y)) =#> a!6220!6220U12#(mark(X), Y) 64] mark#(U12(X, Y)) =#> mark#(X) 65] mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) 66] mark#(U13(X)) =#> a!6220!6220U13#(mark(X)) 67] mark#(U13(X)) =#> mark#(X) 68] mark#(isNatList(X)) =#> a!6220!6220isNatList#(X) 69] mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) 70] mark#(U21(X, Y)) =#> mark#(X) 71] mark#(U22(X, Y)) =#> a!6220!6220U22#(mark(X), Y) 72] mark#(U22(X, Y)) =#> mark#(X) 73] mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(X) 74] mark#(U23(X)) =#> a!6220!6220U23#(mark(X)) 75] mark#(U23(X)) =#> mark#(X) 76] mark#(isNat(X)) =#> a!6220!6220isNat#(X) 77] mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) 78] mark#(U31(X, Y)) =#> mark#(X) 79] mark#(U32(X, Y)) =#> a!6220!6220U32#(mark(X), Y) 80] mark#(U32(X, Y)) =#> mark#(X) 81] mark#(U33(X)) =#> a!6220!6220U33#(mark(X)) 82] mark#(U33(X)) =#> mark#(X) 83] mark#(U41(X, Y, Z)) =#> a!6220!6220U41#(mark(X), Y, Z) 84] mark#(U41(X, Y, Z)) =#> mark#(X) 85] mark#(U42(X, Y, Z)) =#> a!6220!6220U42#(mark(X), Y, Z) 86] mark#(U42(X, Y, Z)) =#> mark#(X) 87] mark#(U43(X, Y, Z)) =#> a!6220!6220U43#(mark(X), Y, Z) 88] mark#(U43(X, Y, Z)) =#> mark#(X) 89] mark#(U44(X, Y, Z)) =#> a!6220!6220U44#(mark(X), Y, Z) 90] mark#(U44(X, Y, Z)) =#> mark#(X) 91] mark#(U45(X, Y)) =#> a!6220!6220U45#(mark(X), Y) 92] mark#(U45(X, Y)) =#> mark#(X) 93] mark#(U46(X)) =#> a!6220!6220U46#(mark(X)) 94] mark#(U46(X)) =#> mark#(X) 95] mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) 96] mark#(U51(X, Y)) =#> a!6220!6220U51#(mark(X), Y) 97] mark#(U51(X, Y)) =#> mark#(X) 98] mark#(U52(X)) =#> a!6220!6220U52#(mark(X)) 99] mark#(U52(X)) =#> mark#(X) 100] mark#(U61(X)) =#> a!6220!6220U61#(mark(X)) 101] mark#(U61(X)) =#> mark#(X) 102] mark#(U71(X)) =#> a!6220!6220U71#(mark(X)) 103] mark#(U71(X)) =#> mark#(X) 104] mark#(U81(X, Y, Z)) =#> a!6220!6220U81#(mark(X), Y, Z) 105] mark#(U81(X, Y, Z)) =#> mark#(X) 106] mark#(U82(X, Y, Z)) =#> a!6220!6220U82#(mark(X), Y, Z) 107] mark#(U82(X, Y, Z)) =#> mark#(X) 108] mark#(U83(X, Y, Z)) =#> a!6220!6220U83#(mark(X), Y, Z) 109] mark#(U83(X, Y, Z)) =#> mark#(X) 110] mark#(U84(X, Y, Z)) =#> a!6220!6220U84#(mark(X), Y, Z) 111] mark#(U84(X, Y, Z)) =#> mark#(X) 112] mark#(U85(X, Y)) =#> a!6220!6220U85#(mark(X), Y) 113] mark#(U85(X, Y)) =#> mark#(X) 114] mark#(U86(X)) =#> a!6220!6220U86#(mark(X)) 115] mark#(U86(X)) =#> mark#(X) 116] mark#(U91(X, Y, Z)) =#> a!6220!6220U91#(mark(X), Y, Z) 117] mark#(U91(X, Y, Z)) =#> mark#(X) 118] mark#(U92(X, Y, Z)) =#> a!6220!6220U92#(mark(X), Y, Z) 119] mark#(U92(X, Y, Z)) =#> mark#(X) 120] mark#(U93(X, Y, Z)) =#> a!6220!6220U93#(mark(X), Y, Z) 121] mark#(U93(X, Y, Z)) =#> mark#(X) 122] mark#(U94(X, Y)) =#> a!6220!6220U94#(mark(X), Y) 123] mark#(U94(X, Y)) =#> mark#(X) 124] mark#(length(X)) =#> a!6220!6220length#(mark(X)) 125] mark#(length(X)) =#> mark#(X) 126] mark#(cons(X, Y)) =#> mark#(X) 127] mark#(s(X)) =#> mark#(X) Rules R_0: a!6220!6220zeros => cons(0, zeros) a!6220!6220U11(tt, X) => a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) => a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) => tt a!6220!6220U21(tt, X) => a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) => a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) => tt a!6220!6220U31(tt, X) => a!6220!6220U32(a!6220!6220isNatIListKind(X), X) a!6220!6220U32(tt, X) => a!6220!6220U33(a!6220!6220isNatList(X)) a!6220!6220U33(tt) => tt a!6220!6220U41(tt, X, Y) => a!6220!6220U42(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42(tt, X, Y) => a!6220!6220U43(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43(tt, X, Y) => a!6220!6220U44(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44(tt, X, Y) => a!6220!6220U45(a!6220!6220isNat(X), Y) a!6220!6220U45(tt, X) => a!6220!6220U46(a!6220!6220isNatIList(X)) a!6220!6220U46(tt) => tt a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) => tt a!6220!6220U61(tt) => tt a!6220!6220U71(tt) => tt a!6220!6220U81(tt, X, Y) => a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) => a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) => a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) => a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) => a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) => tt a!6220!6220U91(tt, X, Y) => a!6220!6220U92(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92(tt, X, Y) => a!6220!6220U93(a!6220!6220isNat(Y), X, Y) a!6220!6220U93(tt, X, Y) => a!6220!6220U94(a!6220!6220isNatKind(Y), X) a!6220!6220U94(tt, X) => s(a!6220!6220length(mark(X))) a!6220!6220isNat(0) => tt a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIList(X) => a!6220!6220U31(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList(zeros) => tt a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNatKind(X), X, Y) a!6220!6220isNatIListKind(nil) => tt a!6220!6220isNatIListKind(zeros) => tt a!6220!6220isNatIListKind(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) => tt a!6220!6220isNatKind(length(X)) => a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) => a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) => tt a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220length(nil) => 0 a!6220!6220length(cons(X, Y)) => a!6220!6220U91(a!6220!6220isNatList(Y), Y, X) mark(zeros) => a!6220!6220zeros mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) mark(U12(X, Y)) => a!6220!6220U12(mark(X), Y) mark(isNatIListKind(X)) => a!6220!6220isNatIListKind(X) mark(U13(X)) => a!6220!6220U13(mark(X)) mark(isNatList(X)) => a!6220!6220isNatList(X) mark(U21(X, Y)) => a!6220!6220U21(mark(X), Y) mark(U22(X, Y)) => a!6220!6220U22(mark(X), Y) mark(isNatKind(X)) => a!6220!6220isNatKind(X) mark(U23(X)) => a!6220!6220U23(mark(X)) mark(isNat(X)) => a!6220!6220isNat(X) mark(U31(X, Y)) => a!6220!6220U31(mark(X), Y) mark(U32(X, Y)) => a!6220!6220U32(mark(X), Y) mark(U33(X)) => a!6220!6220U33(mark(X)) mark(U41(X, Y, Z)) => a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y, Z)) => a!6220!6220U42(mark(X), Y, Z) mark(U43(X, Y, Z)) => a!6220!6220U43(mark(X), Y, Z) mark(U44(X, Y, Z)) => a!6220!6220U44(mark(X), Y, Z) mark(U45(X, Y)) => a!6220!6220U45(mark(X), Y) mark(U46(X)) => a!6220!6220U46(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(U61(X)) => a!6220!6220U61(mark(X)) mark(U71(X)) => a!6220!6220U71(mark(X)) mark(U81(X, Y, Z)) => a!6220!6220U81(mark(X), Y, Z) mark(U82(X, Y, Z)) => a!6220!6220U82(mark(X), Y, Z) mark(U83(X, Y, Z)) => a!6220!6220U83(mark(X), Y, Z) mark(U84(X, Y, Z)) => a!6220!6220U84(mark(X), Y, Z) mark(U85(X, Y)) => a!6220!6220U85(mark(X), Y) mark(U86(X)) => a!6220!6220U86(mark(X)) mark(U91(X, Y, Z)) => a!6220!6220U91(mark(X), Y, Z) mark(U92(X, Y, Z)) => a!6220!6220U92(mark(X), Y, Z) mark(U93(X, Y, Z)) => a!6220!6220U93(mark(X), Y, Z) mark(U94(X, Y)) => a!6220!6220U94(mark(X), Y) mark(length(X)) => a!6220!6220length(mark(X)) 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, Y) => U11(X, Y) a!6220!6220U12(X, Y) => U12(X, Y) a!6220!6220isNatIListKind(X) => isNatIListKind(X) a!6220!6220U13(X) => U13(X) a!6220!6220isNatList(X) => isNatList(X) a!6220!6220U21(X, Y) => U21(X, Y) a!6220!6220U22(X, Y) => U22(X, Y) a!6220!6220isNatKind(X) => isNatKind(X) a!6220!6220U23(X) => U23(X) a!6220!6220isNat(X) => isNat(X) a!6220!6220U31(X, Y) => U31(X, Y) a!6220!6220U32(X, Y) => U32(X, Y) a!6220!6220U33(X) => U33(X) a!6220!6220U41(X, Y, Z) => U41(X, Y, Z) a!6220!6220U42(X, Y, Z) => U42(X, Y, Z) a!6220!6220U43(X, Y, Z) => U43(X, Y, Z) a!6220!6220U44(X, Y, Z) => U44(X, Y, Z) a!6220!6220U45(X, Y) => U45(X, Y) a!6220!6220U46(X) => U46(X) a!6220!6220isNatIList(X) => isNatIList(X) a!6220!6220U51(X, Y) => U51(X, Y) a!6220!6220U52(X) => U52(X) a!6220!6220U61(X) => U61(X) a!6220!6220U71(X) => U71(X) a!6220!6220U81(X, Y, Z) => U81(X, Y, Z) a!6220!6220U82(X, Y, Z) => U82(X, Y, Z) a!6220!6220U83(X, Y, Z) => U83(X, Y, Z) a!6220!6220U84(X, Y, Z) => U84(X, Y, Z) a!6220!6220U85(X, Y) => U85(X, Y) a!6220!6220U86(X) => U86(X) a!6220!6220U91(X, Y, Z) => U91(X, Y, Z) a!6220!6220U92(X, Y, Z) => U92(X, Y, Z) a!6220!6220U93(X, Y, Z) => U93(X, Y, Z) a!6220!6220U94(X, Y) => U94(X, Y) a!6220!6220length(X) => length(X) 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 : 2, 3 * 1 : 50, 51 * 2 : * 3 : 56, 57 * 4 : 6, 7 * 5 : 52, 53, 54, 55 * 6 : * 7 : 42, 43, 44, 45 * 8 : 10, 11 * 9 : 50, 51 * 10 : * 11 : 56, 57 * 12 : 14, 15 * 13 : 52, 53, 54, 55 * 14 : 16, 17 * 15 : 50, 51 * 16 : 18, 19 * 17 : 50, 51 * 18 : 20, 21 * 19 : 42, 43, 44, 45 * 20 : * 21 : 46, 47, 48, 49 * 22 : * 23 : 50, 51 * 24 : 26, 27 * 25 : 52, 53, 54, 55 * 26 : 28, 29 * 27 : 50, 51 * 28 : 30, 31 * 29 : 50, 51 * 30 : 32, 33 * 31 : 42, 43, 44, 45 * 32 : * 33 : 56, 57 * 34 : 36, 37 * 35 : 50, 51 * 36 : 38, 39 * 37 : 42, 43, 44, 45 * 38 : 40, 41 * 39 : 52, 53, 54, 55 * 40 : 58, 59 * 41 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 42 : 0, 1 * 43 : 50, 51 * 44 : 4, 5 * 45 : 52, 53, 54, 55 * 46 : 8, 9 * 47 : 50, 51 * 48 : 12, 13 * 49 : 52, 53, 54, 55 * 50 : 22, 23 * 51 : 52, 53, 54, 55 * 52 : * 53 : 50, 51 * 54 : * 55 : 52, 53, 54, 55 * 56 : 24, 25 * 57 : 52, 53, 54, 55 * 58 : 34, 35 * 59 : 56, 57 * 60 : * 61 : 0, 1 * 62 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 63 : 2, 3 * 64 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 65 : 50, 51 * 66 : * 67 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 68 : 56, 57 * 69 : 4, 5 * 70 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 71 : 6, 7 * 72 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 73 : 52, 53, 54, 55 * 74 : * 75 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 76 : 42, 43, 44, 45 * 77 : 8, 9 * 78 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 79 : 10, 11 * 80 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 81 : * 82 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 83 : 12, 13 * 84 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 85 : 14, 15 * 86 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 87 : 16, 17 * 88 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 89 : 18, 19 * 90 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 91 : 20, 21 * 92 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 93 : * 94 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 95 : 46, 47, 48, 49 * 96 : 22, 23 * 97 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 98 : * 99 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 100 : * 101 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 102 : * 103 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 104 : 24, 25 * 105 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 106 : 26, 27 * 107 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 108 : 28, 29 * 109 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 110 : 30, 31 * 111 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 112 : 32, 33 * 113 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 114 : * 115 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 116 : 34, 35 * 117 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 118 : 36, 37 * 119 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 120 : 38, 39 * 121 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 122 : 40, 41 * 123 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 124 : 58, 59 * 125 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 126 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 * 127 : 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 This graph has the following strongly connected components: P_1: a!6220!6220U11#(tt, X) =#> a!6220!6220U12#(a!6220!6220isNatIListKind(X), X) a!6220!6220U12#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) =#> a!6220!6220U22#(a!6220!6220isNatKind(X), X) a!6220!6220U22#(tt, X) =#> a!6220!6220isNat#(X) a!6220!6220U81#(tt, X, Y) =#> a!6220!6220U82#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82#(tt, X, Y) =#> a!6220!6220U83#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83#(tt, X, Y) =#> a!6220!6220U84#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84#(tt, X, Y) =#> a!6220!6220U85#(a!6220!6220isNat(X), Y) a!6220!6220U84#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U85#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U81#(a!6220!6220isNatKind(X), X, Y) P_2: a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42#(tt, X, Y) =#> a!6220!6220U43#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43#(tt, X, Y) =#> a!6220!6220U44#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44#(tt, X, Y) =#> a!6220!6220U45#(a!6220!6220isNat(X), Y) a!6220!6220U45#(tt, X) =#> a!6220!6220isNatIList#(X) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220isNatKind(X), X, Y) P_3: a!6220!6220U51#(tt, X) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220isNatKind(X), Y) a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatKind#(length(X)) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNatKind#(s(X)) =#> a!6220!6220isNatKind#(X) P_4: a!6220!6220U91#(tt, X, Y) =#> a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92#(tt, X, Y) =#> a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) =#> a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220U94#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220U94#(tt, X) =#> mark#(X) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X, Y)) =#> mark#(X) mark#(U13(X)) =#> mark#(X) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X, Y)) =#> mark#(X) mark#(U23(X)) =#> mark#(X) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X, Y)) =#> mark#(X) mark#(U33(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(U43(X, Y, Z)) =#> mark#(X) mark#(U44(X, Y, Z)) =#> mark#(X) mark#(U45(X, Y)) =#> mark#(X) mark#(U46(X)) =#> mark#(X) mark#(U51(X, Y)) =#> mark#(X) mark#(U52(X)) =#> mark#(X) mark#(U61(X)) =#> mark#(X) mark#(U71(X)) =#> mark#(X) mark#(U81(X, Y, Z)) =#> mark#(X) mark#(U82(X, Y, Z)) =#> mark#(X) mark#(U83(X, Y, Z)) =#> mark#(X) mark#(U84(X, Y, Z)) =#> mark#(X) mark#(U85(X, Y)) =#> mark#(X) mark#(U86(X)) =#> mark#(X) mark#(U91(X, Y, Z)) =#> a!6220!6220U91#(mark(X), Y, Z) mark#(U91(X, Y, Z)) =#> mark#(X) mark#(U92(X, Y, Z)) =#> a!6220!6220U92#(mark(X), Y, Z) mark#(U92(X, Y, Z)) =#> mark#(X) mark#(U93(X, Y, Z)) =#> a!6220!6220U93#(mark(X), Y, Z) mark#(U93(X, Y, Z)) =#> mark#(X) mark#(U94(X, Y)) =#> a!6220!6220U94#(mark(X), Y) mark#(U94(X, Y)) =#> mark#(X) mark#(length(X)) =#> a!6220!6220length#(mark(X)) mark#(length(X)) =#> mark#(X) 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), (P_2, R_0, m, f), (P_3, R_0, m, f) and (P_4, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, 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!6220U91#(tt, X, Y) >? a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92#(tt, X, Y) >? a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) >? a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220U94#(tt, X) >? a!6220!6220length#(mark(X)) a!6220!6220U94#(tt, X) >? mark#(X) a!6220!6220length#(cons(X, Y)) >? a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X, Y)) >? mark#(X) mark#(U13(X)) >? mark#(X) mark#(U21(X, Y)) >? mark#(X) mark#(U22(X, Y)) >? mark#(X) mark#(U23(X)) >? mark#(X) mark#(U31(X, Y)) >? mark#(X) mark#(U32(X, Y)) >? mark#(X) mark#(U33(X)) >? mark#(X) mark#(U41(X, Y, Z)) >? mark#(X) mark#(U42(X, Y, Z)) >? mark#(X) mark#(U43(X, Y, Z)) >? mark#(X) mark#(U44(X, Y, Z)) >? mark#(X) mark#(U45(X, Y)) >? mark#(X) mark#(U46(X)) >? mark#(X) mark#(U51(X, Y)) >? mark#(X) mark#(U52(X)) >? mark#(X) mark#(U61(X)) >? mark#(X) mark#(U71(X)) >? mark#(X) mark#(U81(X, Y, Z)) >? mark#(X) mark#(U82(X, Y, Z)) >? mark#(X) mark#(U83(X, Y, Z)) >? mark#(X) mark#(U84(X, Y, Z)) >? mark#(X) mark#(U85(X, Y)) >? mark#(X) mark#(U86(X)) >? mark#(X) mark#(U91(X, Y, Z)) >? a!6220!6220U91#(mark(X), Y, Z) mark#(U91(X, Y, Z)) >? mark#(X) mark#(U92(X, Y, Z)) >? a!6220!6220U92#(mark(X), Y, Z) mark#(U92(X, Y, Z)) >? mark#(X) mark#(U93(X, Y, Z)) >? a!6220!6220U93#(mark(X), Y, Z) mark#(U93(X, Y, Z)) >? mark#(X) mark#(U94(X, Y)) >? a!6220!6220U94#(mark(X), Y) mark#(U94(X, Y)) >? mark#(X) mark#(length(X)) >? a!6220!6220length#(mark(X)) mark#(length(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220zeros >= cons(0, zeros) a!6220!6220U11(tt, X) >= a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) >= a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) >= a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) >= tt a!6220!6220U31(tt, X) >= a!6220!6220U32(a!6220!6220isNatIListKind(X), X) a!6220!6220U32(tt, X) >= a!6220!6220U33(a!6220!6220isNatList(X)) a!6220!6220U33(tt) >= tt a!6220!6220U41(tt, X, Y) >= a!6220!6220U42(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42(tt, X, Y) >= a!6220!6220U43(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43(tt, X, Y) >= a!6220!6220U44(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44(tt, X, Y) >= a!6220!6220U45(a!6220!6220isNat(X), Y) a!6220!6220U45(tt, X) >= a!6220!6220U46(a!6220!6220isNatIList(X)) a!6220!6220U46(tt) >= tt a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) >= tt a!6220!6220U61(tt) >= tt a!6220!6220U71(tt) >= tt a!6220!6220U81(tt, X, Y) >= a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) >= a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) >= a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) >= a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) >= a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) >= tt a!6220!6220U91(tt, X, Y) >= a!6220!6220U92(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92(tt, X, Y) >= a!6220!6220U93(a!6220!6220isNat(Y), X, Y) a!6220!6220U93(tt, X, Y) >= a!6220!6220U94(a!6220!6220isNatKind(Y), X) a!6220!6220U94(tt, X) >= s(a!6220!6220length(mark(X))) a!6220!6220isNat(0) >= tt a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIList(X) >= a!6220!6220U31(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList(zeros) >= tt a!6220!6220isNatIList(cons(X, Y)) >= a!6220!6220U41(a!6220!6220isNatKind(X), X, Y) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) >= a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220length(nil) >= 0 a!6220!6220length(cons(X, Y)) >= a!6220!6220U91(a!6220!6220isNatList(Y), Y, X) mark(zeros) >= a!6220!6220zeros mark(U11(X, Y)) >= a!6220!6220U11(mark(X), Y) mark(U12(X, Y)) >= a!6220!6220U12(mark(X), Y) mark(isNatIListKind(X)) >= a!6220!6220isNatIListKind(X) mark(U13(X)) >= a!6220!6220U13(mark(X)) mark(isNatList(X)) >= a!6220!6220isNatList(X) mark(U21(X, Y)) >= a!6220!6220U21(mark(X), Y) mark(U22(X, Y)) >= a!6220!6220U22(mark(X), Y) mark(isNatKind(X)) >= a!6220!6220isNatKind(X) mark(U23(X)) >= a!6220!6220U23(mark(X)) mark(isNat(X)) >= a!6220!6220isNat(X) mark(U31(X, Y)) >= a!6220!6220U31(mark(X), Y) mark(U32(X, Y)) >= a!6220!6220U32(mark(X), Y) mark(U33(X)) >= a!6220!6220U33(mark(X)) mark(U41(X, Y, Z)) >= a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y, Z)) >= a!6220!6220U42(mark(X), Y, Z) mark(U43(X, Y, Z)) >= a!6220!6220U43(mark(X), Y, Z) mark(U44(X, Y, Z)) >= a!6220!6220U44(mark(X), Y, Z) mark(U45(X, Y)) >= a!6220!6220U45(mark(X), Y) mark(U46(X)) >= a!6220!6220U46(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(U61(X)) >= a!6220!6220U61(mark(X)) mark(U71(X)) >= a!6220!6220U71(mark(X)) mark(U81(X, Y, Z)) >= a!6220!6220U81(mark(X), Y, Z) mark(U82(X, Y, Z)) >= a!6220!6220U82(mark(X), Y, Z) mark(U83(X, Y, Z)) >= a!6220!6220U83(mark(X), Y, Z) mark(U84(X, Y, Z)) >= a!6220!6220U84(mark(X), Y, Z) mark(U85(X, Y)) >= a!6220!6220U85(mark(X), Y) mark(U86(X)) >= a!6220!6220U86(mark(X)) mark(U91(X, Y, Z)) >= a!6220!6220U91(mark(X), Y, Z) mark(U92(X, Y, Z)) >= a!6220!6220U92(mark(X), Y, Z) mark(U93(X, Y, Z)) >= a!6220!6220U93(mark(X), Y, Z) mark(U94(X, Y)) >= a!6220!6220U94(mark(X), Y) mark(length(X)) >= a!6220!6220length(mark(X)) 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, Y) >= U11(X, Y) a!6220!6220U12(X, Y) >= U12(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220U13(X) >= U13(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X, Y) >= U22(X, Y) a!6220!6220isNatKind(X) >= isNatKind(X) a!6220!6220U23(X) >= U23(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U31(X, Y) >= U31(X, Y) a!6220!6220U32(X, Y) >= U32(X, Y) a!6220!6220U33(X) >= U33(X) a!6220!6220U41(X, Y, Z) >= U41(X, Y, Z) a!6220!6220U42(X, Y, Z) >= U42(X, Y, Z) a!6220!6220U43(X, Y, Z) >= U43(X, Y, Z) a!6220!6220U44(X, Y, Z) >= U44(X, Y, Z) a!6220!6220U45(X, Y) >= U45(X, Y) a!6220!6220U46(X) >= U46(X) a!6220!6220isNatIList(X) >= isNatIList(X) a!6220!6220U51(X, Y) >= U51(X, Y) a!6220!6220U52(X) >= U52(X) a!6220!6220U61(X) >= U61(X) a!6220!6220U71(X) >= U71(X) a!6220!6220U81(X, Y, Z) >= U81(X, Y, Z) a!6220!6220U82(X, Y, Z) >= U82(X, Y, Z) a!6220!6220U83(X, Y, Z) >= U83(X, Y, Z) a!6220!6220U84(X, Y, Z) >= U84(X, Y, Z) a!6220!6220U85(X, Y) >= U85(X, Y) a!6220!6220U86(X) >= U86(X) a!6220!6220U91(X, Y, Z) >= U91(X, Y, Z) a!6220!6220U92(X, Y, Z) >= U92(X, Y, Z) a!6220!6220U93(X, Y, Z) >= U93(X, Y, Z) a!6220!6220U94(X, Y) >= U94(X, Y) a!6220!6220length(X) >= length(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.y0 U12 = \y0y1.y0 U13 = \y0.y0 U21 = \y0y1.y0 U22 = \y0y1.y0 U23 = \y0.y0 U31 = \y0y1.y0 U32 = \y0y1.y0 U33 = \y0.y0 U41 = \y0y1y2.y0 U42 = \y0y1y2.y0 U43 = \y0y1y2.y0 U44 = \y0y1y2.y0 U45 = \y0y1.y0 U46 = \y0.y0 U51 = \y0y1.y0 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0.y0 U81 = \y0y1y2.2y0 U82 = \y0y1y2.2y0 U83 = \y0y1y2.y0 U84 = \y0y1y2.y0 U85 = \y0y1.y0 U86 = \y0.y0 U91 = \y0y1y2.1 + y0 + y1 U92 = \y0y1y2.1 + y0 + y1 U93 = \y0y1y2.2 + y1 + 2y0 U94 = \y0y1.1 + 2y0 + 2y1 a!6220!6220U11 = \y0y1.y0 a!6220!6220U12 = \y0y1.y0 a!6220!6220U13 = \y0.y0 a!6220!6220U21 = \y0y1.y0 a!6220!6220U22 = \y0y1.y0 a!6220!6220U23 = \y0.y0 a!6220!6220U31 = \y0y1.y0 a!6220!6220U32 = \y0y1.y0 a!6220!6220U33 = \y0.y0 a!6220!6220U41 = \y0y1y2.y0 a!6220!6220U42 = \y0y1y2.y0 a!6220!6220U43 = \y0y1y2.y0 a!6220!6220U44 = \y0y1y2.y0 a!6220!6220U45 = \y0y1.y0 a!6220!6220U46 = \y0.y0 a!6220!6220U51 = \y0y1.y0 a!6220!6220U52 = \y0.y0 a!6220!6220U61 = \y0.y0 a!6220!6220U71 = \y0.y0 a!6220!6220U81 = \y0y1y2.2y0 a!6220!6220U82 = \y0y1y2.2y0 a!6220!6220U83 = \y0y1y2.y0 a!6220!6220U84 = \y0y1y2.y0 a!6220!6220U85 = \y0y1.y0 a!6220!6220U86 = \y0.y0 a!6220!6220U91 = \y0y1y2.2 + y0 + 2y1 a!6220!6220U91# = \y0y1y2.2y1 a!6220!6220U92 = \y0y1y2.2 + y0 + 2y1 a!6220!6220U92# = \y0y1y2.2y1 a!6220!6220U93 = \y0y1y2.2 + 2y0 + 2y1 a!6220!6220U93# = \y0y1y2.2y1 a!6220!6220U94 = \y0y1.2 + 2y0 + 2y1 a!6220!6220U94# = \y0y1.2y1 a!6220!6220isNat = \y0.0 a!6220!6220isNatIList = \y0.0 a!6220!6220isNatIListKind = \y0.0 a!6220!6220isNatKind = \y0.0 a!6220!6220isNatList = \y0.0 a!6220!6220length = \y0.2 + y0 a!6220!6220length# = \y0.y0 a!6220!6220zeros = 0 cons = \y0y1.y0 + 2y1 isNat = \y0.0 isNatIList = \y0.0 isNatIListKind = \y0.0 isNatKind = \y0.0 isNatList = \y0.0 length = \y0.1 + y0 mark = \y0.2y0 mark# = \y0.2y0 nil = 0 s = \y0.y0 tt = 0 zeros = 0 Using this interpretation, the requirements translate to: [[a!6220!6220U91#(tt, _x0, _x1)]] = 2x0 >= 2x0 = [[a!6220!6220U92#(a!6220!6220isNatIListKind(_x0), _x0, _x1)]] [[a!6220!6220U92#(tt, _x0, _x1)]] = 2x0 >= 2x0 = [[a!6220!6220U93#(a!6220!6220isNat(_x1), _x0, _x1)]] [[a!6220!6220U93#(tt, _x0, _x1)]] = 2x0 >= 2x0 = [[a!6220!6220U94#(a!6220!6220isNatKind(_x1), _x0)]] [[a!6220!6220U94#(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220length#(mark(_x0))]] [[a!6220!6220U94#(tt, _x0)]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[a!6220!6220length#(cons(_x0, _x1))]] = x0 + 2x1 >= 2x1 = [[a!6220!6220U91#(a!6220!6220isNatList(_x1), _x1, _x0)]] [[mark#(U11(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U12(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U13(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U21(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U22(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U23(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U31(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U32(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U33(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U41(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U42(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U43(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U44(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U45(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U46(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U51(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U52(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U61(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U71(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U81(_x0, _x1, _x2))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U82(_x0, _x1, _x2))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U83(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U84(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U85(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U86(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U91(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 > 2x1 = [[a!6220!6220U91#(mark(_x0), _x1, _x2)]] [[mark#(U91(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 > 2x0 = [[mark#(_x0)]] [[mark#(U92(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 > 2x1 = [[a!6220!6220U92#(mark(_x0), _x1, _x2)]] [[mark#(U92(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 > 2x0 = [[mark#(_x0)]] [[mark#(U93(_x0, _x1, _x2))]] = 4 + 2x1 + 4x0 > 2x1 = [[a!6220!6220U93#(mark(_x0), _x1, _x2)]] [[mark#(U93(_x0, _x1, _x2))]] = 4 + 2x1 + 4x0 > 2x0 = [[mark#(_x0)]] [[mark#(U94(_x0, _x1))]] = 2 + 4x0 + 4x1 > 2x1 = [[a!6220!6220U94#(mark(_x0), _x1)]] [[mark#(U94(_x0, _x1))]] = 2 + 4x0 + 4x1 > 2x0 = [[mark#(_x0)]] [[mark#(length(_x0))]] = 2 + 2x0 > 2x0 = [[a!6220!6220length#(mark(_x0))]] [[mark#(length(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] [[a!6220!6220U11(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U12(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220U12(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U13(a!6220!6220isNatList(_x0))]] [[a!6220!6220U13(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U21(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U22(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220U22(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U23(a!6220!6220isNat(_x0))]] [[a!6220!6220U23(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U31(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U32(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220U32(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U33(a!6220!6220isNatList(_x0))]] [[a!6220!6220U33(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U41(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U42(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220U42(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U43(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U43(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U44(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U44(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U45(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U45(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U46(a!6220!6220isNatIList(_x0))]] [[a!6220!6220U46(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U51(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U52(a!6220!6220isNatIListKind(_x0))]] [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U61(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U71(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U81(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U82(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220U82(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U83(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U83(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U84(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U84(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U85(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U85(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U86(a!6220!6220isNatList(_x0))]] [[a!6220!6220U86(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U91(tt, _x0, _x1)]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220U92(a!6220!6220isNatIListKind(_x0), _x0, _x1)]] [[a!6220!6220U92(tt, _x0, _x1)]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220U93(a!6220!6220isNat(_x1), _x0, _x1)]] [[a!6220!6220U93(tt, _x0, _x1)]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220U94(a!6220!6220isNatKind(_x1), _x0)]] [[a!6220!6220U94(tt, _x0)]] = 2 + 2x0 >= 2 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNat(length(_x0))]] = 0 >= 0 = [[a!6220!6220U11(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNat(s(_x0))]] = 0 >= 0 = [[a!6220!6220U21(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[a!6220!6220U31(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U41(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220isNatIListKind(nil)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatIListKind(zeros)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatIListKind(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U51(a!6220!6220isNatKind(_x0), _x1)]] [[a!6220!6220isNatKind(0)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatKind(length(_x0))]] = 0 >= 0 = [[a!6220!6220U61(a!6220!6220isNatIListKind(_x0))]] [[a!6220!6220isNatKind(s(_x0))]] = 0 >= 0 = [[a!6220!6220U71(a!6220!6220isNatKind(_x0))]] [[a!6220!6220isNatList(nil)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U81(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220length(nil)]] = 2 >= 0 = [[0]] [[a!6220!6220length(cons(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + 2x1 = [[a!6220!6220U91(a!6220!6220isNatList(_x1), _x1, _x0)]] [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] [[mark(U11(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U11(mark(_x0), _x1)]] [[mark(U12(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U12(mark(_x0), _x1)]] [[mark(isNatIListKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind(_x0)]] [[mark(U13(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U13(mark(_x0))]] [[mark(isNatList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatList(_x0)]] [[mark(U21(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0), _x1)]] [[mark(U22(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U22(mark(_x0), _x1)]] [[mark(isNatKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind(_x0)]] [[mark(U23(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U23(mark(_x0))]] [[mark(isNat(_x0))]] = 0 >= 0 = [[a!6220!6220isNat(_x0)]] [[mark(U31(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U31(mark(_x0), _x1)]] [[mark(U32(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U32(mark(_x0), _x1)]] [[mark(U33(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U33(mark(_x0))]] [[mark(U41(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U41(mark(_x0), _x1, _x2)]] [[mark(U42(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0), _x1, _x2)]] [[mark(U43(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U43(mark(_x0), _x1, _x2)]] [[mark(U44(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U44(mark(_x0), _x1, _x2)]] [[mark(U45(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U45(mark(_x0), _x1)]] [[mark(U46(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U46(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(U61(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U61(mark(_x0))]] [[mark(U71(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U71(mark(_x0))]] [[mark(U81(_x0, _x1, _x2))]] = 4x0 >= 4x0 = [[a!6220!6220U81(mark(_x0), _x1, _x2)]] [[mark(U82(_x0, _x1, _x2))]] = 4x0 >= 4x0 = [[a!6220!6220U82(mark(_x0), _x1, _x2)]] [[mark(U83(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U83(mark(_x0), _x1, _x2)]] [[mark(U84(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U84(mark(_x0), _x1, _x2)]] [[mark(U85(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U85(mark(_x0), _x1)]] [[mark(U86(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U86(mark(_x0))]] [[mark(U91(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[a!6220!6220U91(mark(_x0), _x1, _x2)]] [[mark(U92(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[a!6220!6220U92(mark(_x0), _x1, _x2)]] [[mark(U93(_x0, _x1, _x2))]] = 4 + 2x1 + 4x0 >= 2 + 2x1 + 4x0 = [[a!6220!6220U93(mark(_x0), _x1, _x2)]] [[mark(U94(_x0, _x1))]] = 2 + 4x0 + 4x1 >= 2 + 2x1 + 4x0 = [[a!6220!6220U94(mark(_x0), _x1)]] [[mark(length(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220length(mark(_x0))]] [[mark(cons(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[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, _x1)]] = x0 >= x0 = [[U11(_x0, _x1)]] [[a!6220!6220U12(_x0, _x1)]] = x0 >= x0 = [[U12(_x0, _x1)]] [[a!6220!6220isNatIListKind(_x0)]] = 0 >= 0 = [[isNatIListKind(_x0)]] [[a!6220!6220U13(_x0)]] = x0 >= x0 = [[U13(_x0)]] [[a!6220!6220isNatList(_x0)]] = 0 >= 0 = [[isNatList(_x0)]] [[a!6220!6220U21(_x0, _x1)]] = x0 >= x0 = [[U21(_x0, _x1)]] [[a!6220!6220U22(_x0, _x1)]] = x0 >= x0 = [[U22(_x0, _x1)]] [[a!6220!6220isNatKind(_x0)]] = 0 >= 0 = [[isNatKind(_x0)]] [[a!6220!6220U23(_x0)]] = x0 >= x0 = [[U23(_x0)]] [[a!6220!6220isNat(_x0)]] = 0 >= 0 = [[isNat(_x0)]] [[a!6220!6220U31(_x0, _x1)]] = x0 >= x0 = [[U31(_x0, _x1)]] [[a!6220!6220U32(_x0, _x1)]] = x0 >= x0 = [[U32(_x0, _x1)]] [[a!6220!6220U33(_x0)]] = x0 >= x0 = [[U33(_x0)]] [[a!6220!6220U41(_x0, _x1, _x2)]] = x0 >= x0 = [[U41(_x0, _x1, _x2)]] [[a!6220!6220U42(_x0, _x1, _x2)]] = x0 >= x0 = [[U42(_x0, _x1, _x2)]] [[a!6220!6220U43(_x0, _x1, _x2)]] = x0 >= x0 = [[U43(_x0, _x1, _x2)]] [[a!6220!6220U44(_x0, _x1, _x2)]] = x0 >= x0 = [[U44(_x0, _x1, _x2)]] [[a!6220!6220U45(_x0, _x1)]] = x0 >= x0 = [[U45(_x0, _x1)]] [[a!6220!6220U46(_x0)]] = x0 >= x0 = [[U46(_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!6220U61(_x0)]] = x0 >= x0 = [[U61(_x0)]] [[a!6220!6220U71(_x0)]] = x0 >= x0 = [[U71(_x0)]] [[a!6220!6220U81(_x0, _x1, _x2)]] = 2x0 >= 2x0 = [[U81(_x0, _x1, _x2)]] [[a!6220!6220U82(_x0, _x1, _x2)]] = 2x0 >= 2x0 = [[U82(_x0, _x1, _x2)]] [[a!6220!6220U83(_x0, _x1, _x2)]] = x0 >= x0 = [[U83(_x0, _x1, _x2)]] [[a!6220!6220U84(_x0, _x1, _x2)]] = x0 >= x0 = [[U84(_x0, _x1, _x2)]] [[a!6220!6220U85(_x0, _x1)]] = x0 >= x0 = [[U85(_x0, _x1)]] [[a!6220!6220U86(_x0)]] = x0 >= x0 = [[U86(_x0)]] [[a!6220!6220U91(_x0, _x1, _x2)]] = 2 + x0 + 2x1 >= 1 + x0 + x1 = [[U91(_x0, _x1, _x2)]] [[a!6220!6220U92(_x0, _x1, _x2)]] = 2 + x0 + 2x1 >= 1 + x0 + x1 = [[U92(_x0, _x1, _x2)]] [[a!6220!6220U93(_x0, _x1, _x2)]] = 2 + 2x0 + 2x1 >= 2 + x1 + 2x0 = [[U93(_x0, _x1, _x2)]] [[a!6220!6220U94(_x0, _x1)]] = 2 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[U94(_x0, _x1)]] [[a!6220!6220length(_x0)]] = 2 + x0 >= 1 + x0 = [[length(_x0)]] 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_5, R_0, minimal, formative), where P_5 consists of: a!6220!6220U91#(tt, X, Y) =#> a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92#(tt, X, Y) =#> a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) =#> a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220U94#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220U94#(tt, X) =#> mark#(X) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X, Y)) =#> mark#(X) mark#(U13(X)) =#> mark#(X) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X, Y)) =#> mark#(X) mark#(U23(X)) =#> mark#(X) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X, Y)) =#> mark#(X) mark#(U33(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(U43(X, Y, Z)) =#> mark#(X) mark#(U44(X, Y, Z)) =#> mark#(X) mark#(U45(X, Y)) =#> mark#(X) mark#(U46(X)) =#> mark#(X) mark#(U51(X, Y)) =#> mark#(X) mark#(U52(X)) =#> mark#(X) mark#(U61(X)) =#> mark#(X) mark#(U71(X)) =#> mark#(X) mark#(U81(X, Y, Z)) =#> mark#(X) mark#(U82(X, Y, Z)) =#> mark#(X) mark#(U83(X, Y, Z)) =#> mark#(X) mark#(U84(X, Y, Z)) =#> mark#(X) mark#(U85(X, Y)) =#> mark#(X) mark#(U86(X)) =#> 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_2, R_0, minimal, formative), (P_3, 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 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 : 3, 4 * 3 : 5 * 4 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 5 : 0 * 6 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 7 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 8 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 9 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 10 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 11 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 12 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 13 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 14 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 15 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 16 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 17 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 18 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 19 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 20 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 21 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 22 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 23 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 24 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 25 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 26 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 27 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 28 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 29 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 30 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 31 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 * 32 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 This graph has the following strongly connected components: P_6: a!6220!6220U91#(tt, X, Y) =#> a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92#(tt, X, Y) =#> a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) =#> a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220U94#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) P_7: mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X, Y)) =#> mark#(X) mark#(U13(X)) =#> mark#(X) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X, Y)) =#> mark#(X) mark#(U23(X)) =#> mark#(X) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X, Y)) =#> mark#(X) mark#(U33(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(U43(X, Y, Z)) =#> mark#(X) mark#(U44(X, Y, Z)) =#> mark#(X) mark#(U45(X, Y)) =#> mark#(X) mark#(U46(X)) =#> mark#(X) mark#(U51(X, Y)) =#> mark#(X) mark#(U52(X)) =#> mark#(X) mark#(U61(X)) =#> mark#(X) mark#(U71(X)) =#> mark#(X) mark#(U81(X, Y, Z)) =#> mark#(X) mark#(U82(X, Y, Z)) =#> mark#(X) mark#(U83(X, Y, Z)) =#> mark#(X) mark#(U84(X, Y, Z)) =#> mark#(X) mark#(U85(X, Y)) =#> mark#(X) mark#(U86(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(s(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_5, R_0, m, f) by (P_6, R_0, m, f) and (P_7, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_6, 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 apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(U11(X, Y))) = U11(X, Y) |> X = nu(mark#(X)) nu(mark#(U12(X, Y))) = U12(X, Y) |> X = nu(mark#(X)) nu(mark#(U13(X))) = U13(X) |> X = nu(mark#(X)) nu(mark#(U21(X, Y))) = U21(X, Y) |> X = nu(mark#(X)) nu(mark#(U22(X, Y))) = U22(X, Y) |> X = nu(mark#(X)) nu(mark#(U23(X))) = U23(X) |> X = nu(mark#(X)) nu(mark#(U31(X, Y))) = U31(X, Y) |> X = nu(mark#(X)) nu(mark#(U32(X, Y))) = U32(X, Y) |> X = nu(mark#(X)) nu(mark#(U33(X))) = U33(X) |> X = nu(mark#(X)) nu(mark#(U41(X, Y, Z))) = U41(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U42(X, Y, Z))) = U42(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U43(X, Y, Z))) = U43(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U44(X, Y, Z))) = U44(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U45(X, Y))) = U45(X, Y) |> X = nu(mark#(X)) nu(mark#(U46(X))) = U46(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))) = U61(X) |> X = nu(mark#(X)) nu(mark#(U71(X))) = U71(X) |> X = nu(mark#(X)) nu(mark#(U81(X, Y, Z))) = U81(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U82(X, Y, Z))) = U82(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U83(X, Y, Z))) = U83(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U84(X, Y, Z))) = U84(X, Y, Z) |> X = nu(mark#(X)) nu(mark#(U85(X, Y))) = U85(X, Y) |> X = nu(mark#(X)) nu(mark#(U86(X))) = U86(X) |> 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_7, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, 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 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) >? a!6220!6220U92#(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92#(tt, X, Y) >? a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) >? a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220U94#(tt, X) >? a!6220!6220length#(mark(X)) a!6220!6220length#(cons(X, Y)) >? a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) a!6220!6220zeros >= cons(0, zeros) a!6220!6220U11(tt, X) >= a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) >= a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) >= a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) >= tt a!6220!6220U31(tt, X) >= a!6220!6220U32(a!6220!6220isNatIListKind(X), X) a!6220!6220U32(tt, X) >= a!6220!6220U33(a!6220!6220isNatList(X)) a!6220!6220U33(tt) >= tt a!6220!6220U41(tt, X, Y) >= a!6220!6220U42(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42(tt, X, Y) >= a!6220!6220U43(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43(tt, X, Y) >= a!6220!6220U44(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44(tt, X, Y) >= a!6220!6220U45(a!6220!6220isNat(X), Y) a!6220!6220U45(tt, X) >= a!6220!6220U46(a!6220!6220isNatIList(X)) a!6220!6220U46(tt) >= tt a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) >= tt a!6220!6220U61(tt) >= tt a!6220!6220U71(tt) >= tt a!6220!6220U81(tt, X, Y) >= a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) >= a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) >= a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) >= a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) >= a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) >= tt a!6220!6220U91(tt, X, Y) >= a!6220!6220U92(a!6220!6220isNatIListKind(X), X, Y) a!6220!6220U92(tt, X, Y) >= a!6220!6220U93(a!6220!6220isNat(Y), X, Y) a!6220!6220U93(tt, X, Y) >= a!6220!6220U94(a!6220!6220isNatKind(Y), X) a!6220!6220U94(tt, X) >= s(a!6220!6220length(mark(X))) a!6220!6220isNat(0) >= tt a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIList(X) >= a!6220!6220U31(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList(zeros) >= tt a!6220!6220isNatIList(cons(X, Y)) >= a!6220!6220U41(a!6220!6220isNatKind(X), X, Y) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) >= a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220length(nil) >= 0 a!6220!6220length(cons(X, Y)) >= a!6220!6220U91(a!6220!6220isNatList(Y), Y, X) mark(zeros) >= a!6220!6220zeros mark(U11(X, Y)) >= a!6220!6220U11(mark(X), Y) mark(U12(X, Y)) >= a!6220!6220U12(mark(X), Y) mark(isNatIListKind(X)) >= a!6220!6220isNatIListKind(X) mark(U13(X)) >= a!6220!6220U13(mark(X)) mark(isNatList(X)) >= a!6220!6220isNatList(X) mark(U21(X, Y)) >= a!6220!6220U21(mark(X), Y) mark(U22(X, Y)) >= a!6220!6220U22(mark(X), Y) mark(isNatKind(X)) >= a!6220!6220isNatKind(X) mark(U23(X)) >= a!6220!6220U23(mark(X)) mark(isNat(X)) >= a!6220!6220isNat(X) mark(U31(X, Y)) >= a!6220!6220U31(mark(X), Y) mark(U32(X, Y)) >= a!6220!6220U32(mark(X), Y) mark(U33(X)) >= a!6220!6220U33(mark(X)) mark(U41(X, Y, Z)) >= a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y, Z)) >= a!6220!6220U42(mark(X), Y, Z) mark(U43(X, Y, Z)) >= a!6220!6220U43(mark(X), Y, Z) mark(U44(X, Y, Z)) >= a!6220!6220U44(mark(X), Y, Z) mark(U45(X, Y)) >= a!6220!6220U45(mark(X), Y) mark(U46(X)) >= a!6220!6220U46(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(U61(X)) >= a!6220!6220U61(mark(X)) mark(U71(X)) >= a!6220!6220U71(mark(X)) mark(U81(X, Y, Z)) >= a!6220!6220U81(mark(X), Y, Z) mark(U82(X, Y, Z)) >= a!6220!6220U82(mark(X), Y, Z) mark(U83(X, Y, Z)) >= a!6220!6220U83(mark(X), Y, Z) mark(U84(X, Y, Z)) >= a!6220!6220U84(mark(X), Y, Z) mark(U85(X, Y)) >= a!6220!6220U85(mark(X), Y) mark(U86(X)) >= a!6220!6220U86(mark(X)) mark(U91(X, Y, Z)) >= a!6220!6220U91(mark(X), Y, Z) mark(U92(X, Y, Z)) >= a!6220!6220U92(mark(X), Y, Z) mark(U93(X, Y, Z)) >= a!6220!6220U93(mark(X), Y, Z) mark(U94(X, Y)) >= a!6220!6220U94(mark(X), Y) mark(length(X)) >= a!6220!6220length(mark(X)) 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, Y) >= U11(X, Y) a!6220!6220U12(X, Y) >= U12(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220U13(X) >= U13(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X, Y) >= U22(X, Y) a!6220!6220isNatKind(X) >= isNatKind(X) a!6220!6220U23(X) >= U23(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U31(X, Y) >= U31(X, Y) a!6220!6220U32(X, Y) >= U32(X, Y) a!6220!6220U33(X) >= U33(X) a!6220!6220U41(X, Y, Z) >= U41(X, Y, Z) a!6220!6220U42(X, Y, Z) >= U42(X, Y, Z) a!6220!6220U43(X, Y, Z) >= U43(X, Y, Z) a!6220!6220U44(X, Y, Z) >= U44(X, Y, Z) a!6220!6220U45(X, Y) >= U45(X, Y) a!6220!6220U46(X) >= U46(X) a!6220!6220isNatIList(X) >= isNatIList(X) a!6220!6220U51(X, Y) >= U51(X, Y) a!6220!6220U52(X) >= U52(X) a!6220!6220U61(X) >= U61(X) a!6220!6220U71(X) >= U71(X) a!6220!6220U81(X, Y, Z) >= U81(X, Y, Z) a!6220!6220U82(X, Y, Z) >= U82(X, Y, Z) a!6220!6220U83(X, Y, Z) >= U83(X, Y, Z) a!6220!6220U84(X, Y, Z) >= U84(X, Y, Z) a!6220!6220U85(X, Y) >= U85(X, Y) a!6220!6220U86(X) >= U86(X) a!6220!6220U91(X, Y, Z) >= U91(X, Y, Z) a!6220!6220U92(X, Y, Z) >= U92(X, Y, Z) a!6220!6220U93(X, Y, Z) >= U93(X, Y, Z) a!6220!6220U94(X, Y) >= U94(X, Y) a!6220!6220length(X) >= length(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.1 U12 = \y0y1.1 U13 = \y0.1 U21 = \y0y1.1 U22 = \y0y1.1 U23 = \y0.1 U31 = \y0y1.1 U32 = \y0y1.1 U33 = \y0.1 U41 = \y0y1y2.1 U42 = \y0y1y2.1 U43 = \y0y1y2.1 U44 = \y0y1y2.1 U45 = \y0y1.1 U46 = \y0.1 U51 = \y0y1.1 U52 = \y0.1 U61 = \y0.1 U71 = \y0.1 U81 = \y0y1y2.2y2 U82 = \y0y1y2.2y2 U83 = \y0y1y2.2y2 U84 = \y0y1y2.2y2 U85 = \y0y1.2y1 U86 = \y0.y0 U91 = \y0y1y2.0 U92 = \y0y1y2.0 U93 = \y0y1y2.0 U94 = \y0y1.0 a!6220!6220U11 = \y0y1.1 a!6220!6220U12 = \y0y1.1 a!6220!6220U13 = \y0.1 a!6220!6220U21 = \y0y1.1 a!6220!6220U22 = \y0y1.1 a!6220!6220U23 = \y0.1 a!6220!6220U31 = \y0y1.1 a!6220!6220U32 = \y0y1.1 a!6220!6220U33 = \y0.1 a!6220!6220U41 = \y0y1y2.1 a!6220!6220U42 = \y0y1y2.1 a!6220!6220U43 = \y0y1y2.1 a!6220!6220U44 = \y0y1y2.1 a!6220!6220U45 = \y0y1.1 a!6220!6220U46 = \y0.1 a!6220!6220U51 = \y0y1.1 a!6220!6220U52 = \y0.1 a!6220!6220U61 = \y0.1 a!6220!6220U71 = \y0.1 a!6220!6220U81 = \y0y1y2.2y2 a!6220!6220U82 = \y0y1y2.2y2 a!6220!6220U83 = \y0y1y2.2y2 a!6220!6220U84 = \y0y1y2.2y2 a!6220!6220U85 = \y0y1.2y1 a!6220!6220U86 = \y0.y0 a!6220!6220U91 = \y0y1y2.0 a!6220!6220U91# = \y0y1y2.2y0 + 2y1 a!6220!6220U92 = \y0y1y2.0 a!6220!6220U92# = \y0y1y2.1 + 2y1 a!6220!6220U93 = \y0y1y2.0 a!6220!6220U93# = \y0y1y2.1 + 2y1 a!6220!6220U94 = \y0y1.0 a!6220!6220U94# = \y0y1.1 + 2y1 a!6220!6220isNat = \y0.1 a!6220!6220isNatIList = \y0.1 a!6220!6220isNatIListKind = \y0.1 a!6220!6220isNatKind = \y0.2 a!6220!6220isNatList = \y0.2y0 a!6220!6220length = \y0.0 a!6220!6220length# = \y0.2y0 a!6220!6220zeros = 0 cons = \y0y1.3y1 isNat = \y0.1 isNatIList = \y0.1 isNatIListKind = \y0.1 isNatKind = \y0.2 isNatList = \y0.2y0 length = \y0.0 mark = \y0.y0 nil = 1 s = \y0.0 tt = 1 zeros = 0 Using this interpretation, the requirements translate to: [[a!6220!6220U91#(tt, _x0, _x1)]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220U92#(a!6220!6220isNatIListKind(_x0), _x0, _x1)]] [[a!6220!6220U92#(tt, _x0, _x1)]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U93#(a!6220!6220isNat(_x1), _x0, _x1)]] [[a!6220!6220U93#(tt, _x0, _x1)]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U94#(a!6220!6220isNatKind(_x1), _x0)]] [[a!6220!6220U94#(tt, _x0)]] = 1 + 2x0 > 2x0 = [[a!6220!6220length#(mark(_x0))]] [[a!6220!6220length#(cons(_x0, _x1))]] = 6x1 >= 6x1 = [[a!6220!6220U91#(a!6220!6220isNatList(_x1), _x1, _x0)]] [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] [[a!6220!6220U11(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U12(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220U12(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U13(a!6220!6220isNatList(_x0))]] [[a!6220!6220U13(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U21(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U22(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220U22(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U23(a!6220!6220isNat(_x0))]] [[a!6220!6220U23(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U31(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U32(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220U32(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U33(a!6220!6220isNatList(_x0))]] [[a!6220!6220U33(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U41(tt, _x0, _x1)]] = 1 >= 1 = [[a!6220!6220U42(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220U42(tt, _x0, _x1)]] = 1 >= 1 = [[a!6220!6220U43(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U43(tt, _x0, _x1)]] = 1 >= 1 = [[a!6220!6220U44(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U44(tt, _x0, _x1)]] = 1 >= 1 = [[a!6220!6220U45(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U45(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U46(a!6220!6220isNatIList(_x0))]] [[a!6220!6220U46(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U51(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U52(a!6220!6220isNatIListKind(_x0))]] [[a!6220!6220U52(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U61(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U71(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U81(tt, _x0, _x1)]] = 2x1 >= 2x1 = [[a!6220!6220U82(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220U82(tt, _x0, _x1)]] = 2x1 >= 2x1 = [[a!6220!6220U83(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U83(tt, _x0, _x1)]] = 2x1 >= 2x1 = [[a!6220!6220U84(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U84(tt, _x0, _x1)]] = 2x1 >= 2x1 = [[a!6220!6220U85(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U85(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U86(a!6220!6220isNatList(_x0))]] [[a!6220!6220U86(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U91(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U92(a!6220!6220isNatIListKind(_x0), _x0, _x1)]] [[a!6220!6220U92(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U93(a!6220!6220isNat(_x1), _x0, _x1)]] [[a!6220!6220U93(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U94(a!6220!6220isNatKind(_x1), _x0)]] [[a!6220!6220U94(tt, _x0)]] = 0 >= 0 = [[s(a!6220!6220length(mark(_x0)))]] [[a!6220!6220isNat(0)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNat(length(_x0))]] = 1 >= 1 = [[a!6220!6220U11(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNat(s(_x0))]] = 1 >= 1 = [[a!6220!6220U21(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220isNatIList(_x0)]] = 1 >= 1 = [[a!6220!6220U31(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNatIList(zeros)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U41(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220isNatIListKind(nil)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNatIListKind(zeros)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNatIListKind(cons(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U51(a!6220!6220isNatKind(_x0), _x1)]] [[a!6220!6220isNatKind(0)]] = 2 >= 1 = [[tt]] [[a!6220!6220isNatKind(length(_x0))]] = 2 >= 1 = [[a!6220!6220U61(a!6220!6220isNatIListKind(_x0))]] [[a!6220!6220isNatKind(s(_x0))]] = 2 >= 1 = [[a!6220!6220U71(a!6220!6220isNatKind(_x0))]] [[a!6220!6220isNatList(nil)]] = 2 >= 1 = [[tt]] [[a!6220!6220isNatList(cons(_x0, _x1))]] = 6x1 >= 2x1 = [[a!6220!6220U81(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220length(nil)]] = 0 >= 0 = [[0]] [[a!6220!6220length(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U91(a!6220!6220isNatList(_x1), _x1, _x0)]] [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] [[mark(U11(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U11(mark(_x0), _x1)]] [[mark(U12(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U12(mark(_x0), _x1)]] [[mark(isNatIListKind(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIListKind(_x0)]] [[mark(U13(_x0))]] = 1 >= 1 = [[a!6220!6220U13(mark(_x0))]] [[mark(isNatList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatList(_x0)]] [[mark(U21(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U21(mark(_x0), _x1)]] [[mark(U22(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U22(mark(_x0), _x1)]] [[mark(isNatKind(_x0))]] = 2 >= 2 = [[a!6220!6220isNatKind(_x0)]] [[mark(U23(_x0))]] = 1 >= 1 = [[a!6220!6220U23(mark(_x0))]] [[mark(isNat(_x0))]] = 1 >= 1 = [[a!6220!6220isNat(_x0)]] [[mark(U31(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U31(mark(_x0), _x1)]] [[mark(U32(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U32(mark(_x0), _x1)]] [[mark(U33(_x0))]] = 1 >= 1 = [[a!6220!6220U33(mark(_x0))]] [[mark(U41(_x0, _x1, _x2))]] = 1 >= 1 = [[a!6220!6220U41(mark(_x0), _x1, _x2)]] [[mark(U42(_x0, _x1, _x2))]] = 1 >= 1 = [[a!6220!6220U42(mark(_x0), _x1, _x2)]] [[mark(U43(_x0, _x1, _x2))]] = 1 >= 1 = [[a!6220!6220U43(mark(_x0), _x1, _x2)]] [[mark(U44(_x0, _x1, _x2))]] = 1 >= 1 = [[a!6220!6220U44(mark(_x0), _x1, _x2)]] [[mark(U45(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U45(mark(_x0), _x1)]] [[mark(U46(_x0))]] = 1 >= 1 = [[a!6220!6220U46(mark(_x0))]] [[mark(isNatIList(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIList(_x0)]] [[mark(U51(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U51(mark(_x0), _x1)]] [[mark(U52(_x0))]] = 1 >= 1 = [[a!6220!6220U52(mark(_x0))]] [[mark(U61(_x0))]] = 1 >= 1 = [[a!6220!6220U61(mark(_x0))]] [[mark(U71(_x0))]] = 1 >= 1 = [[a!6220!6220U71(mark(_x0))]] [[mark(U81(_x0, _x1, _x2))]] = 2x2 >= 2x2 = [[a!6220!6220U81(mark(_x0), _x1, _x2)]] [[mark(U82(_x0, _x1, _x2))]] = 2x2 >= 2x2 = [[a!6220!6220U82(mark(_x0), _x1, _x2)]] [[mark(U83(_x0, _x1, _x2))]] = 2x2 >= 2x2 = [[a!6220!6220U83(mark(_x0), _x1, _x2)]] [[mark(U84(_x0, _x1, _x2))]] = 2x2 >= 2x2 = [[a!6220!6220U84(mark(_x0), _x1, _x2)]] [[mark(U85(_x0, _x1))]] = 2x1 >= 2x1 = [[a!6220!6220U85(mark(_x0), _x1)]] [[mark(U86(_x0))]] = x0 >= x0 = [[a!6220!6220U86(mark(_x0))]] [[mark(U91(_x0, _x1, _x2))]] = 0 >= 0 = [[a!6220!6220U91(mark(_x0), _x1, _x2)]] [[mark(U92(_x0, _x1, _x2))]] = 0 >= 0 = [[a!6220!6220U92(mark(_x0), _x1, _x2)]] [[mark(U93(_x0, _x1, _x2))]] = 0 >= 0 = [[a!6220!6220U93(mark(_x0), _x1, _x2)]] [[mark(U94(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U94(mark(_x0), _x1)]] [[mark(length(_x0))]] = 0 >= 0 = [[a!6220!6220length(mark(_x0))]] [[mark(cons(_x0, _x1))]] = 3x1 >= 3x1 = [[cons(mark(_x0), _x1)]] [[mark(0)]] = 0 >= 0 = [[0]] [[mark(tt)]] = 1 >= 1 = [[tt]] [[mark(s(_x0))]] = 0 >= 0 = [[s(mark(_x0))]] [[mark(nil)]] = 1 >= 1 = [[nil]] [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] [[a!6220!6220U11(_x0, _x1)]] = 1 >= 1 = [[U11(_x0, _x1)]] [[a!6220!6220U12(_x0, _x1)]] = 1 >= 1 = [[U12(_x0, _x1)]] [[a!6220!6220isNatIListKind(_x0)]] = 1 >= 1 = [[isNatIListKind(_x0)]] [[a!6220!6220U13(_x0)]] = 1 >= 1 = [[U13(_x0)]] [[a!6220!6220isNatList(_x0)]] = 2x0 >= 2x0 = [[isNatList(_x0)]] [[a!6220!6220U21(_x0, _x1)]] = 1 >= 1 = [[U21(_x0, _x1)]] [[a!6220!6220U22(_x0, _x1)]] = 1 >= 1 = [[U22(_x0, _x1)]] [[a!6220!6220isNatKind(_x0)]] = 2 >= 2 = [[isNatKind(_x0)]] [[a!6220!6220U23(_x0)]] = 1 >= 1 = [[U23(_x0)]] [[a!6220!6220isNat(_x0)]] = 1 >= 1 = [[isNat(_x0)]] [[a!6220!6220U31(_x0, _x1)]] = 1 >= 1 = [[U31(_x0, _x1)]] [[a!6220!6220U32(_x0, _x1)]] = 1 >= 1 = [[U32(_x0, _x1)]] [[a!6220!6220U33(_x0)]] = 1 >= 1 = [[U33(_x0)]] [[a!6220!6220U41(_x0, _x1, _x2)]] = 1 >= 1 = [[U41(_x0, _x1, _x2)]] [[a!6220!6220U42(_x0, _x1, _x2)]] = 1 >= 1 = [[U42(_x0, _x1, _x2)]] [[a!6220!6220U43(_x0, _x1, _x2)]] = 1 >= 1 = [[U43(_x0, _x1, _x2)]] [[a!6220!6220U44(_x0, _x1, _x2)]] = 1 >= 1 = [[U44(_x0, _x1, _x2)]] [[a!6220!6220U45(_x0, _x1)]] = 1 >= 1 = [[U45(_x0, _x1)]] [[a!6220!6220U46(_x0)]] = 1 >= 1 = [[U46(_x0)]] [[a!6220!6220isNatIList(_x0)]] = 1 >= 1 = [[isNatIList(_x0)]] [[a!6220!6220U51(_x0, _x1)]] = 1 >= 1 = [[U51(_x0, _x1)]] [[a!6220!6220U52(_x0)]] = 1 >= 1 = [[U52(_x0)]] [[a!6220!6220U61(_x0)]] = 1 >= 1 = [[U61(_x0)]] [[a!6220!6220U71(_x0)]] = 1 >= 1 = [[U71(_x0)]] [[a!6220!6220U81(_x0, _x1, _x2)]] = 2x2 >= 2x2 = [[U81(_x0, _x1, _x2)]] [[a!6220!6220U82(_x0, _x1, _x2)]] = 2x2 >= 2x2 = [[U82(_x0, _x1, _x2)]] [[a!6220!6220U83(_x0, _x1, _x2)]] = 2x2 >= 2x2 = [[U83(_x0, _x1, _x2)]] [[a!6220!6220U84(_x0, _x1, _x2)]] = 2x2 >= 2x2 = [[U84(_x0, _x1, _x2)]] [[a!6220!6220U85(_x0, _x1)]] = 2x1 >= 2x1 = [[U85(_x0, _x1)]] [[a!6220!6220U86(_x0)]] = x0 >= x0 = [[U86(_x0)]] [[a!6220!6220U91(_x0, _x1, _x2)]] = 0 >= 0 = [[U91(_x0, _x1, _x2)]] [[a!6220!6220U92(_x0, _x1, _x2)]] = 0 >= 0 = [[U92(_x0, _x1, _x2)]] [[a!6220!6220U93(_x0, _x1, _x2)]] = 0 >= 0 = [[U93(_x0, _x1, _x2)]] [[a!6220!6220U94(_x0, _x1)]] = 0 >= 0 = [[U94(_x0, _x1)]] [[a!6220!6220length(_x0)]] = 0 >= 0 = [[length(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_6, R_0, minimal, formative) by (P_8, R_0, minimal, formative), where P_8 consists of: a!6220!6220U92#(tt, X, Y) =#> a!6220!6220U93#(a!6220!6220isNat(Y), X, Y) a!6220!6220U93#(tt, X, Y) =#> a!6220!6220U94#(a!6220!6220isNatKind(Y), X) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U91#(a!6220!6220isNatList(Y), Y, X) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, 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 : * 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), (P_2, 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 apply the subterm criterion with the following projection function: nu(a!6220!6220U51#) = 2 nu(a!6220!6220isNatIListKind#) = 1 nu(a!6220!6220isNatKind#) = 1 Thus, we can orient the dependency pairs as follows: nu(a!6220!6220U51#(tt, X)) = X = X = nu(a!6220!6220isNatIListKind#(X)) nu(a!6220!6220isNatIListKind#(cons(X, Y))) = cons(X, Y) |> Y = nu(a!6220!6220U51#(a!6220!6220isNatKind(X), Y)) nu(a!6220!6220isNatIListKind#(cons(X, Y))) = cons(X, Y) |> X = nu(a!6220!6220isNatKind#(X)) nu(a!6220!6220isNatKind#(length(X))) = length(X) |> X = nu(a!6220!6220isNatIListKind#(X)) nu(a!6220!6220isNatKind#(s(X))) = s(X) |> X = nu(a!6220!6220isNatKind#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by (P_9, R_0, minimal, f), where P_9 contains: a!6220!6220U51#(tt, X) =#> a!6220!6220isNatIListKind#(X) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (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 : 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_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(a!6220!6220U41#) = 3 nu(a!6220!6220U42#) = 3 nu(a!6220!6220U43#) = 3 nu(a!6220!6220U44#) = 3 nu(a!6220!6220U45#) = 2 nu(a!6220!6220isNatIList#) = 1 Thus, we can orient the dependency pairs as follows: nu(a!6220!6220U41#(tt, X, Y)) = Y = Y = nu(a!6220!6220U42#(a!6220!6220isNatKind(X), X, Y)) nu(a!6220!6220U42#(tt, X, Y)) = Y = Y = nu(a!6220!6220U43#(a!6220!6220isNatIListKind(Y), X, Y)) nu(a!6220!6220U43#(tt, X, Y)) = Y = Y = nu(a!6220!6220U44#(a!6220!6220isNatIListKind(Y), X, Y)) nu(a!6220!6220U44#(tt, X, Y)) = Y = Y = nu(a!6220!6220U45#(a!6220!6220isNat(X), Y)) nu(a!6220!6220U45#(tt, X)) = X = X = nu(a!6220!6220isNatIList#(X)) nu(a!6220!6220isNatIList#(cons(X, Y))) = cons(X, Y) |> Y = nu(a!6220!6220U41#(a!6220!6220isNatKind(X), X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by (P_10, R_0, minimal, f), where P_10 contains: a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U42#(tt, X, Y) =#> a!6220!6220U43#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U43#(tt, X, Y) =#> a!6220!6220U44#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U44#(tt, X, Y) =#> a!6220!6220U45#(a!6220!6220isNat(X), Y) a!6220!6220U45#(tt, X) =#> a!6220!6220isNatIList#(X) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_10, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_10, 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 : 3 * 3 : 4 * 4 : 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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_1, R_0) are: a!6220!6220U11(tt, X) => a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) => a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) => tt a!6220!6220U21(tt, X) => a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) => a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) => tt a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) => tt a!6220!6220U61(tt) => tt a!6220!6220U71(tt) => tt a!6220!6220U81(tt, X, Y) => a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) => a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) => a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) => a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) => a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) => tt a!6220!6220isNat(0) => tt a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIListKind(nil) => tt a!6220!6220isNatIListKind(zeros) => tt a!6220!6220isNatIListKind(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) => tt a!6220!6220isNatKind(length(X)) => a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) => a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) => tt a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220U11(X, Y) => U11(X, Y) a!6220!6220U12(X, Y) => U12(X, Y) a!6220!6220isNatIListKind(X) => isNatIListKind(X) a!6220!6220U13(X) => U13(X) a!6220!6220isNatList(X) => isNatList(X) a!6220!6220U21(X, Y) => U21(X, Y) a!6220!6220U22(X, Y) => U22(X, Y) a!6220!6220isNatKind(X) => isNatKind(X) a!6220!6220U23(X) => U23(X) a!6220!6220isNat(X) => isNat(X) a!6220!6220U51(X, Y) => U51(X, Y) a!6220!6220U52(X) => U52(X) a!6220!6220U61(X) => U61(X) a!6220!6220U71(X) => U71(X) a!6220!6220U81(X, Y, Z) => U81(X, Y, Z) a!6220!6220U82(X, Y, Z) => U82(X, Y, Z) a!6220!6220U83(X, Y, Z) => U83(X, Y, Z) a!6220!6220U84(X, Y, Z) => U84(X, Y, Z) a!6220!6220U85(X, Y) => U85(X, Y) a!6220!6220U86(X) => U86(X) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220U11#(tt, X) >? a!6220!6220U12#(a!6220!6220isNatIListKind(X), X) a!6220!6220U12#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) >? a!6220!6220U22#(a!6220!6220isNatKind(X), X) a!6220!6220U22#(tt, X) >? a!6220!6220isNat#(X) a!6220!6220U81#(tt, X, Y) >? a!6220!6220U82#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82#(tt, X, Y) >? a!6220!6220U83#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83#(tt, X, Y) >? a!6220!6220U84#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84#(tt, X, Y) >? a!6220!6220U85#(a!6220!6220isNat(X), Y) a!6220!6220U84#(tt, X, Y) >? a!6220!6220isNat#(X) a!6220!6220U85#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220isNat#(length(X)) >? a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(s(X)) >? a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220U81#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U11(tt, X) >= a!6220!6220U12(a!6220!6220isNatIListKind(X), X) a!6220!6220U12(tt, X) >= a!6220!6220U13(a!6220!6220isNatList(X)) a!6220!6220U13(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNatKind(X), X) a!6220!6220U22(tt, X) >= a!6220!6220U23(a!6220!6220isNat(X)) a!6220!6220U23(tt) >= tt a!6220!6220U51(tt, X) >= a!6220!6220U52(a!6220!6220isNatIListKind(X)) a!6220!6220U52(tt) >= tt a!6220!6220U61(tt) >= tt a!6220!6220U71(tt) >= tt a!6220!6220U81(tt, X, Y) >= a!6220!6220U82(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82(tt, X, Y) >= a!6220!6220U83(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83(tt, X, Y) >= a!6220!6220U84(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84(tt, X, Y) >= a!6220!6220U85(a!6220!6220isNat(X), Y) a!6220!6220U85(tt, X) >= a!6220!6220U86(a!6220!6220isNatList(X)) a!6220!6220U86(tt) >= tt a!6220!6220isNat(0) >= tt a!6220!6220isNat(length(X)) >= a!6220!6220U11(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat(s(X)) >= a!6220!6220U21(a!6220!6220isNatKind(X), X) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220U51(a!6220!6220isNatKind(X), Y) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220U61(a!6220!6220isNatIListKind(X)) a!6220!6220isNatKind(s(X)) >= a!6220!6220U71(a!6220!6220isNatKind(X)) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U81(a!6220!6220isNatKind(X), X, Y) a!6220!6220U11(X, Y) >= U11(X, Y) a!6220!6220U12(X, Y) >= U12(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220U13(X) >= U13(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X, Y) >= U22(X, Y) a!6220!6220isNatKind(X) >= isNatKind(X) a!6220!6220U23(X) >= U23(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U51(X, Y) >= U51(X, Y) a!6220!6220U52(X) >= U52(X) a!6220!6220U61(X) >= U61(X) a!6220!6220U71(X) >= U71(X) a!6220!6220U81(X, Y, Z) >= U81(X, Y, Z) a!6220!6220U82(X, Y, Z) >= U82(X, Y, Z) a!6220!6220U83(X, Y, Z) >= U83(X, Y, Z) a!6220!6220U84(X, Y, Z) >= U84(X, Y, Z) a!6220!6220U85(X, Y) >= U85(X, Y) a!6220!6220U86(X) >= U86(X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: a!6220!6220U11#(x_1,x_2) = a!6220!6220U11#(x_2) a!6220!6220U12#(x_1,x_2) = a!6220!6220U12#(x_2) a!6220!6220U21#(x_1,x_2) = a!6220!6220U21#(x_2) a!6220!6220U22#(x_1,x_2) = a!6220!6220U22#(x_2) a!6220!6220U81#(x_1,x_2,x_3) = a!6220!6220U81#(x_2x_3) a!6220!6220U82#(x_1,x_2,x_3) = a!6220!6220U82#(x_2x_3) a!6220!6220U83#(x_1,x_2,x_3) = a!6220!6220U83#(x_2x_3) a!6220!6220U84#(x_1,x_2,x_3) = a!6220!6220U84#(x_2x_3) a!6220!6220U85#(x_1,x_2) = a!6220!6220U85#(x_2) This leaves the following ordering requirements: a!6220!6220U11#(tt, X) >= a!6220!6220U12#(a!6220!6220isNatIListKind(X), X) a!6220!6220U12#(tt, X) >= a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) >= a!6220!6220U22#(a!6220!6220isNatKind(X), X) a!6220!6220U22#(tt, X) > a!6220!6220isNat#(X) a!6220!6220U81#(tt, X, Y) >= a!6220!6220U82#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82#(tt, X, Y) >= a!6220!6220U83#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83#(tt, X, Y) >= a!6220!6220U84#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84#(tt, X, Y) >= a!6220!6220U85#(a!6220!6220isNat(X), Y) a!6220!6220U84#(tt, X, Y) >= a!6220!6220isNat#(X) a!6220!6220U85#(tt, X) >= a!6220!6220isNatList#(X) a!6220!6220isNat#(length(X)) >= a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(s(X)) >= a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNatList#(cons(X, Y)) >= a!6220!6220U81#(a!6220!6220isNatKind(X), X, Y) The following interpretation satisfies the requirements: 0 = 3 U11 = \y0y1.0 U12 = \y0y1.0 U13 = \y0.0 U21 = \y0y1.0 U22 = \y0y1.0 U23 = \y0.0 U51 = \y0y1.0 U52 = \y0.0 U61 = \y0.0 U71 = \y0.0 U81 = \y0y1y2.0 U82 = \y0y1y2.0 U83 = \y0y1y2.0 U84 = \y0y1y2.0 U85 = \y0y1.0 U86 = \y0.0 a!6220!6220U11 = \y0y1.0 a!6220!6220U11# = \y0y1.2y1 a!6220!6220U12 = \y0y1.0 a!6220!6220U12# = \y0y1.2y1 a!6220!6220U13 = \y0.0 a!6220!6220U21 = \y0y1.0 a!6220!6220U21# = \y0y1.1 + 3y1 a!6220!6220U22 = \y0y1.0 a!6220!6220U22# = \y0y1.1 + 3y1 a!6220!6220U23 = \y0.0 a!6220!6220U51 = \y0y1.0 a!6220!6220U52 = \y0.0 a!6220!6220U61 = \y0.0 a!6220!6220U71 = \y0.0 a!6220!6220U81 = \y0y1y2.0 a!6220!6220U81# = \y0y1y2.2y2 + 3y1 a!6220!6220U82 = \y0y1y2.0 a!6220!6220U82# = \y0y1y2.2y2 + 3y1 a!6220!6220U83 = \y0y1y2.0 a!6220!6220U83# = \y0y1y2.2y2 + 3y1 a!6220!6220U84 = \y0y1y2.0 a!6220!6220U84# = \y0y1y2.2y2 + 3y1 a!6220!6220U85 = \y0y1.0 a!6220!6220U85# = \y0y1.2y1 a!6220!6220U86 = \y0.0 a!6220!6220isNat = \y0.0 a!6220!6220isNatIListKind = \y0.0 a!6220!6220isNatKind = \y0.0 a!6220!6220isNatList = \y0.0 a!6220!6220isNatList# = \y0.2y0 a!6220!6220isNat# = \y0.3y0 cons = \y0y1.3 + y1 + 2y0 isNat = \y0.0 isNatIListKind = \y0.0 isNatKind = \y0.0 isNatList = \y0.0 length = \y0.3 + y0 nil = 3 s = \y0.3 + 2y0 tt = 0 zeros = 3 Using this interpretation, the requirements translate to: [[a!6220!6220U11#(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U12#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220U12#(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U21#(tt, _x0)]] = 1 + 3x0 >= 1 + 3x0 = [[a!6220!6220U22#(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220U22#(tt, _x0)]] = 1 + 3x0 > 3x0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U81#(tt, _x0, _x1)]] = 2x1 + 3x0 >= 2x1 + 3x0 = [[a!6220!6220U82#(a!6220!6220isNatKind(_x0), _x0, _x1)]] [[a!6220!6220U82#(tt, _x0, _x1)]] = 2x1 + 3x0 >= 2x1 + 3x0 = [[a!6220!6220U83#(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U83#(tt, _x0, _x1)]] = 2x1 + 3x0 >= 2x1 + 3x0 = [[a!6220!6220U84#(a!6220!6220isNatIListKind(_x1), _x0, _x1)]] [[a!6220!6220U84#(tt, _x0, _x1)]] = 2x1 + 3x0 >= 2x1 = [[a!6220!6220U85#(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U84#(tt, _x0, _x1)]] = 2x1 + 3x0 >= 3x0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U85#(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220isNat#(length(_x0))]] = 9 + 3x0 > 2x0 = [[a!6220!6220U11#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNat#(s(_x0))]] = 9 + 6x0 > 1 + 3x0 = [[a!6220!6220U21#(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 6 + 2x1 + 4x0 > 2x1 + 3x0 = [[a!6220!6220U81#(a!6220!6220isNatKind(_x0), _x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_11, R_0, minimal, formative), where P_11 consists of: a!6220!6220U11#(tt, X) =#> a!6220!6220U12#(a!6220!6220isNatIListKind(X), X) a!6220!6220U12#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) =#> a!6220!6220U22#(a!6220!6220isNatKind(X), X) a!6220!6220U81#(tt, X, Y) =#> a!6220!6220U82#(a!6220!6220isNatKind(X), X, Y) a!6220!6220U82#(tt, X, Y) =#> a!6220!6220U83#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U83#(tt, X, Y) =#> a!6220!6220U84#(a!6220!6220isNatIListKind(Y), X, Y) a!6220!6220U84#(tt, X, Y) =#> a!6220!6220U85#(a!6220!6220isNat(X), Y) a!6220!6220U84#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U85#(tt, X) =#> a!6220!6220isNatList#(X) Thus, the original system is terminating if (P_11, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_11, 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 : * 3 : 4 * 4 : 5 * 5 : 6, 7 * 6 : 8 * 7 : * 8 : 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.