4.31/4.35 YES 4.37/4.45 We consider the system theBenchmark. 4.37/4.45 4.37/4.45 Alphabet: 4.37/4.45 4.37/4.45 !plus : [proc * proc] --> proc 4.37/4.45 !times : [proc * proc] --> proc 4.37/4.45 delta : [] --> proc 4.37/4.45 sigma : [data -> proc] --> proc 4.37/4.45 4.37/4.45 Rules: 4.37/4.45 4.37/4.45 !plus(x, x) => x 4.37/4.45 !times(!plus(x, y), z) => !plus(!times(x, z), !times(y, z)) 4.37/4.45 !times(!times(x, y), z) => !times(x, !times(y, z)) 4.37/4.45 !plus(x, delta) => x 4.37/4.45 !times(delta, x) => delta 4.37/4.45 sigma(/\x.y) => y 4.37/4.45 !plus(sigma(/\x.f x), f y) => sigma(/\z.f z) 4.37/4.45 sigma(/\x.!plus(f x, g x)) => !plus(sigma(/\y.f y), sigma(/\z.g z)) 4.37/4.45 !times(sigma(/\x.f x), y) => sigma(/\z.!times(f z, y)) 4.37/4.45 4.37/4.45 Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term. 4.37/4.45 4.37/4.45 We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0). This leads to the following AFSM: 4.37/4.45 4.37/4.45 Alphabet: 4.37/4.45 4.37/4.45 !plus : [proc * proc] --> proc 4.37/4.45 !times : [proc * proc] --> proc 4.37/4.45 delta : [] --> proc 4.37/4.45 sigma : [data -> proc] --> proc 4.37/4.45 ~AP1 : [data -> proc * data] --> proc 4.37/4.45 4.37/4.45 Rules: 4.37/4.45 4.37/4.45 !plus(X, X) => X 4.37/4.45 !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) => X 4.37/4.45 !times(delta, X) => delta 4.37/4.45 sigma(/\x.X) => X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) => F X 4.37/4.45 4.37/4.45 We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. 4.37/4.45 4.37/4.45 After applying [Kop12, Thm. 7.22] to denote collapsing dependency pairs in an extended form, we thus obtain the following dependency pair problem (P_0, R_0, minimal, all): 4.37/4.45 4.37/4.45 Dependency Pairs P_0: 4.37/4.45 4.37/4.45 0] !times#(!plus(X, Y), Z) =#> !plus#(!times(X, Z), !times(Y, Z)) 4.37/4.45 1] !times#(!plus(X, Y), Z) =#> !times#(X, Z) 4.37/4.45 2] !times#(!plus(X, Y), Z) =#> !times#(Y, Z) 4.37/4.45 3] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z)) 4.37/4.45 4] !times#(!times(X, Y), Z) =#> !times#(Y, Z) 4.37/4.45 5] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> sigma#(/\y.~AP1(F, y)) 4.37/4.45 6] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> ~AP1#(F, y) 4.37/4.45 7] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 8] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(F, y)) 4.37/4.45 9] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(F, y) 4.37/4.45 10] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(G, y)) 4.37/4.45 11] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(G, y) 4.37/4.45 12] !times#(sigma(/\x.~AP1(F, x)), X) =#> sigma#(/\y.!times(~AP1(F, y), X)) 4.37/4.45 13] !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X) 4.37/4.45 14] !times#(sigma(/\x.~AP1(F, x)), X) =#> ~AP1#(F, y) 4.37/4.45 15] ~AP1#(F, X) =#> F(X) 4.37/4.45 4.37/4.45 Rules R_0: 4.37/4.45 4.37/4.45 !plus(X, X) => X 4.37/4.45 !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) => X 4.37/4.45 !times(delta, X) => delta 4.37/4.45 sigma(/\x.X) => X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) => F X 4.37/4.45 4.37/4.45 Thus, the original system is terminating if (P_0, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_0, R_0, minimal, all). 4.37/4.45 4.37/4.45 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 4.37/4.45 4.37/4.45 * 0 : 5, 6 4.37/4.45 * 1 : 0, 1, 2, 3, 4, 12, 13, 14 4.37/4.45 * 2 : 0, 1, 2, 3, 4, 12, 13, 14 4.37/4.45 * 3 : 0, 1, 2, 3, 4, 12, 13, 14 4.37/4.45 * 4 : 0, 1, 2, 3, 4, 12, 13, 14 4.37/4.45 * 5 : 7, 8, 9, 10, 11 4.37/4.45 * 6 : 4.37/4.45 * 7 : 5, 6 4.37/4.45 * 8 : 7, 8, 9, 10, 11 4.37/4.45 * 9 : 4.37/4.45 * 10 : 7, 8, 9, 10, 11 4.37/4.45 * 11 : 4.37/4.45 * 12 : 7, 8, 9, 10, 11 4.37/4.45 * 13 : 0, 1, 2, 3, 4, 12, 13, 14 4.37/4.45 * 14 : 4.37/4.45 * 15 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 4.37/4.45 4.37/4.45 This graph has the following strongly connected components: 4.37/4.45 4.37/4.45 P_1: 4.37/4.45 4.37/4.45 !times#(!plus(X, Y), Z) =#> !times#(X, Z) 4.37/4.45 !times#(!plus(X, Y), Z) =#> !times#(Y, Z) 4.37/4.45 !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z)) 4.37/4.45 !times#(!times(X, Y), Z) =#> !times#(Y, Z) 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X) 4.37/4.45 4.37/4.45 P_2: 4.37/4.45 4.37/4.45 !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> sigma#(/\y.~AP1(F, y)) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(F, y)) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(G, y)) 4.37/4.45 4.37/4.45 P_3: 4.37/4.45 4.37/4.45 ~AP1#(F, X) =#> F(X) 4.37/4.45 4.37/4.45 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) and (P_3, R_0, m, f). 4.37/4.45 4.37/4.45 Thus, the original system is terminating if each of (P_1, R_0, minimal, all), (P_2, R_0, minimal, all) and (P_3, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_3, R_0, minimal, all). 4.37/4.45 4.37/4.45 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: 4.37/4.45 4.37/4.45 ~AP1#(F, X) >? F(X) 4.37/4.45 !plus(X, X) >= X 4.37/4.45 !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) >= X 4.37/4.45 !times(delta, X) >= delta 4.37/4.45 sigma(/\x.X) >= X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) >= F X 4.37/4.45 ~AP1(F, X) >= ~AP1#(F, X) 4.37/4.45 4.37/4.45 We apply [Kop12, Thm. 6.75] and use the following argument functions: 4.37/4.45 4.37/4.45 pi( ~AP1#(F, X) ) = #argfun-~AP1##(F X) 4.37/4.45 4.37/4.45 We orient these requirements with a polynomial interpretation in the natural numbers. 4.37/4.45 4.37/4.45 The following interpretation satisfies the requirements: 4.37/4.45 4.37/4.45 !plus = \y0y1.2 + y0 + y1 4.37/4.45 !times = \y0y1.y1 + 3y0 + 3y0y1 4.37/4.45 #argfun-~AP1## = \y0.1 + y0 4.37/4.45 delta = 0 4.37/4.45 sigma = \G0.3 + 3G0(0) 4.37/4.45 ~AP1 = \G0y1.2 + y1 + G0(y1) 4.37/4.45 ~AP1# = \G0y1.0 4.37/4.45 4.37/4.45 Using this interpretation, the requirements translate to: 4.37/4.45 4.37/4.45 [[#argfun-~AP1##(_F0 _x1)]] = 1 + max(x1, F0(x1)) > F0(x1) = [[_F0(_x1)]] 4.37/4.45 [[!plus(_x0, _x0)]] = 2 + 2x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(!plus(_x0, _x1), _x2)]] = 6 + 3x0 + 3x0x2 + 3x1 + 3x1x2 + 7x2 >= 2 + 2x2 + 3x0 + 3x0x2 + 3x1 + 3x1x2 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 4.37/4.45 [[!times(!times(_x0, _x1), _x2)]] = x2 + 3x1 + 3x1x2 + 9x0 + 9x0x1 + 9x0x1x2 + 9x0x2 >= x2 + 3x0 + 3x0x2 + 3x1 + 3x1x2 + 9x0x1 + 9x0x1x2 = [[!times(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!plus(_x0, delta)]] = 2 + x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(delta, _x0)]] = x0 >= 0 = [[delta]] 4.37/4.45 [[sigma(/\x._x0)]] = 3 + 3x0 >= x0 = [[_x0]] 4.37/4.45 [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 13 + x1 + F0(x1) + 3F0(0) >= 9 + 3F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 21 + 3F0(0) + 3F1(0) >= 20 + 3F0(0) + 3F1(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 27 + 28x1 + 9x1F0(0) + 9F0(0) >= 21 + 21x1 + 9x1F0(0) + 9F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 4.37/4.45 [[~AP1(_F0, _x1)]] = 2 + x1 + F0(x1) >= max(x1, F0(x1)) = [[_F0 _x1]] 4.37/4.45 [[~AP1(_F0, _x1)]] = 2 + x1 + F0(x1) >= 1 + max(x1, F0(x1)) = [[#argfun-~AP1##(_F0 _x1)]] 4.37/4.45 4.37/4.45 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. 4.37/4.45 4.37/4.45 Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_2, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_2, R_0, minimal, all). 4.37/4.45 4.37/4.45 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: 4.37/4.45 4.37/4.45 !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >? sigma#(/\y.~AP1(F, y)) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? sigma#(/\y.~AP1(F, y)) 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? sigma#(/\y.~AP1(G, y)) 4.37/4.45 !plus(X, X) >= X 4.37/4.45 !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) >= X 4.37/4.45 !times(delta, X) >= delta 4.37/4.45 sigma(/\x.X) >= X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) >= F X 4.37/4.45 4.37/4.45 We orient these requirements with a polynomial interpretation in the natural numbers. 4.37/4.45 4.37/4.45 The following interpretation satisfies the requirements: 4.37/4.45 4.37/4.45 !plus = \y0y1.1 + y0 + y1 4.37/4.45 !plus# = \y0y1.1 + y1 4.37/4.45 !times = \y0y1.2y0 4.37/4.45 delta = 0 4.37/4.45 sigma = \G0.G0(0) 4.37/4.45 sigma# = \G0.G0(0) 4.37/4.45 ~AP1 = \G0y1.G0(y1) 4.37/4.45 4.37/4.45 Using this interpretation, the requirements translate to: 4.37/4.45 4.37/4.45 [[!plus#(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 1 + F0(x1) > F0(0) = [[sigma#(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) >= 1 + F1(0) = [[!plus#(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) > F0(0) = [[sigma#(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) > F1(0) = [[sigma#(/\x.~AP1(_F1, x))]] 4.37/4.45 [[!plus(_x0, _x0)]] = 1 + 2x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(!plus(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 4.37/4.45 [[!times(!times(_x0, _x1), _x2)]] = 4x0 >= 2x0 = [[!times(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!plus(_x0, delta)]] = 1 + x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(delta, _x0)]] = 0 >= 0 = [[delta]] 4.37/4.45 [[sigma(/\x._x0)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 1 + F0(0) + F0(x1) >= F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) >= 1 + F0(0) + F1(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2F0(0) >= 2F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 4.37/4.45 [[~AP1(_F0, _x1)]] = F0(x1) >= F0(x1) = [[_F0 _x1]] 4.37/4.45 4.37/4.45 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_0, minimal, all) by (P_4, R_0, minimal, all), where P_4 consists of: 4.37/4.45 4.37/4.45 sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 4.37/4.45 Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_4, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_4, R_0, minimal, all). 4.37/4.45 4.37/4.45 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 4.37/4.45 4.37/4.45 * 0 : 4.37/4.45 4.37/4.45 This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. 4.37/4.45 4.37/4.45 Thus, the original system is terminating if (P_1, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_1, R_0, minimal, all). 4.37/4.45 4.37/4.45 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: 4.37/4.45 4.37/4.45 !times#(!plus(X, Y), Z) >? !times#(X, Z) 4.37/4.45 !times#(!plus(X, Y), Z) >? !times#(Y, Z) 4.37/4.45 !times#(!times(X, Y), Z) >? !times#(X, !times(Y, Z)) 4.37/4.45 !times#(!times(X, Y), Z) >? !times#(Y, Z) 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) >? !times#(~AP1(F, ~c0), X) 4.37/4.45 !plus(X, X) >= X 4.37/4.45 !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) >= X 4.37/4.45 !times(delta, X) >= delta 4.37/4.45 sigma(/\x.X) >= X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) >= F X 4.37/4.45 4.37/4.45 We orient these requirements with a polynomial interpretation in the natural numbers. 4.37/4.45 4.37/4.45 The following interpretation satisfies the requirements: 4.37/4.45 4.37/4.45 !plus = \y0y1.2 + y1 + 2y0 4.37/4.45 !times = \y0y1.y0 + y1 + 2y0y1 4.37/4.45 !times# = \y0y1.2y0 4.37/4.45 delta = 0 4.37/4.45 sigma = \G0.G0(0) 4.37/4.45 ~AP1 = \G0y1.G0(y1) 4.37/4.45 ~c0 = 0 4.37/4.45 4.37/4.45 Using this interpretation, the requirements translate to: 4.37/4.45 4.37/4.45 [[!times#(!plus(_x0, _x1), _x2)]] = 4 + 2x1 + 4x0 > 2x0 = [[!times#(_x0, _x2)]] 4.37/4.45 [[!times#(!plus(_x0, _x1), _x2)]] = 4 + 2x1 + 4x0 > 2x1 = [[!times#(_x1, _x2)]] 4.37/4.45 [[!times#(!times(_x0, _x1), _x2)]] = 2x0 + 2x1 + 4x0x1 >= 2x0 = [[!times#(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!times#(!times(_x0, _x1), _x2)]] = 2x0 + 2x1 + 4x0x1 >= 2x1 = [[!times#(_x1, _x2)]] 4.37/4.45 [[!times#(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2F0(0) >= 2F0(0) = [[!times#(~AP1(_F0, ~c0), _x1)]] 4.37/4.45 [[!plus(_x0, _x0)]] = 2 + 3x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(!plus(_x0, _x1), _x2)]] = 2 + x1 + 2x0 + 2x1x2 + 4x0x2 + 5x2 >= 2 + x1 + 2x0 + 2x1x2 + 3x2 + 4x0x2 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 4.37/4.45 [[!times(!times(_x0, _x1), _x2)]] = x0 + x1 + x2 + 2x0x1 + 2x0x2 + 2x1x2 + 4x0x1x2 >= x0 + x1 + x2 + 2x0x1 + 2x0x2 + 2x1x2 + 4x0x1x2 = [[!times(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!plus(_x0, delta)]] = 2 + 2x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(delta, _x0)]] = x0 >= 0 = [[delta]] 4.37/4.45 [[sigma(/\x._x0)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 2 + F0(x1) + 2F0(0) >= F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 2 + F1(0) + 2F0(0) >= 2 + F1(0) + 2F0(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = x1 + F0(0) + 2x1F0(0) >= x1 + F0(0) + 2x1F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 4.37/4.45 [[~AP1(_F0, _x1)]] = F0(x1) >= F0(x1) = [[_F0 _x1]] 4.37/4.45 4.37/4.45 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, all) by (P_5, R_0, minimal, all), where P_5 consists of: 4.37/4.45 4.37/4.45 !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z)) 4.37/4.45 !times#(!times(X, Y), Z) =#> !times#(Y, Z) 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X) 4.37/4.45 4.37/4.45 Thus, the original system is terminating if (P_5, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_5, R_0, minimal, all). 4.37/4.45 4.37/4.45 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: 4.37/4.45 4.37/4.45 !times#(!times(X, Y), Z) >? !times#(X, !times(Y, Z)) 4.37/4.45 !times#(!times(X, Y), Z) >? !times#(Y, Z) 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) >? !times#(~AP1(F, ~c0), X) 4.37/4.45 !plus(X, X) >= X 4.37/4.45 !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) >= X 4.37/4.45 !times(delta, X) >= delta 4.37/4.45 sigma(/\x.X) >= X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) >= F X 4.37/4.45 4.37/4.45 We orient these requirements with a polynomial interpretation in the natural numbers. 4.37/4.45 4.37/4.45 The following interpretation satisfies the requirements: 4.37/4.45 4.37/4.45 !plus = \y0y1.y0 4.37/4.45 !times = \y0y1.1 + y0 + y1 4.37/4.45 !times# = \y0y1.y0 4.37/4.45 delta = 1 4.37/4.45 sigma = \G0.G0(0) 4.37/4.45 ~AP1 = \G0y1.1 + G0(y1) 4.37/4.45 ~c0 = 0 4.37/4.45 4.37/4.45 Using this interpretation, the requirements translate to: 4.37/4.45 4.37/4.45 [[!times#(!times(_x0, _x1), _x2)]] = 1 + x0 + x1 > x0 = [[!times#(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!times#(!times(_x0, _x1), _x2)]] = 1 + x0 + x1 > x1 = [[!times#(_x1, _x2)]] 4.37/4.45 [[!times#(sigma(/\x.~AP1(_F0, x)), _x1)]] = 1 + F0(0) >= 1 + F0(0) = [[!times#(~AP1(_F0, ~c0), _x1)]] 4.37/4.45 [[!plus(_x0, _x0)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(!plus(_x0, _x1), _x2)]] = 1 + x0 + x2 >= 1 + x0 + x2 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 4.37/4.45 [[!times(!times(_x0, _x1), _x2)]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[!times(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!plus(_x0, delta)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(delta, _x0)]] = 2 + x0 >= 1 = [[delta]] 4.37/4.45 [[sigma(/\x._x0)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 1 + F0(0) >= 1 + F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) >= 1 + F0(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2 + x1 + F0(0) >= 2 + x1 + F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 4.37/4.45 [[~AP1(_F0, _x1)]] = 1 + F0(x1) >= F0(x1) = [[_F0 _x1]] 4.37/4.45 4.37/4.45 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_5, R_0, minimal, all) by (P_6, R_0, minimal, all), where P_6 consists of: 4.37/4.45 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X) 4.37/4.45 4.37/4.45 Thus, the original system is terminating if (P_6, R_0, minimal, all) is finite. 4.37/4.45 4.37/4.45 We consider the dependency pair problem (P_6, R_0, minimal, all). 4.37/4.45 4.37/4.45 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: 4.37/4.45 4.37/4.45 !times#(sigma(/\x.~AP1(F, x)), X) >? !times#(~AP1(F, ~c0), X) 4.37/4.45 !plus(X, X) >= X 4.37/4.45 !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 4.37/4.45 !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 4.37/4.45 !plus(X, delta) >= X 4.37/4.45 !times(delta, X) >= delta 4.37/4.45 sigma(/\x.X) >= X 4.37/4.45 !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 4.37/4.45 sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 4.37/4.45 !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 4.37/4.45 ~AP1(F, X) >= F X 4.37/4.45 4.37/4.45 We orient these requirements with a polynomial interpretation in the natural numbers. 4.37/4.45 4.37/4.45 The following interpretation satisfies the requirements: 4.37/4.45 4.37/4.45 !plus = \y0y1.y0 4.37/4.45 !times = \y0y1.3y0 4.37/4.45 !times# = \y0y1.y0 4.37/4.45 delta = 0 4.37/4.45 sigma = \G0.3 + G0(0) 4.37/4.45 ~AP1 = \G0y1.G0(y1) 4.37/4.45 ~c0 = 0 4.37/4.45 4.37/4.45 Using this interpretation, the requirements translate to: 4.37/4.45 4.37/4.45 [[!times#(sigma(/\x.~AP1(_F0, x)), _x1)]] = 3 + F0(0) > F0(0) = [[!times#(~AP1(_F0, ~c0), _x1)]] 4.37/4.45 [[!plus(_x0, _x0)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(!plus(_x0, _x1), _x2)]] = 3x0 >= 3x0 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 4.37/4.45 [[!times(!times(_x0, _x1), _x2)]] = 9x0 >= 3x0 = [[!times(_x0, !times(_x1, _x2))]] 4.37/4.45 [[!plus(_x0, delta)]] = x0 >= x0 = [[_x0]] 4.37/4.45 [[!times(delta, _x0)]] = 0 >= 0 = [[delta]] 4.37/4.45 [[sigma(/\x._x0)]] = 3 + x0 >= x0 = [[_x0]] 4.37/4.45 [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 3 + F0(0) >= 3 + F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 4.37/4.45 [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 3 + F0(0) >= 3 + F0(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 4.37/4.45 [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 9 + 3F0(0) >= 3 + 3F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 4.37/4.45 [[~AP1(_F0, _x1)]] = F0(x1) >= F0(x1) = [[_F0 _x1]] 4.37/4.45 4.37/4.45 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. 4.37/4.45 4.37/4.45 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 4.37/4.45 4.37/4.45 4.37/4.45 +++ Citations +++ 4.37/4.45 4.37/4.45 [Kop11] C. Kop. Simplifying Algebraic Functional Systems. In Proceedings of CAI 2011, volume 6742 of LNCS. 201--215, Springer, 2011. 4.37/4.45 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 4.44/4.46 EOF