/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 U21 : [o * o] --> o U22 : [o] --> o U31 : [o * o] --> o U32 : [o] --> o U41 : [o * o * o] --> o U42 : [o * o] --> o U43 : [o] --> o U51 : [o * o * o] --> o U52 : [o * o] --> o U53 : [o] --> o U61 : [o * o] --> o a!6220!6220U11 : [o * o] --> o a!6220!6220U12 : [o] --> o a!6220!6220U21 : [o * o] --> o a!6220!6220U22 : [o] --> o a!6220!6220U31 : [o * o] --> o a!6220!6220U32 : [o] --> o a!6220!6220U41 : [o * o * o] --> o a!6220!6220U42 : [o * o] --> o a!6220!6220U43 : [o] --> o a!6220!6220U51 : [o * o * o] --> o a!6220!6220U52 : [o * o] --> o a!6220!6220U53 : [o] --> o a!6220!6220U61 : [o * o] --> o a!6220!6220and : [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 and : [o * o] --> 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!6220isNatList(X)) a!6220!6220U12(tt) => tt a!6220!6220U21(tt, X) => a!6220!6220U22(a!6220!6220isNat(X)) a!6220!6220U22(tt) => tt a!6220!6220U31(tt, X) => a!6220!6220U32(a!6220!6220isNatList(X)) a!6220!6220U32(tt) => tt a!6220!6220U41(tt, X, Y) => a!6220!6220U42(a!6220!6220isNat(X), Y) a!6220!6220U42(tt, X) => a!6220!6220U43(a!6220!6220isNatIList(X)) a!6220!6220U43(tt) => tt a!6220!6220U51(tt, X, Y) => a!6220!6220U52(a!6220!6220isNat(X), Y) a!6220!6220U52(tt, X) => a!6220!6220U53(a!6220!6220isNatList(X)) a!6220!6220U53(tt) => tt a!6220!6220U61(tt, X) => s(a!6220!6220length(mark(X))) a!6220!6220and(tt, X) => 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!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIListKind(nil) => tt a!6220!6220isNatIListKind(zeros) => tt a!6220!6220isNatIListKind(cons(X, Y)) => a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatKind(0) => tt a!6220!6220isNatKind(length(X)) => a!6220!6220isNatIListKind(X) a!6220!6220isNatKind(s(X)) => a!6220!6220isNatKind(X) a!6220!6220isNatList(nil) => tt a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220length(nil) => 0 a!6220!6220length(cons(X, Y)) => a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark(zeros) => a!6220!6220zeros mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) mark(U12(X)) => a!6220!6220U12(mark(X)) mark(isNatList(X)) => a!6220!6220isNatList(X) mark(U21(X, Y)) => a!6220!6220U21(mark(X), Y) mark(U22(X)) => a!6220!6220U22(mark(X)) mark(isNat(X)) => a!6220!6220isNat(X) mark(U31(X, Y)) => a!6220!6220U31(mark(X), Y) mark(U32(X)) => a!6220!6220U32(mark(X)) mark(U41(X, Y, Z)) => a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y)) => a!6220!6220U42(mark(X), Y) mark(U43(X)) => a!6220!6220U43(mark(X)) mark(isNatIList(X)) => a!6220!6220isNatIList(X) mark(U51(X, Y, Z)) => a!6220!6220U51(mark(X), Y, Z) mark(U52(X, Y)) => a!6220!6220U52(mark(X), Y) mark(U53(X)) => a!6220!6220U53(mark(X)) mark(U61(X, Y)) => a!6220!6220U61(mark(X), Y) mark(length(X)) => a!6220!6220length(mark(X)) mark(and(X, Y)) => a!6220!6220and(mark(X), Y) mark(isNatIListKind(X)) => a!6220!6220isNatIListKind(X) mark(isNatKind(X)) => a!6220!6220isNatKind(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) => U12(X) a!6220!6220isNatList(X) => isNatList(X) a!6220!6220U21(X, Y) => U21(X, Y) a!6220!6220U22(X) => U22(X) a!6220!6220isNat(X) => isNat(X) a!6220!6220U31(X, Y) => U31(X, Y) a!6220!6220U32(X) => U32(X) a!6220!6220U41(X, Y, Z) => U41(X, Y, Z) a!6220!6220U42(X, Y) => U42(X, Y) a!6220!6220U43(X) => U43(X) a!6220!6220isNatIList(X) => isNatIList(X) a!6220!6220U51(X, Y, Z) => U51(X, Y, Z) a!6220!6220U52(X, Y) => U52(X, Y) a!6220!6220U53(X) => U53(X) a!6220!6220U61(X, Y) => U61(X, Y) a!6220!6220length(X) => length(X) a!6220!6220and(X, Y) => and(X, Y) a!6220!6220isNatIListKind(X) => isNatIListKind(X) a!6220!6220isNatKind(X) => isNatKind(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!6220isNatList(X)) 1] a!6220!6220U11#(tt, X) =#> a!6220!6220isNatList#(X) 2] a!6220!6220U21#(tt, X) =#> a!6220!6220U22#(a!6220!6220isNat(X)) 3] a!6220!6220U21#(tt, X) =#> a!6220!6220isNat#(X) 4] a!6220!6220U31#(tt, X) =#> a!6220!6220U32#(a!6220!6220isNatList(X)) 5] a!6220!6220U31#(tt, X) =#> a!6220!6220isNatList#(X) 6] a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNat(X), Y) 7] a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNat#(X) 8] a!6220!6220U42#(tt, X) =#> a!6220!6220U43#(a!6220!6220isNatIList(X)) 9] a!6220!6220U42#(tt, X) =#> a!6220!6220isNatIList#(X) 10] a!6220!6220U51#(tt, X, Y) =#> a!6220!6220U52#(a!6220!6220isNat(X), Y) 11] a!6220!6220U51#(tt, X, Y) =#> a!6220!6220isNat#(X) 12] a!6220!6220U52#(tt, X) =#> a!6220!6220U53#(a!6220!6220isNatList(X)) 13] a!6220!6220U52#(tt, X) =#> a!6220!6220isNatList#(X) 14] a!6220!6220U61#(tt, X) =#> a!6220!6220length#(mark(X)) 15] a!6220!6220U61#(tt, X) =#> mark#(X) 16] a!6220!6220and#(tt, X) =#> mark#(X) 17] a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) 18] a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatIListKind#(X) 19] a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) 20] a!6220!6220isNat#(s(X)) =#> a!6220!6220isNatKind#(X) 21] a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) 22] a!6220!6220isNatIList#(X) =#> a!6220!6220isNatIListKind#(X) 23] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) 24] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) 25] a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 26] a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) 27] a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 28] a!6220!6220isNatKind#(length(X)) =#> a!6220!6220isNatIListKind#(X) 29] a!6220!6220isNatKind#(s(X)) =#> a!6220!6220isNatKind#(X) 30] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) 31] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) 32] a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) 33] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) 34] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))) 35] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatList(Y), isNatIListKind(Y)) 36] a!6220!6220length#(cons(X, Y)) =#> a!6220!6220isNatList#(Y) 37] mark#(zeros) =#> a!6220!6220zeros# 38] mark#(U11(X, Y)) =#> a!6220!6220U11#(mark(X), Y) 39] mark#(U11(X, Y)) =#> mark#(X) 40] mark#(U12(X)) =#> a!6220!6220U12#(mark(X)) 41] mark#(U12(X)) =#> mark#(X) 42] mark#(isNatList(X)) =#> a!6220!6220isNatList#(X) 43] mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) 44] mark#(U21(X, Y)) =#> mark#(X) 45] mark#(U22(X)) =#> a!6220!6220U22#(mark(X)) 46] mark#(U22(X)) =#> mark#(X) 47] mark#(isNat(X)) =#> a!6220!6220isNat#(X) 48] mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) 49] mark#(U31(X, Y)) =#> mark#(X) 50] mark#(U32(X)) =#> a!6220!6220U32#(mark(X)) 51] mark#(U32(X)) =#> mark#(X) 52] mark#(U41(X, Y, Z)) =#> a!6220!6220U41#(mark(X), Y, Z) 53] mark#(U41(X, Y, Z)) =#> mark#(X) 54] mark#(U42(X, Y)) =#> a!6220!6220U42#(mark(X), Y) 55] mark#(U42(X, Y)) =#> mark#(X) 56] mark#(U43(X)) =#> a!6220!6220U43#(mark(X)) 57] mark#(U43(X)) =#> mark#(X) 58] mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) 59] mark#(U51(X, Y, Z)) =#> a!6220!6220U51#(mark(X), Y, Z) 60] mark#(U51(X, Y, Z)) =#> mark#(X) 61] mark#(U52(X, Y)) =#> a!6220!6220U52#(mark(X), Y) 62] mark#(U52(X, Y)) =#> mark#(X) 63] mark#(U53(X)) =#> a!6220!6220U53#(mark(X)) 64] mark#(U53(X)) =#> mark#(X) 65] mark#(U61(X, Y)) =#> a!6220!6220U61#(mark(X), Y) 66] mark#(U61(X, Y)) =#> mark#(X) 67] mark#(length(X)) =#> a!6220!6220length#(mark(X)) 68] mark#(length(X)) =#> mark#(X) 69] mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) 70] mark#(and(X, Y)) =#> mark#(X) 71] mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) 72] mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(X) 73] mark#(cons(X, Y)) =#> mark#(X) 74] mark#(s(X)) =#> mark#(X) Rules R_0: a!6220!6220zeros => cons(0, zeros) a!6220!6220U11(tt, X) => a!6220!6220U12(a!6220!6220isNatList(X)) a!6220!6220U12(tt) => tt a!6220!6220U21(tt, X) => a!6220!6220U22(a!6220!6220isNat(X)) a!6220!6220U22(tt) => tt a!6220!6220U31(tt, X) => a!6220!6220U32(a!6220!6220isNatList(X)) a!6220!6220U32(tt) => tt a!6220!6220U41(tt, X, Y) => a!6220!6220U42(a!6220!6220isNat(X), Y) a!6220!6220U42(tt, X) => a!6220!6220U43(a!6220!6220isNatIList(X)) a!6220!6220U43(tt) => tt a!6220!6220U51(tt, X, Y) => a!6220!6220U52(a!6220!6220isNat(X), Y) a!6220!6220U52(tt, X) => a!6220!6220U53(a!6220!6220isNatList(X)) a!6220!6220U53(tt) => tt a!6220!6220U61(tt, X) => s(a!6220!6220length(mark(X))) a!6220!6220and(tt, X) => 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!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIListKind(nil) => tt a!6220!6220isNatIListKind(zeros) => tt a!6220!6220isNatIListKind(cons(X, Y)) => a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatKind(0) => tt a!6220!6220isNatKind(length(X)) => a!6220!6220isNatIListKind(X) a!6220!6220isNatKind(s(X)) => a!6220!6220isNatKind(X) a!6220!6220isNatList(nil) => tt a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220length(nil) => 0 a!6220!6220length(cons(X, Y)) => a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark(zeros) => a!6220!6220zeros mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) mark(U12(X)) => a!6220!6220U12(mark(X)) mark(isNatList(X)) => a!6220!6220isNatList(X) mark(U21(X, Y)) => a!6220!6220U21(mark(X), Y) mark(U22(X)) => a!6220!6220U22(mark(X)) mark(isNat(X)) => a!6220!6220isNat(X) mark(U31(X, Y)) => a!6220!6220U31(mark(X), Y) mark(U32(X)) => a!6220!6220U32(mark(X)) mark(U41(X, Y, Z)) => a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y)) => a!6220!6220U42(mark(X), Y) mark(U43(X)) => a!6220!6220U43(mark(X)) mark(isNatIList(X)) => a!6220!6220isNatIList(X) mark(U51(X, Y, Z)) => a!6220!6220U51(mark(X), Y, Z) mark(U52(X, Y)) => a!6220!6220U52(mark(X), Y) mark(U53(X)) => a!6220!6220U53(mark(X)) mark(U61(X, Y)) => a!6220!6220U61(mark(X), Y) mark(length(X)) => a!6220!6220length(mark(X)) mark(and(X, Y)) => a!6220!6220and(mark(X), Y) mark(isNatIListKind(X)) => a!6220!6220isNatIListKind(X) mark(isNatKind(X)) => a!6220!6220isNatKind(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) => U12(X) a!6220!6220isNatList(X) => isNatList(X) a!6220!6220U21(X, Y) => U21(X, Y) a!6220!6220U22(X) => U22(X) a!6220!6220isNat(X) => isNat(X) a!6220!6220U31(X, Y) => U31(X, Y) a!6220!6220U32(X) => U32(X) a!6220!6220U41(X, Y, Z) => U41(X, Y, Z) a!6220!6220U42(X, Y) => U42(X, Y) a!6220!6220U43(X) => U43(X) a!6220!6220isNatIList(X) => isNatIList(X) a!6220!6220U51(X, Y, Z) => U51(X, Y, Z) a!6220!6220U52(X, Y) => U52(X, Y) a!6220!6220U53(X) => U53(X) a!6220!6220U61(X, Y) => U61(X, Y) a!6220!6220length(X) => length(X) a!6220!6220and(X, Y) => and(X, Y) a!6220!6220isNatIListKind(X) => isNatIListKind(X) a!6220!6220isNatKind(X) => isNatKind(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 : * 1 : 30, 31, 32 * 2 : * 3 : 17, 18, 19, 20 * 4 : * 5 : 30, 31, 32 * 6 : 8, 9 * 7 : 17, 18, 19, 20 * 8 : * 9 : 21, 22, 23, 24, 25 * 10 : 12, 13 * 11 : 17, 18, 19, 20 * 12 : * 13 : 30, 31, 32 * 14 : 33, 34, 35, 36 * 15 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 16 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 17 : 0, 1 * 18 : 26, 27 * 19 : 2, 3 * 20 : 28, 29 * 21 : 4, 5 * 22 : 26, 27 * 23 : 6, 7 * 24 : 16 * 25 : 28, 29 * 26 : 16 * 27 : 28, 29 * 28 : 26, 27 * 29 : 28, 29 * 30 : 10, 11 * 31 : 16 * 32 : 28, 29 * 33 : 14, 15 * 34 : 16 * 35 : 16 * 36 : 30, 31, 32 * 37 : * 38 : 0, 1 * 39 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 40 : * 41 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 42 : 30, 31, 32 * 43 : 2, 3 * 44 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 45 : * 46 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 47 : 17, 18, 19, 20 * 48 : 4, 5 * 49 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 50 : * 51 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 52 : 6, 7 * 53 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 54 : 8, 9 * 55 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 56 : * 57 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 58 : 21, 22, 23, 24, 25 * 59 : 10, 11 * 60 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 61 : 12, 13 * 62 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 63 : * 64 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 65 : 14, 15 * 66 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 67 : 33, 34, 35, 36 * 68 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 69 : 16 * 70 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 71 : 26, 27 * 72 : 28, 29 * 73 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 * 74 : 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 This graph has the following strongly connected components: P_1: a!6220!6220U11#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) =#> a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) =#> a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U61#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220U61#(tt, X) =#> mark#(X) a!6220!6220and#(tt, X) =#> mark#(X) a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatList(Y), isNatIListKind(Y)) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220isNatList#(Y) mark#(U11(X, Y)) =#> a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNatList(X)) =#> a!6220!6220isNatList#(X) mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X)) =#> mark#(X) mark#(isNat(X)) =#> a!6220!6220isNat#(X) mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y)) =#> a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) =#> mark#(X) mark#(U43(X)) =#> mark#(X) mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) =#> a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) =#> mark#(X) mark#(U52(X, Y)) =#> a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) =#> mark#(X) mark#(U53(X)) =#> mark#(X) mark#(U61(X, Y)) =#> a!6220!6220U61#(mark(X), Y) mark#(U61(X, Y)) =#> mark#(X) mark#(length(X)) =#> a!6220!6220length#(mark(X)) mark#(length(X)) =#> mark#(X) mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) =#> mark#(X) mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(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). 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 [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220U11#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) >? a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) >? a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) >? a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) >? a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) >? a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) >? a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U61#(tt, X) >? a!6220!6220length#(mark(X)) a!6220!6220U61#(tt, X) >? mark#(X) a!6220!6220and#(tt, X) >? mark#(X) a!6220!6220isNat#(length(X)) >? a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) >? a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) >? a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) >? a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) >? a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) >? a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220isNatKind#(X) a!6220!6220length#(cons(X, Y)) >? a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) a!6220!6220length#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))) a!6220!6220length#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatList(Y), isNatIListKind(Y)) a!6220!6220length#(cons(X, Y)) >? a!6220!6220isNatList#(Y) mark#(U11(X, Y)) >? a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNatList(X)) >? a!6220!6220isNatList#(X) mark#(U21(X, Y)) >? a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) >? mark#(X) mark#(U22(X)) >? mark#(X) mark#(isNat(X)) >? a!6220!6220isNat#(X) mark#(U31(X, Y)) >? a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) >? mark#(X) mark#(U32(X)) >? mark#(X) mark#(U41(X, Y, Z)) >? a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) >? mark#(X) mark#(U42(X, Y)) >? a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) >? mark#(X) mark#(U43(X)) >? mark#(X) mark#(isNatIList(X)) >? a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) >? a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) >? mark#(X) mark#(U52(X, Y)) >? a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) >? mark#(X) mark#(U53(X)) >? mark#(X) mark#(U61(X, Y)) >? a!6220!6220U61#(mark(X), Y) mark#(U61(X, Y)) >? mark#(X) mark#(length(X)) >? a!6220!6220length#(mark(X)) mark#(length(X)) >? mark#(X) mark#(and(X, Y)) >? a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) >? mark#(X) mark#(isNatIListKind(X)) >? a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) >? a!6220!6220isNatKind#(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!6220isNatList(X)) a!6220!6220U12(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNat(X)) a!6220!6220U22(tt) >= tt a!6220!6220U31(tt, X) >= a!6220!6220U32(a!6220!6220isNatList(X)) a!6220!6220U32(tt) >= tt a!6220!6220U41(tt, X, Y) >= a!6220!6220U42(a!6220!6220isNat(X), Y) a!6220!6220U42(tt, X) >= a!6220!6220U43(a!6220!6220isNatIList(X)) a!6220!6220U43(tt) >= tt a!6220!6220U51(tt, X, Y) >= a!6220!6220U52(a!6220!6220isNat(X), Y) a!6220!6220U52(tt, X) >= a!6220!6220U53(a!6220!6220isNatList(X)) a!6220!6220U53(tt) >= tt a!6220!6220U61(tt, X) >= s(a!6220!6220length(mark(X))) a!6220!6220and(tt, X) >= 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!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220isNatIListKind(X) a!6220!6220isNatKind(s(X)) >= a!6220!6220isNatKind(X) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220length(nil) >= 0 a!6220!6220length(cons(X, Y)) >= a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark(zeros) >= a!6220!6220zeros mark(U11(X, Y)) >= a!6220!6220U11(mark(X), Y) mark(U12(X)) >= a!6220!6220U12(mark(X)) mark(isNatList(X)) >= a!6220!6220isNatList(X) mark(U21(X, Y)) >= a!6220!6220U21(mark(X), Y) mark(U22(X)) >= a!6220!6220U22(mark(X)) mark(isNat(X)) >= a!6220!6220isNat(X) mark(U31(X, Y)) >= a!6220!6220U31(mark(X), Y) mark(U32(X)) >= a!6220!6220U32(mark(X)) mark(U41(X, Y, Z)) >= a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y)) >= a!6220!6220U42(mark(X), Y) mark(U43(X)) >= a!6220!6220U43(mark(X)) mark(isNatIList(X)) >= a!6220!6220isNatIList(X) mark(U51(X, Y, Z)) >= a!6220!6220U51(mark(X), Y, Z) mark(U52(X, Y)) >= a!6220!6220U52(mark(X), Y) mark(U53(X)) >= a!6220!6220U53(mark(X)) mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) mark(length(X)) >= a!6220!6220length(mark(X)) mark(and(X, Y)) >= a!6220!6220and(mark(X), Y) mark(isNatIListKind(X)) >= a!6220!6220isNatIListKind(X) mark(isNatKind(X)) >= a!6220!6220isNatKind(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) >= U12(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X) >= U22(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U31(X, Y) >= U31(X, Y) a!6220!6220U32(X) >= U32(X) a!6220!6220U41(X, Y, Z) >= U41(X, Y, Z) a!6220!6220U42(X, Y) >= U42(X, Y) a!6220!6220U43(X) >= U43(X) a!6220!6220isNatIList(X) >= isNatIList(X) a!6220!6220U51(X, Y, Z) >= U51(X, Y, Z) a!6220!6220U52(X, Y) >= U52(X, Y) a!6220!6220U53(X) >= U53(X) a!6220!6220U61(X, Y) >= U61(X, Y) a!6220!6220length(X) >= length(X) a!6220!6220and(X, Y) >= and(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220isNatKind(X) >= isNatKind(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.2y0 U12 = \y0.y0 U21 = \y0y1.2y0 U22 = \y0.2y0 U31 = \y0y1.y0 U32 = \y0.y0 U41 = \y0y1y2.2y0 U42 = \y0y1.y0 U43 = \y0.2y0 U51 = \y0y1y2.y0 U52 = \y0y1.2y0 U53 = \y0.y0 U61 = \y0y1.2 + 2y0 + 2y1 a!6220!6220U11 = \y0y1.2y0 a!6220!6220U11# = \y0y1.0 a!6220!6220U12 = \y0.y0 a!6220!6220U21 = \y0y1.2y0 a!6220!6220U21# = \y0y1.0 a!6220!6220U22 = \y0.2y0 a!6220!6220U31 = \y0y1.y0 a!6220!6220U31# = \y0y1.0 a!6220!6220U32 = \y0.y0 a!6220!6220U41 = \y0y1y2.2y0 a!6220!6220U41# = \y0y1y2.0 a!6220!6220U42 = \y0y1.y0 a!6220!6220U42# = \y0y1.0 a!6220!6220U43 = \y0.2y0 a!6220!6220U51 = \y0y1y2.y0 a!6220!6220U51# = \y0y1y2.0 a!6220!6220U52 = \y0y1.2y0 a!6220!6220U52# = \y0y1.0 a!6220!6220U53 = \y0.y0 a!6220!6220U61 = \y0y1.2 + 2y0 + 2y1 a!6220!6220U61# = \y0y1.1 + 2y1 a!6220!6220and = \y0y1.y0 + 2y1 a!6220!6220and# = \y0y1.2y1 a!6220!6220isNat = \y0.0 a!6220!6220isNatIList = \y0.0 a!6220!6220isNatIListKind = \y0.0 a!6220!6220isNatIListKind# = \y0.0 a!6220!6220isNatIList# = \y0.0 a!6220!6220isNatKind = \y0.0 a!6220!6220isNatKind# = \y0.0 a!6220!6220isNatList = \y0.0 a!6220!6220isNatList# = \y0.0 a!6220!6220isNat# = \y0.0 a!6220!6220length = \y0.2 + y0 a!6220!6220length# = \y0.1 + y0 a!6220!6220zeros = 0 and = \y0y1.y0 + y1 cons = \y0y1.y0 + 2y1 isNat = \y0.0 isNatIList = \y0.0 isNatIListKind = \y0.0 isNatKind = \y0.0 isNatList = \y0.0 length = \y0.2 + 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!6220U11#(tt, _x0)]] = 0 >= 0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U21#(tt, _x0)]] = 0 >= 0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U31#(tt, _x0)]] = 0 >= 0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U41#(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U42#(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U41#(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U42#(tt, _x0)]] = 0 >= 0 = [[a!6220!6220isNatIList#(_x0)]] [[a!6220!6220U51#(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U52#(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U51#(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U52#(tt, _x0)]] = 0 >= 0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U61#(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220length#(mark(_x0))]] [[a!6220!6220U61#(tt, _x0)]] = 1 + 2x0 > 2x0 = [[mark#(_x0)]] [[a!6220!6220and#(tt, _x0)]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[a!6220!6220isNat#(length(_x0))]] = 0 >= 0 = [[a!6220!6220U11#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNat#(length(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNat#(s(_x0))]] = 0 >= 0 = [[a!6220!6220U21#(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220isNat#(s(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatIList#(_x0)]] = 0 >= 0 = [[a!6220!6220U31#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNatIList#(_x0)]] = 0 >= 0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatIListKind#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatIListKind#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatKind#(length(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNatKind#(s(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220length#(cons(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + 2x1 = [[a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(_x1), isNatIListKind(_x1)), and(isNat(_x0), isNatKind(_x0))), _x1)]] [[a!6220!6220length#(cons(_x0, _x1))]] = 1 + x0 + 2x1 > 0 = [[a!6220!6220and#(a!6220!6220and(a!6220!6220isNatList(_x1), isNatIListKind(_x1)), and(isNat(_x0), isNatKind(_x0)))]] [[a!6220!6220length#(cons(_x0, _x1))]] = 1 + x0 + 2x1 > 0 = [[a!6220!6220and#(a!6220!6220isNatList(_x1), isNatIListKind(_x1))]] [[a!6220!6220length#(cons(_x0, _x1))]] = 1 + x0 + 2x1 > 0 = [[a!6220!6220isNatList#(_x1)]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 0 = [[a!6220!6220U11#(mark(_x0), _x1)]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(isNatList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatList#(_x0)]] [[mark#(U21(_x0, _x1))]] = 4x0 >= 0 = [[a!6220!6220U21#(mark(_x0), _x1)]] [[mark#(U21(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U22(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 0 >= 0 = [[a!6220!6220isNat#(_x0)]] [[mark#(U31(_x0, _x1))]] = 2x0 >= 0 = [[a!6220!6220U31#(mark(_x0), _x1)]] [[mark#(U31(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U32(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U41(_x0, _x1, _x2))]] = 4x0 >= 0 = [[a!6220!6220U41#(mark(_x0), _x1, _x2)]] [[mark#(U41(_x0, _x1, _x2))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U42(_x0, _x1))]] = 2x0 >= 0 = [[a!6220!6220U42#(mark(_x0), _x1)]] [[mark#(U42(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U43(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(isNatIList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIList#(_x0)]] [[mark#(U51(_x0, _x1, _x2))]] = 2x0 >= 0 = [[a!6220!6220U51#(mark(_x0), _x1, _x2)]] [[mark#(U51(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U52(_x0, _x1))]] = 4x0 >= 0 = [[a!6220!6220U52#(mark(_x0), _x1)]] [[mark#(U52(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U53(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U61(_x0, _x1))]] = 4 + 4x0 + 4x1 > 1 + 2x1 = [[a!6220!6220U61#(mark(_x0), _x1)]] [[mark#(U61(_x0, _x1))]] = 4 + 4x0 + 4x1 > 2x0 = [[mark#(_x0)]] [[mark#(length(_x0))]] = 4 + 2x0 > 1 + 2x0 = [[a!6220!6220length#(mark(_x0))]] [[mark#(length(_x0))]] = 4 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[a!6220!6220and#(mark(_x0), _x1)]] [[mark#(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(isNatIListKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind#(_x0)]] [[mark#(isNatKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind#(_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!6220isNatList(_x0))]] [[a!6220!6220U12(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U21(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U22(a!6220!6220isNat(_x0))]] [[a!6220!6220U22(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U31(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U32(a!6220!6220isNatList(_x0))]] [[a!6220!6220U32(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U41(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U42(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U42(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U43(a!6220!6220isNatIList(_x0))]] [[a!6220!6220U43(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U51(tt, _x0, _x1)]] = 0 >= 0 = [[a!6220!6220U52(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U52(tt, _x0)]] = 0 >= 0 = [[a!6220!6220U53(a!6220!6220isNatList(_x0))]] [[a!6220!6220U53(tt)]] = 0 >= 0 = [[tt]] [[a!6220!6220U61(tt, _x0)]] = 2 + 2x0 >= 2 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] [[a!6220!6220and(tt, _x0)]] = 2x0 >= 2x0 = [[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!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _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!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatKind(0)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatKind(length(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind(_x0)]] [[a!6220!6220isNatKind(s(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind(_x0)]] [[a!6220!6220isNatList(nil)]] = 0 >= 0 = [[tt]] [[a!6220!6220isNatList(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220length(nil)]] = 2 >= 0 = [[0]] [[a!6220!6220length(cons(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + 2x1 = [[a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(_x1), isNatIListKind(_x1)), and(isNat(_x0), isNatKind(_x0))), _x1)]] [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] [[mark(U11(_x0, _x1))]] = 4x0 >= 4x0 = [[a!6220!6220U11(mark(_x0), _x1)]] [[mark(U12(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U12(mark(_x0))]] [[mark(isNatList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatList(_x0)]] [[mark(U21(_x0, _x1))]] = 4x0 >= 4x0 = [[a!6220!6220U21(mark(_x0), _x1)]] [[mark(U22(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U22(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))]] = 2x0 >= 2x0 = [[a!6220!6220U32(mark(_x0))]] [[mark(U41(_x0, _x1, _x2))]] = 4x0 >= 4x0 = [[a!6220!6220U41(mark(_x0), _x1, _x2)]] [[mark(U42(_x0, _x1))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0), _x1)]] [[mark(U43(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U43(mark(_x0))]] [[mark(isNatIList(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIList(_x0)]] [[mark(U51(_x0, _x1, _x2))]] = 2x0 >= 2x0 = [[a!6220!6220U51(mark(_x0), _x1, _x2)]] [[mark(U52(_x0, _x1))]] = 4x0 >= 4x0 = [[a!6220!6220U52(mark(_x0), _x1)]] [[mark(U53(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U53(mark(_x0))]] [[mark(U61(_x0, _x1))]] = 4 + 4x0 + 4x1 >= 2 + 2x1 + 4x0 = [[a!6220!6220U61(mark(_x0), _x1)]] [[mark(length(_x0))]] = 4 + 2x0 >= 2 + 2x0 = [[a!6220!6220length(mark(_x0))]] [[mark(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] [[mark(isNatIListKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatIListKind(_x0)]] [[mark(isNatKind(_x0))]] = 0 >= 0 = [[a!6220!6220isNatKind(_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)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[a!6220!6220U12(_x0)]] = x0 >= x0 = [[U12(_x0)]] [[a!6220!6220isNatList(_x0)]] = 0 >= 0 = [[isNatList(_x0)]] [[a!6220!6220U21(_x0, _x1)]] = 2x0 >= 2x0 = [[U21(_x0, _x1)]] [[a!6220!6220U22(_x0)]] = 2x0 >= 2x0 = [[U22(_x0)]] [[a!6220!6220isNat(_x0)]] = 0 >= 0 = [[isNat(_x0)]] [[a!6220!6220U31(_x0, _x1)]] = x0 >= x0 = [[U31(_x0, _x1)]] [[a!6220!6220U32(_x0)]] = x0 >= x0 = [[U32(_x0)]] [[a!6220!6220U41(_x0, _x1, _x2)]] = 2x0 >= 2x0 = [[U41(_x0, _x1, _x2)]] [[a!6220!6220U42(_x0, _x1)]] = x0 >= x0 = [[U42(_x0, _x1)]] [[a!6220!6220U43(_x0)]] = 2x0 >= 2x0 = [[U43(_x0)]] [[a!6220!6220isNatIList(_x0)]] = 0 >= 0 = [[isNatIList(_x0)]] [[a!6220!6220U51(_x0, _x1, _x2)]] = x0 >= x0 = [[U51(_x0, _x1, _x2)]] [[a!6220!6220U52(_x0, _x1)]] = 2x0 >= 2x0 = [[U52(_x0, _x1)]] [[a!6220!6220U53(_x0)]] = x0 >= x0 = [[U53(_x0)]] [[a!6220!6220U61(_x0, _x1)]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[U61(_x0, _x1)]] [[a!6220!6220length(_x0)]] = 2 + x0 >= 2 + x0 = [[length(_x0)]] [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] [[a!6220!6220isNatIListKind(_x0)]] = 0 >= 0 = [[isNatIListKind(_x0)]] [[a!6220!6220isNatKind(_x0)]] = 0 >= 0 = [[isNatKind(_x0)]] 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_2, R_0, minimal, formative), where P_2 consists of: a!6220!6220U11#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) =#> a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) =#> a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U61#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220and#(tt, X) =#> mark#(X) a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark#(U11(X, Y)) =#> a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNatList(X)) =#> a!6220!6220isNatList#(X) mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X)) =#> mark#(X) mark#(isNat(X)) =#> a!6220!6220isNat#(X) mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y)) =#> a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) =#> mark#(X) mark#(U43(X)) =#> mark#(X) mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) =#> a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) =#> mark#(X) mark#(U52(X, Y)) =#> a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) =#> mark#(X) mark#(U53(X)) =#> mark#(X) mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) =#> mark#(X) mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(s(X)) =#> mark#(X) Thus, the original system is terminating if (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, 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 : 24, 25, 26 * 1 : 11, 12, 13, 14 * 2 : 24, 25, 26 * 3 : 5 * 4 : 11, 12, 13, 14 * 5 : 15, 16, 17, 18, 19 * 6 : 8 * 7 : 11, 12, 13, 14 * 8 : 24, 25, 26 * 9 : 27 * 10 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 11 : 0 * 12 : 20, 21 * 13 : 1 * 14 : 22, 23 * 15 : 2 * 16 : 20, 21 * 17 : 3, 4 * 18 : 10 * 19 : 22, 23 * 20 : 10 * 21 : 22, 23 * 22 : 20, 21 * 23 : 22, 23 * 24 : 6, 7 * 25 : 10 * 26 : 22, 23 * 27 : 9 * 28 : 0 * 29 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 30 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 31 : 24, 25, 26 * 32 : 1 * 33 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 34 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 35 : 11, 12, 13, 14 * 36 : 2 * 37 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 38 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 39 : 3, 4 * 40 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 41 : 5 * 42 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 43 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 44 : 15, 16, 17, 18, 19 * 45 : 6, 7 * 46 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 47 : 8 * 48 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 49 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 50 : 10 * 51 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 52 : 20, 21 * 53 : 22, 23 * 54 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 * 55 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 This graph has the following strongly connected components: P_3: a!6220!6220U11#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) =#> a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) =#> a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220and#(tt, X) =#> mark#(X) a!6220!6220isNat#(length(X)) =#> a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) =#> a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) =#> a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) =#> a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) =#> a!6220!6220isNatKind#(X) mark#(U11(X, Y)) =#> a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNatList(X)) =#> a!6220!6220isNatList#(X) mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) =#> mark#(X) mark#(U22(X)) =#> mark#(X) mark#(isNat(X)) =#> a!6220!6220isNat#(X) mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) =#> mark#(X) mark#(U32(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y)) =#> a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) =#> mark#(X) mark#(U43(X)) =#> mark#(X) mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) =#> a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) =#> mark#(X) mark#(U52(X, Y)) =#> a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) =#> mark#(X) mark#(U53(X)) =#> mark#(X) mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) =#> mark#(X) mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(s(X)) =#> mark#(X) P_4: a!6220!6220U61#(tt, X) =#> a!6220!6220length#(mark(X)) a!6220!6220length#(cons(X, Y)) =#> a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_2, R_0, m, f) by (P_3, R_0, m, f) and (P_4, R_0, m, f). Thus, the original system is terminating if each of (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!6220U61#(tt, X) >? a!6220!6220length#(mark(X)) a!6220!6220length#(cons(X, Y)) >? a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) a!6220!6220zeros >= cons(0, zeros) a!6220!6220U11(tt, X) >= a!6220!6220U12(a!6220!6220isNatList(X)) a!6220!6220U12(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNat(X)) a!6220!6220U22(tt) >= tt a!6220!6220U31(tt, X) >= a!6220!6220U32(a!6220!6220isNatList(X)) a!6220!6220U32(tt) >= tt a!6220!6220U41(tt, X, Y) >= a!6220!6220U42(a!6220!6220isNat(X), Y) a!6220!6220U42(tt, X) >= a!6220!6220U43(a!6220!6220isNatIList(X)) a!6220!6220U43(tt) >= tt a!6220!6220U51(tt, X, Y) >= a!6220!6220U52(a!6220!6220isNat(X), Y) a!6220!6220U52(tt, X) >= a!6220!6220U53(a!6220!6220isNatList(X)) a!6220!6220U53(tt) >= tt a!6220!6220U61(tt, X) >= s(a!6220!6220length(mark(X))) a!6220!6220and(tt, X) >= 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!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220isNatIListKind(X) a!6220!6220isNatKind(s(X)) >= a!6220!6220isNatKind(X) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220length(nil) >= 0 a!6220!6220length(cons(X, Y)) >= a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark(zeros) >= a!6220!6220zeros mark(U11(X, Y)) >= a!6220!6220U11(mark(X), Y) mark(U12(X)) >= a!6220!6220U12(mark(X)) mark(isNatList(X)) >= a!6220!6220isNatList(X) mark(U21(X, Y)) >= a!6220!6220U21(mark(X), Y) mark(U22(X)) >= a!6220!6220U22(mark(X)) mark(isNat(X)) >= a!6220!6220isNat(X) mark(U31(X, Y)) >= a!6220!6220U31(mark(X), Y) mark(U32(X)) >= a!6220!6220U32(mark(X)) mark(U41(X, Y, Z)) >= a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y)) >= a!6220!6220U42(mark(X), Y) mark(U43(X)) >= a!6220!6220U43(mark(X)) mark(isNatIList(X)) >= a!6220!6220isNatIList(X) mark(U51(X, Y, Z)) >= a!6220!6220U51(mark(X), Y, Z) mark(U52(X, Y)) >= a!6220!6220U52(mark(X), Y) mark(U53(X)) >= a!6220!6220U53(mark(X)) mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) mark(length(X)) >= a!6220!6220length(mark(X)) mark(and(X, Y)) >= a!6220!6220and(mark(X), Y) mark(isNatIListKind(X)) >= a!6220!6220isNatIListKind(X) mark(isNatKind(X)) >= a!6220!6220isNatKind(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) >= U12(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X) >= U22(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U31(X, Y) >= U31(X, Y) a!6220!6220U32(X) >= U32(X) a!6220!6220U41(X, Y, Z) >= U41(X, Y, Z) a!6220!6220U42(X, Y) >= U42(X, Y) a!6220!6220U43(X) >= U43(X) a!6220!6220isNatIList(X) >= isNatIList(X) a!6220!6220U51(X, Y, Z) >= U51(X, Y, Z) a!6220!6220U52(X, Y) >= U52(X, Y) a!6220!6220U53(X) >= U53(X) a!6220!6220U61(X, Y) >= U61(X, Y) a!6220!6220length(X) >= length(X) a!6220!6220and(X, Y) >= and(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220isNatKind(X) >= isNatKind(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 = \y0.0 U21 = \y0y1.0 U22 = \y0.1 U31 = \y0y1.1 U32 = \y0.0 U41 = \y0y1y2.1 U42 = \y0y1.0 U43 = \y0.y0 U51 = \y0y1y2.y2 U52 = \y0y1.2y1 U53 = \y0.y0 U61 = \y0y1.0 a!6220!6220U11 = \y0y1.1 a!6220!6220U12 = \y0.1 a!6220!6220U21 = \y0y1.1 a!6220!6220U22 = \y0.1 a!6220!6220U31 = \y0y1.1 a!6220!6220U32 = \y0.1 a!6220!6220U41 = \y0y1y2.1 a!6220!6220U42 = \y0y1.1 a!6220!6220U43 = \y0.y0 a!6220!6220U51 = \y0y1y2.2y2 a!6220!6220U52 = \y0y1.2y1 a!6220!6220U53 = \y0.y0 a!6220!6220U61 = \y0y1.0 a!6220!6220U61# = \y0y1.y0 + 2y1 a!6220!6220and = \y0y1.y0 + 2y1 a!6220!6220isNat = \y0.1 a!6220!6220isNatIList = \y0.1 a!6220!6220isNatIListKind = \y0.1 a!6220!6220isNatKind = \y0.1 a!6220!6220isNatList = \y0.y0 a!6220!6220length = \y0.0 a!6220!6220length# = \y0.y0 a!6220!6220zeros = 1 and = \y0y1.y0 + 2y1 cons = \y0y1.1 + 3y1 isNat = \y0.0 isNatIList = \y0.0 isNatIListKind = \y0.0 isNatKind = \y0.0 isNatList = \y0.y0 length = \y0.0 mark = \y0.1 + 2y0 nil = 1 s = \y0.0 tt = 1 zeros = 0 Using this interpretation, the requirements translate to: [[a!6220!6220U61#(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220length#(mark(_x0))]] [[a!6220!6220length#(cons(_x0, _x1))]] = 1 + 3x1 > 3x1 = [[a!6220!6220U61#(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(_x1), isNatIListKind(_x1)), and(isNat(_x0), isNatKind(_x0))), _x1)]] [[a!6220!6220zeros]] = 1 >= 1 = [[cons(0, zeros)]] [[a!6220!6220U11(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U12(a!6220!6220isNatList(_x0))]] [[a!6220!6220U12(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U21(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U22(a!6220!6220isNat(_x0))]] [[a!6220!6220U22(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U31(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U32(a!6220!6220isNatList(_x0))]] [[a!6220!6220U32(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U41(tt, _x0, _x1)]] = 1 >= 1 = [[a!6220!6220U42(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U42(tt, _x0)]] = 1 >= 1 = [[a!6220!6220U43(a!6220!6220isNatIList(_x0))]] [[a!6220!6220U43(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U51(tt, _x0, _x1)]] = 2x1 >= 2x1 = [[a!6220!6220U52(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U52(tt, _x0)]] = 2x0 >= x0 = [[a!6220!6220U53(a!6220!6220isNatList(_x0))]] [[a!6220!6220U53(tt)]] = 1 >= 1 = [[tt]] [[a!6220!6220U61(tt, _x0)]] = 0 >= 0 = [[s(a!6220!6220length(mark(_x0)))]] [[a!6220!6220and(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[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!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _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!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatKind(0)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNatKind(length(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIListKind(_x0)]] [[a!6220!6220isNatKind(s(_x0))]] = 1 >= 1 = [[a!6220!6220isNatKind(_x0)]] [[a!6220!6220isNatList(nil)]] = 1 >= 1 = [[tt]] [[a!6220!6220isNatList(cons(_x0, _x1))]] = 1 + 3x1 >= 2x1 = [[a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220length(nil)]] = 0 >= 0 = [[0]] [[a!6220!6220length(cons(_x0, _x1))]] = 0 >= 0 = [[a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(_x1), isNatIListKind(_x1)), and(isNat(_x0), isNatKind(_x0))), _x1)]] [[mark(zeros)]] = 1 >= 1 = [[a!6220!6220zeros]] [[mark(U11(_x0, _x1))]] = 3 >= 1 = [[a!6220!6220U11(mark(_x0), _x1)]] [[mark(U12(_x0))]] = 1 >= 1 = [[a!6220!6220U12(mark(_x0))]] [[mark(isNatList(_x0))]] = 1 + 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] [[mark(U21(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U21(mark(_x0), _x1)]] [[mark(U22(_x0))]] = 3 >= 1 = [[a!6220!6220U22(mark(_x0))]] [[mark(isNat(_x0))]] = 1 >= 1 = [[a!6220!6220isNat(_x0)]] [[mark(U31(_x0, _x1))]] = 3 >= 1 = [[a!6220!6220U31(mark(_x0), _x1)]] [[mark(U32(_x0))]] = 1 >= 1 = [[a!6220!6220U32(mark(_x0))]] [[mark(U41(_x0, _x1, _x2))]] = 3 >= 1 = [[a!6220!6220U41(mark(_x0), _x1, _x2)]] [[mark(U42(_x0, _x1))]] = 1 >= 1 = [[a!6220!6220U42(mark(_x0), _x1)]] [[mark(U43(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U43(mark(_x0))]] [[mark(isNatIList(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIList(_x0)]] [[mark(U51(_x0, _x1, _x2))]] = 1 + 2x2 >= 2x2 = [[a!6220!6220U51(mark(_x0), _x1, _x2)]] [[mark(U52(_x0, _x1))]] = 1 + 4x1 >= 2x1 = [[a!6220!6220U52(mark(_x0), _x1)]] [[mark(U53(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U53(mark(_x0))]] [[mark(U61(_x0, _x1))]] = 1 >= 0 = [[a!6220!6220U61(mark(_x0), _x1)]] [[mark(length(_x0))]] = 1 >= 0 = [[a!6220!6220length(mark(_x0))]] [[mark(and(_x0, _x1))]] = 1 + 2x0 + 4x1 >= 1 + 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] [[mark(isNatIListKind(_x0))]] = 1 >= 1 = [[a!6220!6220isNatIListKind(_x0)]] [[mark(isNatKind(_x0))]] = 1 >= 1 = [[a!6220!6220isNatKind(_x0)]] [[mark(cons(_x0, _x1))]] = 3 + 6x1 >= 1 + 3x1 = [[cons(mark(_x0), _x1)]] [[mark(0)]] = 1 >= 0 = [[0]] [[mark(tt)]] = 3 >= 1 = [[tt]] [[mark(s(_x0))]] = 1 >= 0 = [[s(mark(_x0))]] [[mark(nil)]] = 3 >= 1 = [[nil]] [[a!6220!6220zeros]] = 1 >= 0 = [[zeros]] [[a!6220!6220U11(_x0, _x1)]] = 1 >= 1 = [[U11(_x0, _x1)]] [[a!6220!6220U12(_x0)]] = 1 >= 0 = [[U12(_x0)]] [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] [[a!6220!6220U21(_x0, _x1)]] = 1 >= 0 = [[U21(_x0, _x1)]] [[a!6220!6220U22(_x0)]] = 1 >= 1 = [[U22(_x0)]] [[a!6220!6220isNat(_x0)]] = 1 >= 0 = [[isNat(_x0)]] [[a!6220!6220U31(_x0, _x1)]] = 1 >= 1 = [[U31(_x0, _x1)]] [[a!6220!6220U32(_x0)]] = 1 >= 0 = [[U32(_x0)]] [[a!6220!6220U41(_x0, _x1, _x2)]] = 1 >= 1 = [[U41(_x0, _x1, _x2)]] [[a!6220!6220U42(_x0, _x1)]] = 1 >= 0 = [[U42(_x0, _x1)]] [[a!6220!6220U43(_x0)]] = x0 >= x0 = [[U43(_x0)]] [[a!6220!6220isNatIList(_x0)]] = 1 >= 0 = [[isNatIList(_x0)]] [[a!6220!6220U51(_x0, _x1, _x2)]] = 2x2 >= x2 = [[U51(_x0, _x1, _x2)]] [[a!6220!6220U52(_x0, _x1)]] = 2x1 >= 2x1 = [[U52(_x0, _x1)]] [[a!6220!6220U53(_x0)]] = x0 >= x0 = [[U53(_x0)]] [[a!6220!6220U61(_x0, _x1)]] = 0 >= 0 = [[U61(_x0, _x1)]] [[a!6220!6220length(_x0)]] = 0 >= 0 = [[length(_x0)]] [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[a!6220!6220isNatIListKind(_x0)]] = 1 >= 0 = [[isNatIListKind(_x0)]] [[a!6220!6220isNatKind(_x0)]] = 1 >= 0 = [[isNatKind(_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!6220U61#(tt, X) =#> a!6220!6220length#(mark(X)) Thus, the original system is terminating if each of (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 : 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_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, 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!6220U11#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) >? a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) >? a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) >? a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) >? a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) >? a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) >? a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) >? a!6220!6220isNatList#(X) a!6220!6220and#(tt, X) >? mark#(X) a!6220!6220isNat#(length(X)) >? a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) >? a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) >? a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) >? a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) >? a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) >? a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) >? a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) >? a!6220!6220isNatKind#(X) mark#(U11(X, Y)) >? a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNatList(X)) >? a!6220!6220isNatList#(X) mark#(U21(X, Y)) >? a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) >? mark#(X) mark#(U22(X)) >? mark#(X) mark#(isNat(X)) >? a!6220!6220isNat#(X) mark#(U31(X, Y)) >? a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) >? mark#(X) mark#(U32(X)) >? mark#(X) mark#(U41(X, Y, Z)) >? a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) >? mark#(X) mark#(U42(X, Y)) >? a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) >? mark#(X) mark#(U43(X)) >? mark#(X) mark#(isNatIList(X)) >? a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) >? a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) >? mark#(X) mark#(U52(X, Y)) >? a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) >? mark#(X) mark#(U53(X)) >? mark#(X) mark#(and(X, Y)) >? a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) >? mark#(X) mark#(isNatIListKind(X)) >? a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) >? a!6220!6220isNatKind#(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!6220isNatList(X)) a!6220!6220U12(tt) >= tt a!6220!6220U21(tt, X) >= a!6220!6220U22(a!6220!6220isNat(X)) a!6220!6220U22(tt) >= tt a!6220!6220U31(tt, X) >= a!6220!6220U32(a!6220!6220isNatList(X)) a!6220!6220U32(tt) >= tt a!6220!6220U41(tt, X, Y) >= a!6220!6220U42(a!6220!6220isNat(X), Y) a!6220!6220U42(tt, X) >= a!6220!6220U43(a!6220!6220isNatIList(X)) a!6220!6220U43(tt) >= tt a!6220!6220U51(tt, X, Y) >= a!6220!6220U52(a!6220!6220isNat(X), Y) a!6220!6220U52(tt, X) >= a!6220!6220U53(a!6220!6220isNatList(X)) a!6220!6220U53(tt) >= tt a!6220!6220U61(tt, X) >= s(a!6220!6220length(mark(X))) a!6220!6220and(tt, X) >= 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!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIListKind(nil) >= tt a!6220!6220isNatIListKind(zeros) >= tt a!6220!6220isNatIListKind(cons(X, Y)) >= a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatKind(0) >= tt a!6220!6220isNatKind(length(X)) >= a!6220!6220isNatIListKind(X) a!6220!6220isNatKind(s(X)) >= a!6220!6220isNatKind(X) a!6220!6220isNatList(nil) >= tt a!6220!6220isNatList(cons(X, Y)) >= a!6220!6220U51(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220length(nil) >= 0 a!6220!6220length(cons(X, Y)) >= a!6220!6220U61(a!6220!6220and(a!6220!6220and(a!6220!6220isNatList(Y), isNatIListKind(Y)), and(isNat(X), isNatKind(X))), Y) mark(zeros) >= a!6220!6220zeros mark(U11(X, Y)) >= a!6220!6220U11(mark(X), Y) mark(U12(X)) >= a!6220!6220U12(mark(X)) mark(isNatList(X)) >= a!6220!6220isNatList(X) mark(U21(X, Y)) >= a!6220!6220U21(mark(X), Y) mark(U22(X)) >= a!6220!6220U22(mark(X)) mark(isNat(X)) >= a!6220!6220isNat(X) mark(U31(X, Y)) >= a!6220!6220U31(mark(X), Y) mark(U32(X)) >= a!6220!6220U32(mark(X)) mark(U41(X, Y, Z)) >= a!6220!6220U41(mark(X), Y, Z) mark(U42(X, Y)) >= a!6220!6220U42(mark(X), Y) mark(U43(X)) >= a!6220!6220U43(mark(X)) mark(isNatIList(X)) >= a!6220!6220isNatIList(X) mark(U51(X, Y, Z)) >= a!6220!6220U51(mark(X), Y, Z) mark(U52(X, Y)) >= a!6220!6220U52(mark(X), Y) mark(U53(X)) >= a!6220!6220U53(mark(X)) mark(U61(X, Y)) >= a!6220!6220U61(mark(X), Y) mark(length(X)) >= a!6220!6220length(mark(X)) mark(and(X, Y)) >= a!6220!6220and(mark(X), Y) mark(isNatIListKind(X)) >= a!6220!6220isNatIListKind(X) mark(isNatKind(X)) >= a!6220!6220isNatKind(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) >= U12(X) a!6220!6220isNatList(X) >= isNatList(X) a!6220!6220U21(X, Y) >= U21(X, Y) a!6220!6220U22(X) >= U22(X) a!6220!6220isNat(X) >= isNat(X) a!6220!6220U31(X, Y) >= U31(X, Y) a!6220!6220U32(X) >= U32(X) a!6220!6220U41(X, Y, Z) >= U41(X, Y, Z) a!6220!6220U42(X, Y) >= U42(X, Y) a!6220!6220U43(X) >= U43(X) a!6220!6220isNatIList(X) >= isNatIList(X) a!6220!6220U51(X, Y, Z) >= U51(X, Y, Z) a!6220!6220U52(X, Y) >= U52(X, Y) a!6220!6220U53(X) >= U53(X) a!6220!6220U61(X, Y) >= U61(X, Y) a!6220!6220length(X) >= length(X) a!6220!6220and(X, Y) >= and(X, Y) a!6220!6220isNatIListKind(X) >= isNatIListKind(X) a!6220!6220isNatKind(X) >= isNatKind(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!6220U21#(x_1,x_2) = a!6220!6220U21#(x_2) a!6220!6220U31#(x_1,x_2) = a!6220!6220U31#(x_2) a!6220!6220U41#(x_1,x_2,x_3) = a!6220!6220U41#(x_2x_3) a!6220!6220U42#(x_1,x_2) = a!6220!6220U42#(x_2) a!6220!6220U51#(x_1,x_2,x_3) = a!6220!6220U51#(x_2x_3) a!6220!6220U52#(x_1,x_2) = a!6220!6220U52#(x_2) a!6220!6220and#(x_1,x_2) = a!6220!6220and#(x_2) This leaves the following ordering requirements: a!6220!6220U11#(tt, X) >= a!6220!6220isNatList#(X) a!6220!6220U21#(tt, X) >= a!6220!6220isNat#(X) a!6220!6220U31#(tt, X) >= a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) >= a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) >= a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) >= a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) >= a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) >= a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) >= a!6220!6220isNatList#(X) a!6220!6220and#(tt, X) >= mark#(X) a!6220!6220isNat#(length(X)) >= a!6220!6220U11#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNat#(length(X)) >= a!6220!6220isNatIListKind#(X) a!6220!6220isNat#(s(X)) >= a!6220!6220U21#(a!6220!6220isNatKind(X), X) a!6220!6220isNat#(s(X)) >= a!6220!6220isNatKind#(X) a!6220!6220isNatIList#(X) >= a!6220!6220U31#(a!6220!6220isNatIListKind(X), X) a!6220!6220isNatIList#(X) >= a!6220!6220isNatIListKind#(X) a!6220!6220isNatIList#(cons(X, Y)) >= a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatIList#(cons(X, Y)) >= a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatIList#(cons(X, Y)) >= a!6220!6220isNatKind#(X) a!6220!6220isNatIListKind#(cons(X, Y)) >= a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(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) a!6220!6220isNatList#(cons(X, Y)) >= a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(X), isNatIListKind(Y)), X, Y) a!6220!6220isNatList#(cons(X, Y)) >= a!6220!6220and#(a!6220!6220isNatKind(X), isNatIListKind(Y)) a!6220!6220isNatList#(cons(X, Y)) >= a!6220!6220isNatKind#(X) mark#(U11(X, Y)) >= a!6220!6220U11#(mark(X), Y) mark#(U11(X, Y)) >= mark#(X) mark#(U12(X)) >= mark#(X) mark#(isNatList(X)) >= a!6220!6220isNatList#(X) mark#(U21(X, Y)) >= a!6220!6220U21#(mark(X), Y) mark#(U21(X, Y)) >= mark#(X) mark#(U22(X)) >= mark#(X) mark#(isNat(X)) >= a!6220!6220isNat#(X) mark#(U31(X, Y)) >= a!6220!6220U31#(mark(X), Y) mark#(U31(X, Y)) >= mark#(X) mark#(U32(X)) >= mark#(X) mark#(U41(X, Y, Z)) >= a!6220!6220U41#(mark(X), Y, Z) mark#(U41(X, Y, Z)) >= mark#(X) mark#(U42(X, Y)) >= a!6220!6220U42#(mark(X), Y) mark#(U42(X, Y)) >= mark#(X) mark#(U43(X)) >= mark#(X) mark#(isNatIList(X)) >= a!6220!6220isNatIList#(X) mark#(U51(X, Y, Z)) >= a!6220!6220U51#(mark(X), Y, Z) mark#(U51(X, Y, Z)) >= mark#(X) mark#(U52(X, Y)) >= a!6220!6220U52#(mark(X), Y) mark#(U52(X, Y)) >= mark#(X) mark#(U53(X)) >= mark#(X) mark#(and(X, Y)) >= a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) >= mark#(X) mark#(isNatIListKind(X)) >= a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) >= a!6220!6220isNatKind#(X) mark#(cons(X, Y)) >= mark#(X) mark#(s(X)) >= mark#(X) The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.2 + y0 + 2y1 U12 = \y0.y0 U21 = \y0y1.2 + y1 + 2y0 U22 = \y0.y0 U31 = \y0y1.1 + y0 + y1 U32 = \y0.y0 U41 = \y0y1y2.2 + y0 + y1 + y2 U42 = \y0y1.1 + y0 + y1 U43 = \y0.y0 U51 = \y0y1y2.2 + y0 + y1 + y2 U52 = \y0y1.1 + y0 + 2y1 U53 = \y0.y0 U61 = \y0y1.0 a!6220!6220U11 = \y0y1.0 a!6220!6220U11# = \y0y1.1 + 2y1 a!6220!6220U12 = \y0.0 a!6220!6220U21 = \y0y1.0 a!6220!6220U21# = \y0y1.2 + y1 a!6220!6220U22 = \y0.0 a!6220!6220U31 = \y0y1.0 a!6220!6220U31# = \y0y1.1 + y1 a!6220!6220U32 = \y0.0 a!6220!6220U41 = \y0y1y2.0 a!6220!6220U41# = \y0y1y2.1 + y1 + y2 a!6220!6220U42 = \y0y1.0 a!6220!6220U42# = \y0y1.1 + y1 a!6220!6220U43 = \y0.0 a!6220!6220U51 = \y0y1y2.0 a!6220!6220U51# = \y0y1y2.1 + y1 + y2 a!6220!6220U52 = \y0y1.0 a!6220!6220U52# = \y0y1.1 + y1 a!6220!6220U53 = \y0.0 a!6220!6220U61 = \y0y1.0 a!6220!6220and = \y0y1.0 a!6220!6220and# = \y0y1.y1 a!6220!6220isNat = \y0.0 a!6220!6220isNatIList = \y0.0 a!6220!6220isNatIListKind = \y0.0 a!6220!6220isNatIListKind# = \y0.1 + y0 a!6220!6220isNatIList# = \y0.1 + y0 a!6220!6220isNatKind = \y0.0 a!6220!6220isNatKind# = \y0.1 + y0 a!6220!6220isNatList = \y0.0 a!6220!6220isNatList# = \y0.1 + y0 a!6220!6220isNat# = \y0.1 + y0 a!6220!6220length = \y0.0 a!6220!6220zeros = 0 and = \y0y1.y0 + 2y1 cons = \y0y1.1 + y0 + 2y1 isNat = \y0.2 + y0 isNatIList = \y0.1 + y0 isNatIListKind = \y0.1 + 2y0 isNatKind = \y0.1 + y0 isNatList = \y0.2 + y0 length = \y0.1 + 2y0 mark = \y0.0 mark# = \y0.y0 nil = 0 s = \y0.1 + y0 tt = 0 zeros = 0 Using this interpretation, the requirements translate to: [[a!6220!6220U11#(tt, _x0)]] = 1 + 2x0 >= 1 + x0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U21#(tt, _x0)]] = 2 + x0 > 1 + x0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U31#(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220U41#(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x1 = [[a!6220!6220U42#(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U41#(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U42#(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatIList#(_x0)]] [[a!6220!6220U51#(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x1 = [[a!6220!6220U52#(a!6220!6220isNat(_x0), _x1)]] [[a!6220!6220U51#(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 = [[a!6220!6220isNat#(_x0)]] [[a!6220!6220U52#(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatList#(_x0)]] [[a!6220!6220and#(tt, _x0)]] = x0 >= x0 = [[mark#(_x0)]] [[a!6220!6220isNat#(length(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220U11#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNat#(length(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNat#(s(_x0))]] = 2 + x0 >= 2 + x0 = [[a!6220!6220U21#(a!6220!6220isNatKind(_x0), _x0)]] [[a!6220!6220isNat#(s(_x0))]] = 2 + x0 > 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatIList#(_x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U31#(a!6220!6220isNatIListKind(_x0), _x0)]] [[a!6220!6220isNatIList#(_x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + x0 + x1 = [[a!6220!6220U41#(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + 2x1 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatIList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatIListKind#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + 2x1 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatIListKind#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatKind#(length(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNatIListKind#(_x0)]] [[a!6220!6220isNatKind#(s(_x0))]] = 2 + x0 > 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + x0 + x1 = [[a!6220!6220U51#(a!6220!6220and(a!6220!6220isNatKind(_x0), isNatIListKind(_x1)), _x0, _x1)]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + 2x1 = [[a!6220!6220and#(a!6220!6220isNatKind(_x0), isNatIListKind(_x1))]] [[a!6220!6220isNatList#(cons(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[mark#(U11(_x0, _x1))]] = 2 + x0 + 2x1 > 1 + 2x1 = [[a!6220!6220U11#(mark(_x0), _x1)]] [[mark#(U11(_x0, _x1))]] = 2 + x0 + 2x1 > x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(isNatList(_x0))]] = 2 + x0 > 1 + x0 = [[a!6220!6220isNatList#(_x0)]] [[mark#(U21(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 = [[a!6220!6220U21#(mark(_x0), _x1)]] [[mark#(U21(_x0, _x1))]] = 2 + x1 + 2x0 > x0 = [[mark#(_x0)]] [[mark#(U22(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 2 + x0 > 1 + x0 = [[a!6220!6220isNat#(_x0)]] [[mark#(U31(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x1 = [[a!6220!6220U31#(mark(_x0), _x1)]] [[mark#(U31(_x0, _x1))]] = 1 + x0 + x1 > x0 = [[mark#(_x0)]] [[mark#(U32(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(U41(_x0, _x1, _x2))]] = 2 + x0 + x1 + x2 > 1 + x1 + x2 = [[a!6220!6220U41#(mark(_x0), _x1, _x2)]] [[mark#(U41(_x0, _x1, _x2))]] = 2 + x0 + x1 + x2 > x0 = [[mark#(_x0)]] [[mark#(U42(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x1 = [[a!6220!6220U42#(mark(_x0), _x1)]] [[mark#(U42(_x0, _x1))]] = 1 + x0 + x1 > x0 = [[mark#(_x0)]] [[mark#(U43(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(isNatIList(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatIList#(_x0)]] [[mark#(U51(_x0, _x1, _x2))]] = 2 + x0 + x1 + x2 > 1 + x1 + x2 = [[a!6220!6220U51#(mark(_x0), _x1, _x2)]] [[mark#(U51(_x0, _x1, _x2))]] = 2 + x0 + x1 + x2 > x0 = [[mark#(_x0)]] [[mark#(U52(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x1 = [[a!6220!6220U52#(mark(_x0), _x1)]] [[mark#(U52(_x0, _x1))]] = 1 + x0 + 2x1 > x0 = [[mark#(_x0)]] [[mark#(U53(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(and(_x0, _x1))]] = x0 + 2x1 >= x1 = [[a!6220!6220and#(mark(_x0), _x1)]] [[mark#(and(_x0, _x1))]] = x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(isNatIListKind(_x0))]] = 1 + 2x0 >= 1 + x0 = [[a!6220!6220isNatIListKind#(_x0)]] [[mark#(isNatKind(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNatKind#(_x0)]] [[mark#(cons(_x0, _x1))]] = 1 + x0 + 2x1 > x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 1 + x0 > x0 = [[mark#(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_3, R_0, minimal, formative) by (P_6, R_0, minimal, formative), where P_6 consists of: a!6220!6220U11#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U31#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220U42#(a!6220!6220isNat(X), Y) a!6220!6220U41#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U42#(tt, X) =#> a!6220!6220isNatIList#(X) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220U52#(a!6220!6220isNat(X), Y) a!6220!6220U51#(tt, X, Y) =#> a!6220!6220isNat#(X) a!6220!6220U52#(tt, X) =#> a!6220!6220isNatList#(X) a!6220!6220and#(tt, X) =#> mark#(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#(X) =#> a!6220!6220isNatIListKind#(X) mark#(U12(X)) =#> mark#(X) mark#(U21(X, Y)) =#> a!6220!6220U21#(mark(X), Y) mark#(U22(X)) =#> mark#(X) mark#(U31(X, Y)) =#> a!6220!6220U31#(mark(X), Y) mark#(U32(X)) =#> mark#(X) mark#(U42(X, Y)) =#> a!6220!6220U42#(mark(X), Y) mark#(U43(X)) =#> mark#(X) mark#(isNatIList(X)) =#> a!6220!6220isNatIList#(X) mark#(U52(X, Y)) =#> a!6220!6220U52#(mark(X), Y) mark#(U53(X)) =#> mark#(X) mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) =#> mark#(X) mark#(isNatIListKind(X)) =#> a!6220!6220isNatIListKind#(X) mark#(isNatKind(X)) =#> a!6220!6220isNatKind#(X) Thus, the original system is terminating if (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : * 1 : * 2 : 4 * 3 : 9 * 4 : 10, 11 * 5 : 7 * 6 : 9 * 7 : * 8 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 9 : * 10 : 1 * 11 : * 12 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 13 : * 14 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 15 : 1 * 16 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 17 : 4 * 18 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 19 : 10, 11 * 20 : 7 * 21 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 22 : 8 * 23 : 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 * 24 : * 25 : This graph has the following strongly connected components: P_7: a!6220!6220and#(tt, X) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(U22(X)) =#> mark#(X) mark#(U32(X)) =#> mark#(X) mark#(U43(X)) =#> mark#(X) mark#(U53(X)) =#> mark#(X) mark#(and(X, Y)) =#> a!6220!6220and#(mark(X), Y) mark#(and(X, Y)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_6, R_0, m, f) by (P_7, R_0, m, f). Thus, the original system is terminating if (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(a!6220!6220and#) = 2 nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(a!6220!6220and#(tt, X)) = X = X = nu(mark#(X)) nu(mark#(U12(X))) = U12(X) |> X = nu(mark#(X)) nu(mark#(U22(X))) = U22(X) |> X = nu(mark#(X)) nu(mark#(U32(X))) = U32(X) |> X = nu(mark#(X)) nu(mark#(U43(X))) = U43(X) |> X = nu(mark#(X)) nu(mark#(U53(X))) = U53(X) |> X = nu(mark#(X)) nu(mark#(and(X, Y))) = and(X, Y) |> Y = nu(a!6220!6220and#(mark(X), Y)) nu(mark#(and(X, Y))) = and(X, Y) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by (P_8, R_0, minimal, f), where P_8 contains: a!6220!6220and#(tt, X) =#> mark#(X) Thus, the original system is terminating if (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 : 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.