/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o active : [o] --> o adx : [o] --> o cons : [o * o] --> o hd : [o] --> o incr : [o] --> o mark : [o] --> o nats : [] --> o s : [o] --> o tl : [o] --> o zeros : [] --> o active(nats) => mark(adx(zeros)) active(zeros) => mark(cons(0, zeros)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) => mark(incr(cons(X, adx(Y)))) active(hd(cons(X, Y))) => mark(X) active(tl(cons(X, Y))) => mark(Y) mark(nats) => active(nats) mark(adx(X)) => active(adx(mark(X))) mark(zeros) => active(zeros) mark(cons(X, Y)) => active(cons(X, Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(s(X)) => active(s(X)) mark(hd(X)) => active(hd(mark(X))) mark(tl(X)) => active(tl(mark(X))) adx(mark(X)) => adx(X) adx(active(X)) => adx(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) s(mark(X)) => s(X) s(active(X)) => s(X) hd(mark(X)) => hd(X) hd(active(X)) => hd(X) tl(mark(X)) => tl(X) tl(active(X)) => tl(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]): active(nats) >? mark(adx(zeros)) active(zeros) >? mark(cons(0, zeros)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) >? mark(incr(cons(X, adx(Y)))) active(hd(cons(X, Y))) >? mark(X) active(tl(cons(X, Y))) >? mark(Y) mark(nats) >? active(nats) mark(adx(X)) >? active(adx(mark(X))) mark(zeros) >? active(zeros) mark(cons(X, Y)) >? active(cons(X, Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(s(X)) >? active(s(X)) mark(hd(X)) >? active(hd(mark(X))) mark(tl(X)) >? active(tl(mark(X))) adx(mark(X)) >? adx(X) adx(active(X)) >? adx(X) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) hd(mark(X)) >? hd(X) hd(active(X)) >? hd(X) tl(mark(X)) >? tl(X) tl(active(X)) >? tl(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 adx = \y0.2y0 cons = \y0y1.y0 + y1 hd = \y0.2y0 incr = \y0.y0 mark = \y0.y0 nats = 1 s = \y0.y0 tl = \y0.1 + 2y0 zeros = 0 Using this interpretation, the requirements translate to: [[active(nats)]] = 1 > 0 = [[mark(adx(zeros))]] [[active(zeros)]] = 0 >= 0 = [[mark(cons(0, zeros))]] [[active(incr(cons(_x0, _x1)))]] = x0 + x1 >= x0 + x1 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(adx(cons(_x0, _x1)))]] = 2x0 + 2x1 >= x0 + 2x1 = [[mark(incr(cons(_x0, adx(_x1))))]] [[active(hd(cons(_x0, _x1)))]] = 2x0 + 2x1 >= x0 = [[mark(_x0)]] [[active(tl(cons(_x0, _x1)))]] = 1 + 2x0 + 2x1 > x1 = [[mark(_x1)]] [[mark(nats)]] = 1 >= 1 = [[active(nats)]] [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[active(adx(mark(_x0)))]] [[mark(zeros)]] = 0 >= 0 = [[active(zeros)]] [[mark(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(cons(_x0, _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = x0 >= x0 = [[active(incr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(_x0))]] [[mark(hd(_x0))]] = 2x0 >= 2x0 = [[active(hd(mark(_x0)))]] [[mark(tl(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[active(tl(mark(_x0)))]] [[adx(mark(_x0))]] = 2x0 >= 2x0 = [[adx(_x0)]] [[adx(active(_x0))]] = 2x0 >= 2x0 = [[adx(_x0)]] [[cons(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[hd(mark(_x0))]] = 2x0 >= 2x0 = [[hd(_x0)]] [[hd(active(_x0))]] = 2x0 >= 2x0 = [[hd(_x0)]] [[tl(mark(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[tl(_x0)]] [[tl(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[tl(_x0)]] We can thus remove the following rules: active(nats) => mark(adx(zeros)) active(tl(cons(X, Y))) => mark(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]): active(zeros) >? mark(cons(0, zeros)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) >? mark(incr(cons(X, adx(Y)))) active(hd(cons(X, Y))) >? mark(X) mark(nats) >? active(nats) mark(adx(X)) >? active(adx(mark(X))) mark(zeros) >? active(zeros) mark(cons(X, Y)) >? active(cons(X, Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(s(X)) >? active(s(X)) mark(hd(X)) >? active(hd(mark(X))) mark(tl(X)) >? active(tl(mark(X))) adx(mark(X)) >? adx(X) adx(active(X)) >? adx(X) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) hd(mark(X)) >? hd(X) hd(active(X)) >? hd(X) tl(mark(X)) >? tl(X) tl(active(X)) >? tl(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 adx = \y0.y0 cons = \y0y1.y1 + 2y0 hd = \y0.2 + 2y0 incr = \y0.y0 mark = \y0.y0 nats = 0 s = \y0.y0 tl = \y0.2y0 zeros = 0 Using this interpretation, the requirements translate to: [[active(zeros)]] = 0 >= 0 = [[mark(cons(0, zeros))]] [[active(incr(cons(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(adx(cons(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(incr(cons(_x0, adx(_x1))))]] [[active(hd(cons(_x0, _x1)))]] = 2 + 2x1 + 4x0 > x0 = [[mark(_x0)]] [[mark(nats)]] = 0 >= 0 = [[active(nats)]] [[mark(adx(_x0))]] = x0 >= x0 = [[active(adx(mark(_x0)))]] [[mark(zeros)]] = 0 >= 0 = [[active(zeros)]] [[mark(cons(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(cons(_x0, _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = x0 >= x0 = [[active(incr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(_x0))]] [[mark(hd(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(hd(mark(_x0)))]] [[mark(tl(_x0))]] = 2x0 >= 2x0 = [[active(tl(mark(_x0)))]] [[adx(mark(_x0))]] = x0 >= x0 = [[adx(_x0)]] [[adx(active(_x0))]] = x0 >= x0 = [[adx(_x0)]] [[cons(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[hd(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[hd(_x0)]] [[hd(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[hd(_x0)]] [[tl(mark(_x0))]] = 2x0 >= 2x0 = [[tl(_x0)]] [[tl(active(_x0))]] = 2x0 >= 2x0 = [[tl(_x0)]] We can thus remove the following rules: active(hd(cons(X, Y))) => mark(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] active#(zeros) =#> mark#(cons(0, zeros)) 1] active#(zeros) =#> cons#(0, zeros) 2] active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) 3] active#(incr(cons(X, Y))) =#> cons#(s(X), incr(Y)) 4] active#(incr(cons(X, Y))) =#> s#(X) 5] active#(incr(cons(X, Y))) =#> incr#(Y) 6] active#(adx(cons(X, Y))) =#> mark#(incr(cons(X, adx(Y)))) 7] active#(adx(cons(X, Y))) =#> incr#(cons(X, adx(Y))) 8] active#(adx(cons(X, Y))) =#> cons#(X, adx(Y)) 9] active#(adx(cons(X, Y))) =#> adx#(Y) 10] mark#(nats) =#> active#(nats) 11] mark#(adx(X)) =#> active#(adx(mark(X))) 12] mark#(adx(X)) =#> adx#(mark(X)) 13] mark#(adx(X)) =#> mark#(X) 14] mark#(zeros) =#> active#(zeros) 15] mark#(cons(X, Y)) =#> active#(cons(X, Y)) 16] mark#(cons(X, Y)) =#> cons#(X, Y) 17] mark#(0) =#> active#(0) 18] mark#(incr(X)) =#> active#(incr(mark(X))) 19] mark#(incr(X)) =#> incr#(mark(X)) 20] mark#(incr(X)) =#> mark#(X) 21] mark#(s(X)) =#> active#(s(X)) 22] mark#(s(X)) =#> s#(X) 23] mark#(hd(X)) =#> active#(hd(mark(X))) 24] mark#(hd(X)) =#> hd#(mark(X)) 25] mark#(hd(X)) =#> mark#(X) 26] mark#(tl(X)) =#> active#(tl(mark(X))) 27] mark#(tl(X)) =#> tl#(mark(X)) 28] mark#(tl(X)) =#> mark#(X) 29] adx#(mark(X)) =#> adx#(X) 30] adx#(active(X)) =#> adx#(X) 31] cons#(mark(X), Y) =#> cons#(X, Y) 32] cons#(X, mark(Y)) =#> cons#(X, Y) 33] cons#(active(X), Y) =#> cons#(X, Y) 34] cons#(X, active(Y)) =#> cons#(X, Y) 35] incr#(mark(X)) =#> incr#(X) 36] incr#(active(X)) =#> incr#(X) 37] s#(mark(X)) =#> s#(X) 38] s#(active(X)) =#> s#(X) 39] hd#(mark(X)) =#> hd#(X) 40] hd#(active(X)) =#> hd#(X) 41] tl#(mark(X)) =#> tl#(X) 42] tl#(active(X)) =#> tl#(X) Rules R_0: active(zeros) => mark(cons(0, zeros)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) => mark(incr(cons(X, adx(Y)))) mark(nats) => active(nats) mark(adx(X)) => active(adx(mark(X))) mark(zeros) => active(zeros) mark(cons(X, Y)) => active(cons(X, Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(s(X)) => active(s(X)) mark(hd(X)) => active(hd(mark(X))) mark(tl(X)) => active(tl(mark(X))) adx(mark(X)) => adx(X) adx(active(X)) => adx(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) s(mark(X)) => s(X) s(active(X)) => s(X) hd(mark(X)) => hd(X) hd(active(X)) => hd(X) tl(mark(X)) => tl(X) tl(active(X)) => tl(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 : 15, 16 * 1 : * 2 : 15, 16 * 3 : * 4 : 37, 38 * 5 : 35, 36 * 6 : 18, 19, 20 * 7 : * 8 : 31, 33 * 9 : 29, 30 * 10 : * 11 : 6, 7, 8, 9 * 12 : 29, 30 * 13 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 14 : 0, 1 * 15 : * 16 : 31, 32, 33, 34 * 17 : * 18 : 2, 3, 4, 5 * 19 : 35, 36 * 20 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 21 : * 22 : 37, 38 * 23 : * 24 : 39, 40 * 25 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 26 : * 27 : 41, 42 * 28 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 29 : 29, 30 * 30 : 29, 30 * 31 : 31, 32, 33, 34 * 32 : 31, 32, 33, 34 * 33 : 31, 32, 33, 34 * 34 : 31, 32, 33, 34 * 35 : 35, 36 * 36 : 35, 36 * 37 : 37, 38 * 38 : 37, 38 * 39 : 39, 40 * 40 : 39, 40 * 41 : 41, 42 * 42 : 41, 42 This graph has the following strongly connected components: P_1: active#(adx(cons(X, Y))) =#> mark#(incr(cons(X, adx(Y)))) mark#(adx(X)) =#> active#(adx(mark(X))) mark#(adx(X)) =#> mark#(X) mark#(incr(X)) =#> mark#(X) mark#(hd(X)) =#> mark#(X) mark#(tl(X)) =#> mark#(X) P_2: adx#(mark(X)) =#> adx#(X) adx#(active(X)) =#> adx#(X) P_3: cons#(mark(X), Y) =#> cons#(X, Y) cons#(X, mark(Y)) =#> cons#(X, Y) cons#(active(X), Y) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) P_4: incr#(mark(X)) =#> incr#(X) incr#(active(X)) =#> incr#(X) P_5: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_6: hd#(mark(X)) =#> hd#(X) hd#(active(X)) =#> hd#(X) P_7: tl#(mark(X)) =#> tl#(X) tl#(active(X)) =#> tl#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f) and (P_7, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(tl#) = 1 Thus, we can orient the dependency pairs as follows: nu(tl#(mark(X))) = mark(X) |> X = nu(tl#(X)) nu(tl#(active(X))) = active(X) |> X = nu(tl#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(hd#) = 1 Thus, we can orient the dependency pairs as follows: nu(hd#(mark(X))) = mark(X) |> X = nu(hd#(X)) nu(hd#(active(X))) = active(X) |> X = nu(hd#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_5, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(s#) = 1 Thus, we can orient the dependency pairs as follows: nu(s#(mark(X))) = mark(X) |> X = nu(s#(X)) nu(s#(active(X))) = active(X) |> X = nu(s#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(incr#) = 1 Thus, we can orient the dependency pairs as follows: nu(incr#(mark(X))) = mark(X) |> X = nu(incr#(X)) nu(incr#(active(X))) = active(X) |> X = nu(incr#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 1 Thus, we can orient the dependency pairs as follows: nu(cons#(mark(X), Y)) = mark(X) |> X = nu(cons#(X, Y)) nu(cons#(X, mark(Y))) = X = X = nu(cons#(X, Y)) nu(cons#(active(X), Y)) = active(X) |> X = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = X = X = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by (P_8, R_0, minimal, f), where P_8 contains: cons#(X, mark(Y)) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 2 Thus, we can orient the dependency pairs as follows: nu(cons#(X, mark(Y))) = mark(Y) |> Y = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = active(Y) |> Y = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_8, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(adx#) = 1 Thus, we can orient the dependency pairs as follows: nu(adx#(mark(X))) = mark(X) |> X = nu(adx#(X)) nu(adx#(active(X))) = active(X) |> X = nu(adx#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). The formative rules of (P_1, R_0) are R_1 ::= active(zeros) => mark(cons(0, zeros)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) => mark(incr(cons(X, adx(Y)))) mark(nats) => active(nats) mark(adx(X)) => active(adx(mark(X))) mark(zeros) => active(zeros) mark(cons(X, Y)) => active(cons(X, Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(s(X)) => active(s(X)) mark(hd(X)) => active(hd(mark(X))) mark(tl(X)) => active(tl(mark(X))) adx(mark(X)) => adx(X) adx(active(X)) => adx(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) hd(mark(X)) => hd(X) hd(active(X)) => hd(X) tl(mark(X)) => tl(X) tl(active(X)) => tl(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative). Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, 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: active#(adx(cons(X, Y))) >? mark#(incr(cons(X, adx(Y)))) mark#(adx(X)) >? active#(adx(mark(X))) mark#(adx(X)) >? mark#(X) mark#(incr(X)) >? mark#(X) mark#(hd(X)) >? mark#(X) mark#(tl(X)) >? mark#(X) active(zeros) >= mark(cons(0, zeros)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) >= mark(incr(cons(X, adx(Y)))) mark(nats) >= active(nats) mark(adx(X)) >= active(adx(mark(X))) mark(zeros) >= active(zeros) mark(cons(X, Y)) >= active(cons(X, Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(s(X)) >= active(s(X)) mark(hd(X)) >= active(hd(mark(X))) mark(tl(X)) >= active(tl(mark(X))) adx(mark(X)) >= adx(X) adx(active(X)) >= adx(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) incr(mark(X)) >= incr(X) incr(active(X)) >= incr(X) hd(mark(X)) >= hd(X) hd(active(X)) >= hd(X) tl(mark(X)) >= tl(X) tl(active(X)) >= tl(X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: active#(x_1) = active#() cons(x_1,x_2) = cons(x_1) This leaves the following ordering requirements: active#(adx(cons(X, Y))) > mark#(incr(cons(X, adx(Y)))) mark#(adx(X)) >= active#(adx(mark(X))) mark#(adx(X)) >= mark#(X) mark#(incr(X)) >= mark#(X) mark#(hd(X)) >= mark#(X) mark#(tl(X)) >= mark#(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) incr(mark(X)) >= incr(X) incr(active(X)) >= incr(X) The following interpretation satisfies the requirements: 0 = 0 active = \y0.2y0 active# = \y0.1 adx = \y0.1 + y0 cons = \y0y1.0 hd = \y0.2y0 incr = \y0.y0 mark = \y0.y0 mark# = \y0.2y0 nats = 0 s = \y0.0 tl = \y0.y0 zeros = 0 Using this interpretation, the requirements translate to: [[active#(adx(cons(_x0, _x1)))]] = 1 > 0 = [[mark#(incr(cons(_x0, adx(_x1))))]] [[mark#(adx(_x0))]] = 2 + 2x0 > 1 = [[active#(adx(mark(_x0)))]] [[mark#(adx(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(incr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(hd(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(tl(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[cons(mark(_x0), _x1)]] = 0 >= 0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = 0 >= 0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = 0 >= 0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = 0 >= 0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = 2x0 >= x0 = [[incr(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_1, minimal, formative) by (P_9, R_1, minimal, formative), where P_9 consists of: mark#(incr(X)) =#> mark#(X) mark#(hd(X)) =#> mark#(X) mark#(tl(X)) =#> mark#(X) Thus, the original system is terminating if (P_9, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_1, minimal, formative). We apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(incr(X))) = incr(X) |> X = nu(mark#(X)) nu(mark#(hd(X))) = hd(X) |> X = nu(mark#(X)) nu(mark#(tl(X))) = tl(X) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_9, R_1, minimal, f) by ({}, R_1, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 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.