0.00/0.15 YES 0.00/0.18 We consider the system theBenchmark. 0.00/0.18 0.00/0.18 Alphabet: 0.00/0.18 0.00/0.18 0 : [] --> nat 0.00/0.18 I : [nat] --> nat 0.00/0.18 s : [nat] --> nat 0.00/0.18 twice : [nat -> nat] --> nat -> nat 0.00/0.18 0.00/0.18 Rules: 0.00/0.18 0.00/0.18 I(0) => 0 0.00/0.18 I(s(x)) => s(twice(/\y.I(y)) x) 0.00/0.18 twice(f) => /\x.f (f x) 0.00/0.18 0.00/0.18 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.18 0.00/0.18 We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. 0.00/0.18 0.00/0.18 To start, the system is beta-saturated by adding the following rules: 0.00/0.18 0.00/0.18 twice(F) X => F (F X) 0.00/0.18 0.00/0.18 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, formative): 0.00/0.18 0.00/0.18 Dependency Pairs P_0: 0.00/0.18 0.00/0.18 0] I#(s(X)) =#> twice(/\x.I(x)) X 0.00/0.18 1] I#(s(X)) =#> twice#(/\x.I(x)) 0.00/0.18 2] I#(s(X)) =#> I#(x) 0.00/0.18 3] twice#(F) =#> F(F x) 0.00/0.18 4] twice#(F) =#> F(x) 0.00/0.18 5] twice(F) X =#> F(F X) 0.00/0.18 6] twice(F) X =#> F(X) 0.00/0.18 0.00/0.18 Rules R_0: 0.00/0.18 0.00/0.18 I(0) => 0 0.00/0.18 I(s(X)) => s(twice(/\x.I(x)) X) 0.00/0.18 twice(F) => /\x.F (F x) 0.00/0.18 twice(F) X => F (F X) 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_0, R_0, minimal, formative). 0.00/0.18 0.00/0.18 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 0.00/0.18 0.00/0.18 * 0 : 5, 6 0.00/0.18 * 1 : 3, 4 0.00/0.18 * 2 : 0.00/0.18 * 3 : 0, 1, 2, 3, 4, 5, 6 0.00/0.18 * 4 : 0, 1, 2, 3, 4, 5, 6 0.00/0.18 * 5 : 0, 1, 2, 3, 4, 5, 6 0.00/0.18 * 6 : 0, 1, 2, 3, 4, 5, 6 0.00/0.18 0.00/0.18 This graph has the following strongly connected components: 0.00/0.18 0.00/0.18 P_1: 0.00/0.18 0.00/0.18 I#(s(X)) =#> twice(/\x.I(x)) X 0.00/0.18 I#(s(X)) =#> twice#(/\x.I(x)) 0.00/0.18 twice#(F) =#> F(F x) 0.00/0.18 twice#(F) =#> F(x) 0.00/0.18 twice(F) X =#> F(F X) 0.00/0.18 twice(F) X =#> F(X) 0.00/0.18 0.00/0.18 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). 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_1, R_0, minimal, formative). 0.00/0.18 0.00/0.18 The formative rules of (P_1, R_0) are R_1 ::= 0.00/0.18 0.00/0.18 I(s(X)) => s(twice(/\x.I(x)) X) 0.00/0.18 twice(F) X => F (F X) 0.00/0.18 0.00/0.18 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). 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_1, R_1, minimal, formative). 0.00/0.18 0.00/0.18 We will use the reduction pair processor [Kop12, Thm. 7.16]. As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70]. Thus, we must orient: 0.00/0.18 0.00/0.18 I#(s(X)) >? twice(/\x.I-(x), X) 0.00/0.18 I#(s(X)) >? twice#(/\x.I-(x)) ~c0 0.00/0.18 twice#(F) X >? F(F ~c1) 0.00/0.18 twice#(F) X >? F(~c2) 0.00/0.18 twice(F, X) >? F(F X) 0.00/0.18 twice(F, X) >? F(X) 0.00/0.18 I(s(X)) >= s(twice(/\x.I-(x), X)) 0.00/0.18 twice(F, X) >= F (F X) 0.00/0.18 I-(X) >= I(X) 0.00/0.18 I-(X) >= I#(X) 0.00/0.18 0.00/0.18 We apply [Kop12, Thm. 6.75] and use the following argument functions: 0.00/0.18 0.00/0.18 pi( twice(F, X) ) = #argfun-twice#(F (F X), F X, F (F X)) 0.00/0.18 pi( twice#(F) ) = #argfun-twice##(/\x.F (F ~c1), /\y.F ~c2) 0.00/0.18 0.00/0.18 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.18 0.00/0.18 The following interpretation satisfies the requirements: 0.00/0.18 0.00/0.18 #argfun-twice# = \y0y1y2.max(y0, y1, y2) 0.00/0.18 #argfun-twice## = \G0G1y2.2 + max(G0(x0), G1(x0)) 0.00/0.18 I = \y0.y0 0.00/0.18 I- = \y0.y0 0.00/0.18 I# = \y0.y0 0.00/0.18 s = \y0.2 + 2y0 0.00/0.18 twice = \G0y1.0 0.00/0.18 twice# = \G0y1.0 0.00/0.18 ~c0 = 0 0.00/0.18 ~c1 = 0 0.00/0.18 ~c2 = 0 0.00/0.18 0.00/0.18 Using this interpretation, the requirements translate to: 0.00/0.18 0.00/0.18 [[I#(s(_x0))]] = 2 + 2x0 > max(x0, x0) = [[#argfun-twice#((/\x.I-(x)) ((/\y.I-(y)) _x0), (/\z.I-(z)) _x0, (/\u.I-(u)) ((/\v.I-(v)) _x0))]] 0.00/0.18 [[I#(s(_x0))]] = 2 + 2x0 >= 2 = [[#argfun-twice##(/\x.(/\y.I-(y)) ((/\z.I-(z)) ~c1), /\u.(/\v.I-(v)) ~c2) ~c0]] 0.00/0.18 [[#argfun-twice##(/\x._F0 (_F0 ~c1), /\y._F0 ~c2) _x1]] = max(x1, 2 + max(F0(0), F0(F0(0)))) >= F0(F0(0)) = [[_F0(_F0 ~c1)]] 0.00/0.18 [[#argfun-twice##(/\x._F0 (_F0 ~c1), /\y._F0 ~c2) _x1]] = max(x1, 2 + max(F0(0), F0(F0(0)))) >= F0(0) = [[_F0(~c2)]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) >= F0(max(x1, F0(x1))) = [[_F0(_F0 _x1)]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) >= F0(x1) = [[_F0(_x1)]] 0.00/0.18 [[I(s(_x0))]] = 2 + 2x0 >= 2 + 2max(x0, x0) = [[s(#argfun-twice#((/\x.I-(x)) ((/\y.I-(y)) _x0), (/\z.I-(z)) _x0, (/\u.I-(u)) ((/\v.I-(v)) _x0)))]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) >= max(x1, F0(x1), F0(max(x1, F0(x1)))) = [[_F0 (_F0 _x1)]] 0.00/0.18 [[I-(_x0)]] = x0 >= x0 = [[I(_x0)]] 0.00/0.18 [[I-(_x0)]] = x0 >= x0 = [[I#(_x0)]] 0.00/0.18 0.00/0.18 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_2, R_1, minimal, formative), where P_2 consists of: 0.00/0.18 0.00/0.18 I#(s(X)) =#> twice#(/\x.I(x)) 0.00/0.18 twice#(F) =#> F(F x) 0.00/0.18 twice(F) X =#> F(F X) 0.00/0.18 twice(F) X =#> F(X) 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_2, R_1, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_2, R_1, minimal, formative). 0.00/0.18 0.00/0.18 We will use the reduction pair processor [Kop12, Thm. 7.16]. As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70]. Thus, we must orient: 0.00/0.18 0.00/0.18 I#(s(X)) >? twice#(/\x.I-(x)) ~c0 0.00/0.18 twice#(F) X >? F(F ~c1) 0.00/0.18 twice(F, X) >? F(F X) 0.00/0.18 twice(F, X) >? F(X) 0.00/0.18 I(s(X)) >= s(twice(/\x.I-(x), X)) 0.00/0.18 twice(F, X) >= F (F X) 0.00/0.18 I-(X) >= I(X) 0.00/0.18 I-(X) >= I#(X) 0.00/0.18 0.00/0.18 We apply [Kop12, Thm. 6.75] and use the following argument functions: 0.00/0.18 0.00/0.18 pi( twice(F, X) ) = #argfun-twice#(F (F X), F X, F (F X)) 0.00/0.18 pi( twice#(F) ) = #argfun-twice##(/\x.F (F ~c1)) 0.00/0.18 0.00/0.18 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.18 0.00/0.18 The following interpretation satisfies the requirements: 0.00/0.18 0.00/0.18 #argfun-twice# = \y0y1y2.1 + max(y0, y1, y2) 0.00/0.18 #argfun-twice## = \G0y1.G0(x0) 0.00/0.18 I = \y0.0 0.00/0.18 I- = \y0.2y0 0.00/0.18 I# = \y0.0 0.00/0.18 s = \y0.0 0.00/0.18 twice = \G0y1.0 0.00/0.18 twice# = \G0y1.0 0.00/0.18 ~c0 = 0 0.00/0.18 ~c1 = 0 0.00/0.18 0.00/0.18 Using this interpretation, the requirements translate to: 0.00/0.18 0.00/0.18 [[I#(s(_x0))]] = 0 >= 0 = [[#argfun-twice##(/\x.(/\y.I-(y)) ((/\z.I-(z)) ~c1)) ~c0]] 0.00/0.18 [[#argfun-twice##(/\x._F0 (_F0 ~c1)) _x1]] = max(x1, F0(0), F0(F0(0))) >= F0(F0(0)) = [[_F0(_F0 ~c1)]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = 1 + max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) > F0(max(x1, F0(x1))) = [[_F0(_F0 _x1)]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = 1 + max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) > F0(x1) = [[_F0(_x1)]] 0.00/0.18 [[I(s(_x0))]] = 0 >= 0 = [[s(#argfun-twice#((/\x.I-(x)) ((/\y.I-(y)) _x0), (/\z.I-(z)) _x0, (/\u.I-(u)) ((/\v.I-(v)) _x0)))]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1), _F0 _x1, _F0 (_F0 _x1))]] = 1 + max(x1, x1, F0(x1), F0(x1), F0(max(x1, F0(x1)))) >= max(x1, F0(x1), F0(max(x1, F0(x1)))) = [[_F0 (_F0 _x1)]] 0.00/0.18 [[I-(_x0)]] = 2x0 >= 0 = [[I(_x0)]] 0.00/0.18 [[I-(_x0)]] = 2x0 >= 0 = [[I#(_x0)]] 0.00/0.18 0.00/0.18 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_1, minimal, formative) by (P_3, R_1, minimal, formative), where P_3 consists of: 0.00/0.18 0.00/0.18 I#(s(X)) =#> twice#(/\x.I(x)) 0.00/0.18 twice#(F) =#> F(F x) 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_3, R_1, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_3, R_1, minimal, formative). 0.00/0.18 0.00/0.18 We will use the reduction pair processor [Kop12, Thm. 7.16]. As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70]. Thus, we must orient: 0.00/0.18 0.00/0.18 I#(s(X)) >? twice#(/\x.I-(x)) ~c0 0.00/0.18 twice#(F) X >? F(F ~c1) 0.00/0.18 I(s(X)) >= s(twice(/\x.I-(x), X)) 0.00/0.18 twice(F, X) >= F (F X) 0.00/0.18 I-(X) >= I(X) 0.00/0.18 I-(X) >= I#(X) 0.00/0.18 0.00/0.18 We apply [Kop12, Thm. 6.75] and use the following argument functions: 0.00/0.18 0.00/0.18 pi( twice(F, X) ) = #argfun-twice#(F (F X)) 0.00/0.18 pi( twice#(F) ) = #argfun-twice##(/\x.F (F ~c1)) 0.00/0.18 0.00/0.18 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.18 0.00/0.18 The following interpretation satisfies the requirements: 0.00/0.18 0.00/0.18 #argfun-twice# = \y0.y0 0.00/0.18 #argfun-twice## = \G0y1.1 + G0(x0) 0.00/0.18 I = \y0.2y0 0.00/0.18 I- = \y0.2y0 0.00/0.18 I# = \y0.y0 0.00/0.18 s = \y0.1 0.00/0.18 twice = \G0y1.0 0.00/0.18 twice# = \G0y1.0 0.00/0.18 ~c0 = 0 0.00/0.18 ~c1 = 0 0.00/0.18 0.00/0.18 Using this interpretation, the requirements translate to: 0.00/0.18 0.00/0.18 [[I#(s(_x0))]] = 1 >= 1 = [[#argfun-twice##(/\x.(/\y.I-(y)) ((/\z.I-(z)) ~c1)) ~c0]] 0.00/0.18 [[#argfun-twice##(/\x._F0 (_F0 ~c1)) _x1]] = max(x1, 1 + max(F0(0), F0(F0(0)))) >= F0(F0(0)) = [[_F0(_F0 ~c1)]] 0.00/0.18 [[I(s(_x0))]] = 2 >= 1 = [[s(#argfun-twice#((/\x.I-(x)) ((/\y.I-(y)) _x0)))]] 0.00/0.18 [[#argfun-twice#(_F0 (_F0 _x1))]] = max(x1, F0(x1), F0(max(x1, F0(x1)))) >= max(x1, F0(x1), F0(max(x1, F0(x1)))) = [[_F0 (_F0 _x1)]] 0.00/0.18 [[I-(_x0)]] = 2x0 >= 2x0 = [[I(_x0)]] 0.00/0.18 [[I-(_x0)]] = 2x0 >= x0 = [[I#(_x0)]] 0.00/0.18 0.00/0.18 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_3, R_1, minimal, formative) by (P_4, R_1, minimal, formative), where P_4 consists of: 0.00/0.18 0.00/0.18 I#(s(X)) =#> twice#(/\x.I(x)) 0.00/0.18 0.00/0.18 Thus, the original system is terminating if (P_4, R_1, minimal, formative) is finite. 0.00/0.18 0.00/0.18 We consider the dependency pair problem (P_4, R_1, minimal, formative). 0.00/0.18 0.00/0.18 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 0.00/0.18 0.00/0.18 * 0 : 0.00/0.18 0.00/0.18 This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. 0.00/0.18 0.00/0.18 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 0.00/0.18 0.00/0.18 0.00/0.18 +++ Citations +++ 0.00/0.18 0.00/0.18 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.18 EOF