/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. !colon : [o * o] --> o !minus : [o * o] --> o !plus : [o * o] --> o !plus!plus : [o * o] --> o 0 : [] --> o avg : [o] --> o hd : [o] --> o length : [o] --> o nil : [] --> o quot : [o * o] --> o s : [o] --> o sum : [o] --> o !plus(0, X) => X !plus(s(X), Y) => s(!plus(X, Y)) !plus!plus(nil, X) => X !plus!plus(!colon(X, Y), Z) => !colon(X, !plus!plus(Y, Z)) sum(!colon(X, nil)) => !colon(X, nil) sum(!colon(X, !colon(Y, Z))) => sum(!colon(!plus(X, Y), Z)) sum(!plus!plus(X, !colon(Y, !colon(Z, U)))) => sum(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) !minus(X, 0) => X !minus(0, s(X)) => 0 !minus(s(X), s(Y)) => !minus(X, Y) quot(0, s(X)) => 0 quot(s(X), s(Y)) => s(quot(!minus(X, Y), s(Y))) length(nil) => 0 length(!colon(X, Y)) => s(length(Y)) hd(!colon(X, Y)) => X avg(X) => quot(hd(sum(X)), length(X)) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] !plus#(s(X), Y) =#> !plus#(X, Y) 1] !plus!plus#(!colon(X, Y), Z) =#> !plus!plus#(Y, Z) 2] sum#(!colon(X, !colon(Y, Z))) =#> sum#(!colon(!plus(X, Y), Z)) 3] sum#(!colon(X, !colon(Y, Z))) =#> !plus#(X, Y) 4] sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) =#> sum#(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) 5] sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) =#> !plus!plus#(X, sum(!colon(Y, !colon(Z, U)))) 6] sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) =#> sum#(!colon(Y, !colon(Z, U))) 7] !minus#(s(X), s(Y)) =#> !minus#(X, Y) 8] quot#(s(X), s(Y)) =#> quot#(!minus(X, Y), s(Y)) 9] quot#(s(X), s(Y)) =#> !minus#(X, Y) 10] length#(!colon(X, Y)) =#> length#(Y) 11] avg#(X) =#> quot#(hd(sum(X)), length(X)) 12] avg#(X) =#> hd#(sum(X)) 13] avg#(X) =#> sum#(X) 14] avg#(X) =#> length#(X) Rules R_0: !plus(0, X) => X !plus(s(X), Y) => s(!plus(X, Y)) !plus!plus(nil, X) => X !plus!plus(!colon(X, Y), Z) => !colon(X, !plus!plus(Y, Z)) sum(!colon(X, nil)) => !colon(X, nil) sum(!colon(X, !colon(Y, Z))) => sum(!colon(!plus(X, Y), Z)) sum(!plus!plus(X, !colon(Y, !colon(Z, U)))) => sum(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) !minus(X, 0) => X !minus(0, s(X)) => 0 !minus(s(X), s(Y)) => !minus(X, Y) quot(0, s(X)) => 0 quot(s(X), s(Y)) => s(quot(!minus(X, Y), s(Y))) length(nil) => 0 length(!colon(X, Y)) => s(length(Y)) hd(!colon(X, Y)) => X avg(X) => quot(hd(sum(X)), length(X)) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0 * 1 : 1 * 2 : 2, 3 * 3 : 0 * 4 : 2, 3, 4, 5, 6 * 5 : 1 * 6 : 2, 3 * 7 : 7 * 8 : 8, 9 * 9 : 7 * 10 : 10 * 11 : 8, 9 * 12 : * 13 : 2, 3, 4, 5, 6 * 14 : 10 This graph has the following strongly connected components: P_1: !plus#(s(X), Y) =#> !plus#(X, Y) P_2: !plus!plus#(!colon(X, Y), Z) =#> !plus!plus#(Y, Z) P_3: sum#(!colon(X, !colon(Y, Z))) =#> sum#(!colon(!plus(X, Y), Z)) P_4: sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) =#> sum#(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) P_5: !minus#(s(X), s(Y)) =#> !minus#(X, Y) P_6: quot#(s(X), s(Y)) =#> quot#(!minus(X, Y), s(Y)) P_7: length#(!colon(X, Y)) =#> length#(Y) 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(length#) = 1 Thus, we can orient the dependency pairs as follows: nu(length#(!colon(X, Y))) = !colon(X, Y) |> Y = nu(length#(Y)) 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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_6, R_0) are: !minus(X, 0) => X !minus(0, s(X)) => 0 !minus(s(X), s(Y)) => !minus(X, Y) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: quot#(s(X), s(Y)) >? quot#(!minus(X, Y), s(Y)) !minus(X, 0) >= X !minus(0, s(X)) >= 0 !minus(s(X), s(Y)) >= !minus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !minus = \y0y1.1 + y0 0 = 1 quot# = \y0y1.2y0 s = \y0.3 + y0 Using this interpretation, the requirements translate to: [[quot#(s(_x0), s(_x1))]] = 6 + 2x0 > 2 + 2x0 = [[quot#(!minus(_x0, _x1), s(_x1))]] [[!minus(_x0, 0)]] = 1 + x0 >= x0 = [[_x0]] [[!minus(0, s(_x0))]] = 2 >= 1 = [[0]] [[!minus(s(_x0), s(_x1))]] = 4 + x0 >= 1 + x0 = [[!minus(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_6, R_0) by ({}, R_0). 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(!minus#) = 1 Thus, we can orient the dependency pairs as follows: nu(!minus#(s(X), s(Y))) = s(X) |> X = nu(!minus#(X, Y)) 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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_4, R_0) are: !plus(0, X) => X !plus(s(X), Y) => s(!plus(X, Y)) !plus!plus(nil, X) => X !plus!plus(!colon(X, Y), Z) => !colon(X, !plus!plus(Y, Z)) sum(!colon(X, nil)) => !colon(X, nil) sum(!colon(X, !colon(Y, Z))) => sum(!colon(!plus(X, Y), Z)) sum(!plus!plus(X, !colon(Y, !colon(Z, U)))) => sum(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) >? sum#(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) !plus(0, X) >= X !plus(s(X), Y) >= s(!plus(X, Y)) !plus!plus(nil, X) >= X !plus!plus(!colon(X, Y), Z) >= !colon(X, !plus!plus(Y, Z)) sum(!colon(X, nil)) >= !colon(X, nil) sum(!colon(X, !colon(Y, Z))) >= sum(!colon(!plus(X, Y), Z)) sum(!plus!plus(X, !colon(Y, !colon(Z, U)))) >= sum(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: !colon(x_1,x_2) = !colon(x_2) This leaves the following ordering requirements: sum#(!plus!plus(X, !colon(Y, !colon(Z, U)))) > sum#(!plus!plus(X, sum(!colon(Y, !colon(Z, U))))) !plus!plus(nil, X) >= X !plus!plus(!colon(X, Y), Z) >= !colon(X, !plus!plus(Y, Z)) sum(!colon(X, nil)) >= !colon(X, nil) sum(!colon(X, !colon(Y, Z))) >= sum(!colon(!plus(X, Y), Z)) The following interpretation satisfies the requirements: !colon = \y0y1.2 + y1 !plus = \y0y1.0 !plus!plus = \y0y1.y0 + y1 0 = 0 nil = 0 s = \y0.0 sum = \y0.2 sum# = \y0.y0 Using this interpretation, the requirements translate to: [[sum#(!plus!plus(_x0, !colon(_x1, !colon(_x2, _x3))))]] = 4 + x0 + x3 > 2 + x0 = [[sum#(!plus!plus(_x0, sum(!colon(_x1, !colon(_x2, _x3)))))]] [[!plus!plus(nil, _x0)]] = x0 >= x0 = [[_x0]] [[!plus!plus(!colon(_x0, _x1), _x2)]] = 2 + x1 + x2 >= 2 + x1 + x2 = [[!colon(_x0, !plus!plus(_x1, _x2))]] [[sum(!colon(_x0, nil))]] = 2 >= 2 = [[!colon(_x0, nil)]] [[sum(!colon(_x0, !colon(_x1, _x2)))]] = 2 >= 2 = [[sum(!colon(!plus(_x0, _x1), _x2))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_4, R_0) by ({}, R_0). 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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_3, R_0) are: !plus(0, X) => X !plus(s(X), Y) => s(!plus(X, Y)) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: sum#(!colon(X, !colon(Y, Z))) >? sum#(!colon(!plus(X, Y), Z)) !plus(0, X) >= X !plus(s(X), Y) >= s(!plus(X, Y)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !colon = \y0y1.3 + 2y0 + 2y1 !plus = \y0y1.y1 0 = 0 s = \y0.0 sum# = \y0.y0 Using this interpretation, the requirements translate to: [[sum#(!colon(_x0, !colon(_x1, _x2)))]] = 9 + 2x0 + 4x1 + 4x2 > 3 + 2x1 + 2x2 = [[sum#(!colon(!plus(_x0, _x1), _x2))]] [[!plus(0, _x0)]] = x0 >= x0 = [[_x0]] [[!plus(s(_x0), _x1)]] = x1 >= 0 = [[s(!plus(_x0, _x1))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_3, R_0) by ({}, R_0). 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(!plus!plus#) = 1 Thus, we can orient the dependency pairs as follows: nu(!plus!plus#(!colon(X, Y), Z)) = !colon(X, Y) |> Y = nu(!plus!plus#(Y, Z)) 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). We apply the subterm criterion with the following projection function: nu(!plus#) = 1 Thus, we can orient the dependency pairs as follows: nu(!plus#(s(X), Y)) = s(X) |> X = nu(!plus#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by ({}, R_0, 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.