0.00/0.07 YES 0.00/0.07 We consider the system theBenchmark. 0.00/0.07 0.00/0.07 Alphabet: 0.00/0.07 0.00/0.07 A : [term * term] --> term 0.00/0.07 L : [term -> term] --> term 0.00/0.07 V : [term] --> term 0.00/0.07 noabs : [term] --> term 0.00/0.07 0.00/0.07 Rules: 0.00/0.07 0.00/0.07 noabs(A(x, y)) => A(noabs(x), noabs(y)) 0.00/0.07 noabs(V(x)) => V(x) 0.00/0.07 A(L(f), x) => f noabs(x) 0.00/0.07 0.00/0.07 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.07 0.00/0.07 We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. 0.00/0.07 0.00/0.07 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.07 0.00/0.07 Dependency Pairs P_0: 0.00/0.07 0.00/0.07 0] noabs#(A(X, Y)) =#> A#(noabs(X), noabs(Y)) 0.00/0.07 1] noabs#(A(X, Y)) =#> noabs#(X) 0.00/0.07 2] noabs#(A(X, Y)) =#> noabs#(Y) 0.00/0.07 3] A#(L(F), X) =#> F(noabs(X)) 0.00/0.07 4] A#(L(F), X) =#> noabs#(X) 0.00/0.07 0.00/0.07 Rules R_0: 0.00/0.07 0.00/0.07 noabs(A(X, Y)) => A(noabs(X), noabs(Y)) 0.00/0.07 noabs(V(X)) => V(X) 0.00/0.07 A(L(F), X) => F noabs(X) 0.00/0.07 0.00/0.07 Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. 0.00/0.07 0.00/0.07 We consider the dependency pair problem (P_0, R_0, minimal, formative). 0.00/0.07 0.00/0.07 The formative rules of (P_0, R_0) are R_1 ::= 0.00/0.07 0.00/0.07 noabs(A(X, Y)) => A(noabs(X), noabs(Y)) 0.00/0.07 A(L(F), X) => F noabs(X) 0.00/0.07 0.00/0.07 By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_0, R_0, minimal, formative) by (P_0, R_1, minimal, formative). 0.00/0.07 0.00/0.07 Thus, the original system is terminating if (P_0, R_1, minimal, formative) is finite. 0.00/0.07 0.00/0.07 We consider the dependency pair problem (P_0, R_1, minimal, formative). 0.00/0.07 0.00/0.07 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.07 0.00/0.07 noabs#(A(X, Y)) >? A#(noabs(X), noabs(Y)) 0.00/0.07 noabs#(A(X, Y)) >? noabs#(X) 0.00/0.07 noabs#(A(X, Y)) >? noabs#(Y) 0.00/0.07 A#(L(F), X) >? F(noabs(X)) 0.00/0.07 A#(L(F), X) >? noabs#(X) 0.00/0.07 noabs(A(X, Y)) >= A(noabs(X), noabs(Y)) 0.00/0.07 A(L(F), X) >= F noabs(X) 0.00/0.07 0.00/0.07 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.07 0.00/0.07 The following interpretation satisfies the requirements: 0.00/0.07 0.00/0.07 A = \y0y1.3y0 0.00/0.07 A# = \y0y1.2y0 + 2y1 0.00/0.07 L = \G0.3 + G0(0) 0.00/0.07 noabs = \y0.0 0.00/0.07 noabs# = \y0.2 0.00/0.07 0.00/0.07 Using this interpretation, the requirements translate to: 0.00/0.07 0.00/0.07 [[noabs#(A(_x0, _x1))]] = 2 > 0 = [[A#(noabs(_x0), noabs(_x1))]] 0.00/0.07 [[noabs#(A(_x0, _x1))]] = 2 >= 2 = [[noabs#(_x0)]] 0.00/0.07 [[noabs#(A(_x0, _x1))]] = 2 >= 2 = [[noabs#(_x1)]] 0.00/0.07 [[A#(L(_F0), _x1)]] = 6 + 2x1 + 2F0(0) > F0(0) = [[_F0(noabs(_x1))]] 0.00/0.07 [[A#(L(_F0), _x1)]] = 6 + 2x1 + 2F0(0) > 2 = [[noabs#(_x1)]] 0.00/0.07 [[noabs(A(_x0, _x1))]] = 0 >= 0 = [[A(noabs(_x0), noabs(_x1))]] 0.00/0.07 [[A(L(_F0), _x1)]] = 9 + 3F0(0) >= F0(0) = [[_F0 noabs(_x1)]] 0.00/0.07 0.00/0.07 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_0, R_1, minimal, formative) by (P_1, R_1, minimal, formative), where P_1 consists of: 0.00/0.07 0.00/0.07 noabs#(A(X, Y)) =#> noabs#(X) 0.00/0.07 noabs#(A(X, Y)) =#> noabs#(Y) 0.00/0.07 0.00/0.07 Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. 0.00/0.07 0.00/0.07 We consider the dependency pair problem (P_1, R_1, minimal, formative). 0.00/0.07 0.00/0.07 We apply the subterm criterion with the following projection function: 0.00/0.07 0.00/0.07 nu(noabs#) = 1 0.00/0.07 0.00/0.07 Thus, we can orient the dependency pairs as follows: 0.00/0.07 0.00/0.07 nu(noabs#(A(X, Y))) = A(X, Y) |> X = nu(noabs#(X)) 0.00/0.07 nu(noabs#(A(X, Y))) = A(X, Y) |> Y = nu(noabs#(Y)) 0.00/0.07 0.00/0.07 By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_1, minimal, f) by ({}, R_1, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 0.00/0.07 0.00/0.07 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 0.00/0.07 0.00/0.07 0.00/0.07 +++ Citations +++ 0.00/0.07 0.00/0.07 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.07 EOF