/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] --> o 1 : [o] --> o O : [o] --> o choice : [o] --> o cons : [o * o] --> o eq : [o * o] --> o false : [] --> o guess : [o] --> o if : [o * o * o] --> o member : [o * o] --> o negate : [o] --> o nil : [] --> o sat : [o] --> o satck : [o * o] --> o true : [] --> o unsat : [] --> o verify : [o] --> o if(true, X, Y) => X if(false, X, Y) => Y member(X, nil) => false member(X, cons(Y, Z)) => if(eq(X, Y), true, member(X, Z)) eq(nil, nil) => true eq(O(X), 0(Y)) => eq(X, Y) eq(0(X), 1(Y)) => false eq(1(X), 0(Y)) => false eq(1(X), 1(Y)) => eq(X, Y) negate(0(X)) => 1(X) negate(1(X)) => 0(X) choice(cons(X, Y)) => X choice(cons(X, Y)) => choice(Y) guess(nil) => nil guess(cons(X, Y)) => cons(choice(X), guess(Y)) verify(nil) => true verify(cons(X, Y)) => if(member(negate(X), Y), false, verify(Y)) sat(X) => satck(X, guess(X)) satck(X, Y) => if(verify(Y), Y, unsat) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(true, X, Y) >? X if(false, X, Y) >? Y member(X, nil) >? false member(X, cons(Y, Z)) >? if(eq(X, Y), true, member(X, Z)) eq(nil, nil) >? true eq(O(X), 0(Y)) >? eq(X, Y) eq(0(X), 1(Y)) >? false eq(1(X), 0(Y)) >? false eq(1(X), 1(Y)) >? eq(X, Y) negate(0(X)) >? 1(X) negate(1(X)) >? 0(X) choice(cons(X, Y)) >? X choice(cons(X, Y)) >? choice(Y) guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true verify(cons(X, Y)) >? if(member(negate(X), Y), false, verify(Y)) sat(X) >? satck(X, guess(X)) satck(X, Y) >? if(verify(Y), Y, unsat) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[false]] = _|_ [[nil]] = _|_ [[true]] = _|_ [[unsat]] = _|_ We choose Lex = {} and Mul = {0, 1, O, choice, cons, eq, guess, if, member, negate, sat, satck, verify}, and the following precedence: sat > satck > guess > 0 = 1 = negate = verify > member > if > eq > cons > choice > O Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(_|_, X, Y) > X if(_|_, X, Y) >= Y member(X, _|_) >= _|_ member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) eq(_|_, _|_) >= _|_ eq(O(X), 0(Y)) >= eq(X, Y) eq(0(X), 1(Y)) > _|_ eq(1(X), 0(Y)) >= _|_ eq(1(X), 1(Y)) > eq(X, Y) negate(0(X)) >= 1(X) negate(1(X)) >= 0(X) choice(cons(X, Y)) > X choice(cons(X, Y)) >= choice(Y) guess(_|_) >= _|_ guess(cons(X, Y)) >= cons(choice(X), guess(Y)) verify(_|_) >= _|_ verify(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) sat(X) >= satck(X, guess(X)) satck(X, Y) > if(verify(Y), Y, _|_) With these choices, we have: 1] if(_|_, X, Y) > X because [2], by definition 2] if*(_|_, X, Y) >= X because [3], by (Select) 3] X >= X by (Meta) 4] if(_|_, X, Y) >= Y because [5], by (Star) 5] if*(_|_, X, Y) >= Y because [6], by (Select) 6] Y >= Y by (Meta) 7] member(X, _|_) >= _|_ by (Bot) 8] member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because [9], by (Star) 9] member*(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because member > if, [10], [17] and [18], by (Copy) 10] member*(X, cons(Y, Z)) >= eq(X, Y) because member > eq, [11] and [13], by (Copy) 11] member*(X, cons(Y, Z)) >= X because [12], by (Select) 12] X >= X by (Meta) 13] member*(X, cons(Y, Z)) >= Y because [14], by (Select) 14] cons(Y, Z) >= Y because [15], by (Star) 15] cons*(Y, Z) >= Y because [16], by (Select) 16] Y >= Y by (Meta) 17] member*(X, cons(Y, Z)) >= _|_ by (Bot) 18] member*(X, cons(Y, Z)) >= member(X, Z) because member in Mul, [19] and [20], by (Stat) 19] X >= X by (Meta) 20] cons(Y, Z) > Z because [21], by definition 21] cons*(Y, Z) >= Z because [22], by (Select) 22] Z >= Z by (Meta) 23] eq(_|_, _|_) >= _|_ by (Bot) 24] eq(O(X), 0(Y)) >= eq(X, Y) because [25], by (Star) 25] eq*(O(X), 0(Y)) >= eq(X, Y) because eq in Mul, [26] and [28], by (Stat) 26] O(X) > X because [27], by definition 27] O*(X) >= X because [19], by (Select) 28] 0(Y) >= Y because [29], by (Star) 29] 0*(Y) >= Y because [16], by (Select) 30] eq(0(X), 1(Y)) > _|_ because [31], by definition 31] eq*(0(X), 1(Y)) >= _|_ by (Bot) 32] eq(1(X), 0(Y)) >= _|_ by (Bot) 33] eq(1(X), 1(Y)) > eq(X, Y) because [34], by definition 34] eq*(1(X), 1(Y)) >= eq(X, Y) because eq in Mul, [35] and [37], by (Stat) 35] 1(X) >= X because [36], by (Star) 36] 1*(X) >= X because [19], by (Select) 37] 1(Y) > Y because [38], by definition 38] 1*(Y) >= Y because [16], by (Select) 39] negate(0(X)) >= 1(X) because [40], by (Star) 40] negate*(0(X)) >= 1(X) because [41], by (Select) 41] 0(X) >= 1(X) because 0 = 1, 0 in Mul and [19], by (Fun) 42] negate(1(X)) >= 0(X) because negate = 0, negate in Mul and [35], by (Fun) 43] choice(cons(X, Y)) > X because [44], by definition 44] choice*(cons(X, Y)) >= X because [45], by (Select) 45] cons(X, Y) >= X because [46], by (Star) 46] cons*(X, Y) >= X because [19], by (Select) 47] choice(cons(X, Y)) >= choice(Y) because [48], by (Star) 48] choice*(cons(X, Y)) >= choice(Y) because [49], by (Select) 49] cons(X, Y) >= choice(Y) because [50], by (Star) 50] cons*(X, Y) >= choice(Y) because cons > choice and [51], by (Copy) 51] cons*(X, Y) >= Y because [52], by (Select) 52] Y >= Y by (Meta) 53] guess(_|_) >= _|_ by (Bot) 54] guess(cons(X, Y)) >= cons(choice(X), guess(Y)) because [55], by (Star) 55] guess*(cons(X, Y)) >= cons(choice(X), guess(Y)) because guess > cons, [56] and [61], by (Copy) 56] guess*(cons(X, Y)) >= choice(X) because [57], by (Select) 57] cons(X, Y) >= choice(X) because [58], by (Star) 58] cons*(X, Y) >= choice(X) because cons > choice and [59], by (Copy) 59] cons*(X, Y) >= X because [60], by (Select) 60] X >= X by (Meta) 61] guess*(cons(X, Y)) >= guess(Y) because guess in Mul and [62], by (Stat) 62] cons(X, Y) > Y because [63], by definition 63] cons*(X, Y) >= Y because [64], by (Select) 64] Y >= Y by (Meta) 65] verify(_|_) >= _|_ by (Bot) 66] verify(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) because [67], by (Star) 67] verify*(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) because verify > if, [68], [77] and [78], by (Copy) 68] verify*(cons(X, Y)) >= member(negate(X), Y) because verify > member, [69] and [73], by (Copy) 69] verify*(cons(X, Y)) >= negate(X) because verify = negate, verify in Mul and [70], by (Stat) 70] cons(X, Y) > X because [71], by definition 71] cons*(X, Y) >= X because [72], by (Select) 72] X >= X by (Meta) 73] verify*(cons(X, Y)) >= Y because [74], by (Select) 74] cons(X, Y) >= Y because [75], by (Star) 75] cons*(X, Y) >= Y because [76], by (Select) 76] Y >= Y by (Meta) 77] verify*(cons(X, Y)) >= _|_ by (Bot) 78] verify*(cons(X, Y)) >= verify(Y) because verify in Mul and [79], by (Stat) 79] cons(X, Y) > Y because [80], by definition 80] cons*(X, Y) >= Y because [76], by (Select) 81] sat(X) >= satck(X, guess(X)) because [82], by (Star) 82] sat*(X) >= satck(X, guess(X)) because sat > satck, [83] and [84], by (Copy) 83] sat*(X) >= X because [64], by (Select) 84] sat*(X) >= guess(X) because sat > guess and [83], by (Copy) 85] satck(X, Y) > if(verify(Y), Y, _|_) because [86], by definition 86] satck*(X, Y) >= if(verify(Y), Y, _|_) because satck > if, [87], [88] and [90], by (Copy) 87] satck*(X, Y) >= verify(Y) because satck > verify and [88], by (Copy) 88] satck*(X, Y) >= Y because [89], by (Select) 89] Y >= Y by (Meta) 90] satck*(X, Y) >= _|_ by (Bot) We can thus remove the following rules: if(true, X, Y) => X eq(0(X), 1(Y)) => false eq(1(X), 1(Y)) => eq(X, Y) choice(cons(X, Y)) => X satck(X, Y) => if(verify(Y), Y, unsat) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(false, X, Y) >? Y member(X, nil) >? false member(X, cons(Y, Z)) >? if(eq(X, Y), true, member(X, Z)) eq(nil, nil) >? true eq(O(X), 0(Y)) >? eq(X, Y) eq(1(X), 0(Y)) >? false negate(0(X)) >? 1(X) negate(1(X)) >? 0(X) choice(cons(X, Y)) >? choice(Y) guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true verify(cons(X, Y)) >? if(member(negate(X), Y), false, verify(Y)) sat(X) >? satck(X, guess(X)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[choice(x_1)]] = x_1 [[false]] = _|_ [[nil]] = _|_ [[true]] = _|_ We choose Lex = {} and Mul = {0, 1, O, cons, eq, guess, if, member, negate, sat, satck, verify}, and the following precedence: sat > guess > satck > verify > cons > member > if > O > negate > 0 > 1 > eq Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(_|_, X, Y) >= Y member(X, _|_) >= _|_ member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) eq(_|_, _|_) >= _|_ eq(O(X), 0(Y)) > eq(X, Y) eq(1(X), 0(Y)) >= _|_ negate(0(X)) > 1(X) negate(1(X)) > 0(X) cons(X, Y) >= Y guess(_|_) >= _|_ guess(cons(X, Y)) >= cons(X, guess(Y)) verify(_|_) >= _|_ verify(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) sat(X) >= satck(X, guess(X)) With these choices, we have: 1] if(_|_, X, Y) >= Y because [2], by (Star) 2] if*(_|_, X, Y) >= Y because [3], by (Select) 3] Y >= Y by (Meta) 4] member(X, _|_) >= _|_ by (Bot) 5] member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because [6], by (Star) 6] member*(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because member > if, [7], [14] and [15], by (Copy) 7] member*(X, cons(Y, Z)) >= eq(X, Y) because member > eq, [8] and [10], by (Copy) 8] member*(X, cons(Y, Z)) >= X because [9], by (Select) 9] X >= X by (Meta) 10] member*(X, cons(Y, Z)) >= Y because [11], by (Select) 11] cons(Y, Z) >= Y because [12], by (Star) 12] cons*(Y, Z) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] member*(X, cons(Y, Z)) >= _|_ by (Bot) 15] member*(X, cons(Y, Z)) >= member(X, Z) because member in Mul, [16] and [17], by (Stat) 16] X >= X by (Meta) 17] cons(Y, Z) > Z because [18], by definition 18] cons*(Y, Z) >= Z because [19], by (Select) 19] Z >= Z by (Meta) 20] eq(_|_, _|_) >= _|_ by (Bot) 21] eq(O(X), 0(Y)) > eq(X, Y) because [22], by definition 22] eq*(O(X), 0(Y)) >= eq(X, Y) because eq in Mul, [23] and [25], by (Stat) 23] O(X) >= X because [24], by (Star) 24] O*(X) >= X because [16], by (Select) 25] 0(Y) > Y because [26], by definition 26] 0*(Y) >= Y because [13], by (Select) 27] eq(1(X), 0(Y)) >= _|_ by (Bot) 28] negate(0(X)) > 1(X) because [29], by definition 29] negate*(0(X)) >= 1(X) because negate > 1 and [30], by (Copy) 30] negate*(0(X)) >= X because [31], by (Select) 31] 0(X) >= X because [32], by (Star) 32] 0*(X) >= X because [16], by (Select) 33] negate(1(X)) > 0(X) because [34], by definition 34] negate*(1(X)) >= 0(X) because negate > 0 and [35], by (Copy) 35] negate*(1(X)) >= X because [36], by (Select) 36] 1(X) >= X because [37], by (Star) 37] 1*(X) >= X because [16], by (Select) 38] cons(X, Y) >= Y because [39], by (Star) 39] cons*(X, Y) >= Y because [40], by (Select) 40] Y >= Y by (Meta) 41] guess(_|_) >= _|_ by (Bot) 42] guess(cons(X, Y)) >= cons(X, guess(Y)) because [43], by (Star) 43] guess*(cons(X, Y)) >= cons(X, guess(Y)) because guess > cons, [44] and [48], by (Copy) 44] guess*(cons(X, Y)) >= X because [45], by (Select) 45] cons(X, Y) >= X because [46], by (Star) 46] cons*(X, Y) >= X because [47], by (Select) 47] X >= X by (Meta) 48] guess*(cons(X, Y)) >= guess(Y) because guess in Mul and [49], by (Stat) 49] cons(X, Y) > Y because [50], by definition 50] cons*(X, Y) >= Y because [51], by (Select) 51] Y >= Y by (Meta) 52] verify(_|_) >= _|_ by (Bot) 53] verify(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) because [54], by (Star) 54] verify*(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) because verify > if, [55], [63] and [64], by (Copy) 55] verify*(cons(X, Y)) >= member(negate(X), Y) because [56], by (Select) 56] cons(X, Y) >= member(negate(X), Y) because [57], by (Star) 57] cons*(X, Y) >= member(negate(X), Y) because cons > member, [58] and [61], by (Copy) 58] cons*(X, Y) >= negate(X) because cons > negate and [59], by (Copy) 59] cons*(X, Y) >= X because [60], by (Select) 60] X >= X by (Meta) 61] cons*(X, Y) >= Y because [62], by (Select) 62] Y >= Y by (Meta) 63] verify*(cons(X, Y)) >= _|_ by (Bot) 64] verify*(cons(X, Y)) >= verify(Y) because verify in Mul and [65], by (Stat) 65] cons(X, Y) > Y because [61], by definition 66] sat(X) >= satck(X, guess(X)) because [67], by (Star) 67] sat*(X) >= satck(X, guess(X)) because sat > satck, [68] and [69], by (Copy) 68] sat*(X) >= X because [51], by (Select) 69] sat*(X) >= guess(X) because sat > guess and [68], by (Copy) We can thus remove the following rules: eq(O(X), 0(Y)) => eq(X, Y) negate(0(X)) => 1(X) negate(1(X)) => 0(X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(false, X, Y) >? Y member(X, nil) >? false member(X, cons(Y, Z)) >? if(eq(X, Y), true, member(X, Z)) eq(nil, nil) >? true eq(1(X), 0(Y)) >? false choice(cons(X, Y)) >? choice(Y) guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true verify(cons(X, Y)) >? if(member(negate(X), Y), false, verify(Y)) sat(X) >? satck(X, guess(X)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0(x_1)]] = x_1 [[1(x_1)]] = x_1 [[choice(x_1)]] = x_1 [[false]] = _|_ [[true]] = _|_ We choose Lex = {} and Mul = {cons, eq, guess, if, member, negate, nil, sat, satck, verify}, and the following precedence: sat > cons = guess = negate > verify > nil > member > eq > satck > if Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(_|_, X, Y) >= Y member(X, nil) >= _|_ member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) eq(nil, nil) >= _|_ eq(X, Y) >= _|_ cons(X, Y) >= Y guess(nil) >= nil guess(cons(X, Y)) >= cons(X, guess(Y)) verify(nil) >= _|_ verify(cons(X, Y)) > if(member(negate(X), Y), _|_, verify(Y)) sat(X) >= satck(X, guess(X)) With these choices, we have: 1] if(_|_, X, Y) >= Y because [2], by (Star) 2] if*(_|_, X, Y) >= Y because [3], by (Select) 3] Y >= Y by (Meta) 4] member(X, nil) >= _|_ by (Bot) 5] member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because [6], by (Star) 6] member*(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because member > if, [7], [14] and [15], by (Copy) 7] member*(X, cons(Y, Z)) >= eq(X, Y) because member > eq, [8] and [10], by (Copy) 8] member*(X, cons(Y, Z)) >= X because [9], by (Select) 9] X >= X by (Meta) 10] member*(X, cons(Y, Z)) >= Y because [11], by (Select) 11] cons(Y, Z) >= Y because [12], by (Star) 12] cons*(Y, Z) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] member*(X, cons(Y, Z)) >= _|_ by (Bot) 15] member*(X, cons(Y, Z)) >= member(X, Z) because member in Mul, [16] and [17], by (Stat) 16] X >= X by (Meta) 17] cons(Y, Z) > Z because [18], by definition 18] cons*(Y, Z) >= Z because [19], by (Select) 19] Z >= Z by (Meta) 20] eq(nil, nil) >= _|_ by (Bot) 21] eq(X, Y) >= _|_ by (Bot) 22] cons(X, Y) >= Y because [23], by (Star) 23] cons*(X, Y) >= Y because [24], by (Select) 24] Y >= Y by (Meta) 25] guess(nil) >= nil because [26], by (Star) 26] guess*(nil) >= nil because [27], by (Select) 27] nil >= nil by (Fun) 28] guess(cons(X, Y)) >= cons(X, guess(Y)) because [29], by (Star) 29] guess*(cons(X, Y)) >= cons(X, guess(Y)) because guess = cons, guess in Mul, [30] and [33], by (Stat) 30] cons(X, Y) > X because [31], by definition 31] cons*(X, Y) >= X because [32], by (Select) 32] X >= X by (Meta) 33] cons(X, Y) > guess(Y) because [34], by definition 34] cons*(X, Y) >= guess(Y) because cons = guess, cons in Mul and [35], by (Stat) 35] Y >= Y by (Meta) 36] verify(nil) >= _|_ by (Bot) 37] verify(cons(X, Y)) > if(member(negate(X), Y), _|_, verify(Y)) because [38], by definition 38] verify*(cons(X, Y)) >= if(member(negate(X), Y), _|_, verify(Y)) because verify > if, [39], [46] and [47], by (Copy) 39] verify*(cons(X, Y)) >= member(negate(X), Y) because [40], by (Select) 40] cons(X, Y) >= member(negate(X), Y) because [41], by (Star) 41] cons*(X, Y) >= member(negate(X), Y) because cons > member, [42] and [44], by (Copy) 42] cons*(X, Y) >= negate(X) because cons = negate, cons in Mul and [43], by (Stat) 43] X >= X by (Meta) 44] cons*(X, Y) >= Y because [45], by (Select) 45] Y >= Y by (Meta) 46] verify*(cons(X, Y)) >= _|_ by (Bot) 47] verify*(cons(X, Y)) >= verify(Y) because verify in Mul and [48], by (Stat) 48] cons(X, Y) > Y because [44], by definition 49] sat(X) >= satck(X, guess(X)) because [50], by (Star) 50] sat*(X) >= satck(X, guess(X)) because sat > satck, [51] and [52], by (Copy) 51] sat*(X) >= X because [35], by (Select) 52] sat*(X) >= guess(X) because sat > guess and [51], by (Copy) We can thus remove the following rules: verify(cons(X, Y)) => if(member(negate(X), Y), false, verify(Y)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(false, X, Y) >? Y member(X, nil) >? false member(X, cons(Y, Z)) >? if(eq(X, Y), true, member(X, Z)) eq(nil, nil) >? true eq(1(X), 0(Y)) >? false choice(cons(X, Y)) >? choice(Y) guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true sat(X) >? satck(X, guess(X)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0(x_1)]] = x_1 [[1(x_1)]] = x_1 [[choice(x_1)]] = x_1 [[false]] = _|_ [[guess(x_1)]] = x_1 [[true]] = _|_ [[verify(x_1)]] = x_1 We choose Lex = {} and Mul = {cons, eq, if, member, nil, sat, satck}, and the following precedence: member > eq > nil > cons > if > sat > satck Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(_|_, X, Y) >= Y member(X, nil) >= _|_ member(X, cons(Y, Z)) > if(eq(X, Y), _|_, member(X, Z)) eq(nil, nil) >= _|_ eq(X, Y) >= _|_ cons(X, Y) > Y nil >= nil cons(X, Y) >= cons(X, Y) nil >= _|_ sat(X) >= satck(X, X) With these choices, we have: 1] if(_|_, X, Y) >= Y because [2], by (Star) 2] if*(_|_, X, Y) >= Y because [3], by (Select) 3] Y >= Y by (Meta) 4] member(X, nil) >= _|_ by (Bot) 5] member(X, cons(Y, Z)) > if(eq(X, Y), _|_, member(X, Z)) because [6], by definition 6] member*(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) because member > if, [7], [14] and [15], by (Copy) 7] member*(X, cons(Y, Z)) >= eq(X, Y) because member > eq, [8] and [10], by (Copy) 8] member*(X, cons(Y, Z)) >= X because [9], by (Select) 9] X >= X by (Meta) 10] member*(X, cons(Y, Z)) >= Y because [11], by (Select) 11] cons(Y, Z) >= Y because [12], by (Star) 12] cons*(Y, Z) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] member*(X, cons(Y, Z)) >= _|_ by (Bot) 15] member*(X, cons(Y, Z)) >= member(X, Z) because member in Mul, [16] and [17], by (Stat) 16] X >= X by (Meta) 17] cons(Y, Z) > Z because [18], by definition 18] cons*(Y, Z) >= Z because [19], by (Select) 19] Z >= Z by (Meta) 20] eq(nil, nil) >= _|_ by (Bot) 21] eq(X, Y) >= _|_ by (Bot) 22] cons(X, Y) > Y because [23], by definition 23] cons*(X, Y) >= Y because [24], by (Select) 24] Y >= Y by (Meta) 25] nil >= nil by (Fun) 26] cons(X, Y) >= cons(X, Y) because cons in Mul, [27] and [28], by (Fun) 27] X >= X by (Meta) 28] Y >= Y by (Meta) 29] nil >= _|_ by (Bot) 30] sat(X) >= satck(X, X) because [31], by (Star) 31] sat*(X) >= satck(X, X) because sat > satck, [32] and [33], by (Copy) 32] sat*(X) >= X because [28], by (Select) 33] sat*(X) >= X because [28], by (Select) We can thus remove the following rules: member(X, cons(Y, Z)) => if(eq(X, Y), true, member(X, Z)) choice(cons(X, Y)) => choice(Y) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(false, X, Y) >? Y member(X, nil) >? false eq(nil, nil) >? true eq(1(X), 0(Y)) >? false guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true sat(X) >? satck(X, guess(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = \y0.3 + y0 1 = \y0.3 + y0 choice = \y0.y0 cons = \y0y1.1 + y0 + y1 eq = \y0y1.3 + 3y0 + 3y1 false = 0 guess = \y0.2 + 2y0 if = \y0y1y2.3 + y0 + y1 + y2 member = \y0y1.3 + y0 + 3y1 nil = 0 sat = \y0.3 + 3y0 satck = \y0y1.y0 + y1 true = 0 verify = \y0.3 + 3y0 Using this interpretation, the requirements translate to: [[if(false, _x0, _x1)]] = 3 + x0 + x1 > x1 = [[_x1]] [[member(_x0, nil)]] = 3 + x0 > 0 = [[false]] [[eq(nil, nil)]] = 3 > 0 = [[true]] [[eq(1(_x0), 0(_x1))]] = 21 + 3x0 + 3x1 > 0 = [[false]] [[guess(nil)]] = 2 > 0 = [[nil]] [[guess(cons(_x0, _x1))]] = 4 + 2x0 + 2x1 > 3 + x0 + 2x1 = [[cons(choice(_x0), guess(_x1))]] [[verify(nil)]] = 3 > 0 = [[true]] [[sat(_x0)]] = 3 + 3x0 > 2 + 3x0 = [[satck(_x0, guess(_x0))]] We can thus remove the following rules: if(false, X, Y) => Y member(X, nil) => false eq(nil, nil) => true eq(1(X), 0(Y)) => false guess(nil) => nil guess(cons(X, Y)) => cons(choice(X), guess(Y)) verify(nil) => true sat(X) => satck(X, guess(X)) All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.