1.41/0.63 YES 1.41/0.63 We consider the system theBenchmark. 1.41/0.63 1.41/0.63 Alphabet: 1.41/0.63 1.41/0.63 0 : [] --> o 1.41/0.63 a : [] --> o 1.41/0.63 f : [o -> o] --> o 1.41/0.63 g : [o] --> o 1.41/0.63 h : [o * o] --> o 1.41/0.63 s : [o] --> o 1.41/0.63 1.41/0.63 Rules: 1.41/0.63 1.41/0.63 a => f(/\x.g(x)) 1.41/0.63 f(/\x.y) => a 1.41/0.63 g(x) => h(x, x) 1.41/0.63 h(0, x) => x 1.41/0.63 h(s(x), 0) => g(x) 1.41/0.63 1.41/0.63 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 1.41/0.63 1.41/0.63 We use rule removal, following [Kop12, Theorem 2.23]. 1.41/0.63 1.41/0.63 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.41/0.63 1.41/0.63 a >? f(/\x.g(x)) 1.41/0.63 f(/\x.X) >? a 1.41/0.63 g(X) >? h(X, X) 1.41/0.63 h(0, X) >? X 1.41/0.63 h(s(X), 0) >? g(X) 1.41/0.63 1.41/0.63 We orient these requirements with a polynomial interpretation in the natural numbers. 1.41/0.63 1.41/0.63 The following interpretation satisfies the requirements: 1.41/0.63 1.41/0.63 0 = 3 1.41/0.63 a = 0 1.41/0.63 f = \G0.G0(0) 1.41/0.63 g = \y0.3y0 1.41/0.63 h = \y0y1.y0 + 2y1 1.41/0.63 s = \y0.3 + 3y0 1.41/0.63 1.41/0.63 Using this interpretation, the requirements translate to: 1.41/0.63 1.41/0.63 [[a]] = 0 >= 0 = [[f(/\x.g(x))]] 1.41/0.63 [[f(/\x._x0)]] = x0 >= 0 = [[a]] 1.41/0.63 [[g(_x0)]] = 3x0 >= 3x0 = [[h(_x0, _x0)]] 1.41/0.63 [[h(0, _x0)]] = 3 + 2x0 > x0 = [[_x0]] 1.41/0.63 [[h(s(_x0), 0)]] = 9 + 3x0 > 3x0 = [[g(_x0)]] 1.41/0.63 1.41/0.63 We can thus remove the following rules: 1.41/0.63 1.41/0.63 h(0, X) => X 1.41/0.63 h(s(X), 0) => g(X) 1.41/0.63 1.41/0.63 We observe that the rules contain a first-order subset: 1.41/0.63 1.41/0.63 g(X) => h(X, X) 1.41/0.63 1.41/0.63 Moreover, the system is finitely branching. Thus, by [Kop12, Thm. 7.55], we may omit all first-order dependency pairs from the dependency pair problem (DP(R), R) if this first-order part is Ce-terminating when seen as a many-sorted first-order TRS. 1.41/0.63 1.41/0.63 According to the external first-order termination prover, this system is indeed Ce-terminating: 1.41/0.63 1.41/0.63 || proof of resources/system.trs 1.41/0.63 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616 1.41/0.63 || 1.41/0.63 || 1.41/0.63 || Termination w.r.t. Q of the given QTRS could be proven: 1.41/0.63 || 1.41/0.63 || (0) QTRS 1.41/0.63 || (1) QTRSRRRProof [EQUIVALENT] 1.41/0.63 || (2) QTRS 1.41/0.63 || (3) RisEmptyProof [EQUIVALENT] 1.41/0.63 || (4) YES 1.41/0.63 || 1.41/0.63 || 1.41/0.63 || ---------------------------------------- 1.41/0.63 || 1.41/0.63 || (0) 1.41/0.63 || Obligation: 1.41/0.63 || Q restricted rewrite system: 1.41/0.63 || The TRS R consists of the following rules: 1.41/0.63 || 1.41/0.63 || g(%X) -> h(%X, %X) 1.41/0.63 || ~PAIR(%X, %Y) -> %X 1.41/0.63 || ~PAIR(%X, %Y) -> %Y 1.41/0.63 || 1.41/0.63 || Q is empty. 1.41/0.63 || 1.41/0.63 || ---------------------------------------- 1.41/0.63 || 1.41/0.63 || (1) QTRSRRRProof (EQUIVALENT) 1.41/0.63 || Used ordering: 1.41/0.63 || Polynomial interpretation [POLO]: 1.41/0.63 || 1.41/0.63 || POL(g(x_1)) = 1 + 2*x_1 1.41/0.63 || POL(h(x_1, x_2)) = x_1 + x_2 1.41/0.63 || POL(~PAIR(x_1, x_2)) = 2 + x_1 + x_2 1.41/0.63 || With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 1.41/0.63 || 1.41/0.63 || g(%X) -> h(%X, %X) 1.41/0.63 || ~PAIR(%X, %Y) -> %X 1.41/0.63 || ~PAIR(%X, %Y) -> %Y 1.41/0.63 || 1.41/0.63 || 1.41/0.63 || 1.41/0.63 || 1.41/0.63 || ---------------------------------------- 1.41/0.63 || 1.41/0.63 || (2) 1.41/0.63 || Obligation: 1.41/0.63 || Q restricted rewrite system: 1.41/0.63 || R is empty. 1.41/0.63 || Q is empty. 1.41/0.63 || 1.41/0.63 || ---------------------------------------- 1.41/0.63 || 1.41/0.63 || (3) RisEmptyProof (EQUIVALENT) 1.41/0.63 || The TRS R is empty. Hence, termination is trivially proven. 1.41/0.63 || ---------------------------------------- 1.41/0.63 || 1.41/0.63 || (4) 1.41/0.63 || YES 1.41/0.63 || 1.41/0.63 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]). 1.41/0.63 1.41/0.63 We thus obtain the following dependency pair problem (P_0, R_0, minimal, all): 1.41/0.63 1.41/0.63 Dependency Pairs P_0: 1.41/0.63 1.41/0.63 0] a# =#> f#(/\x.g(x)) 1.41/0.63 1] a# =#> g#(X) 1.41/0.63 2] f#(/\x.X) =#> a# 1.41/0.63 1.41/0.63 Rules R_0: 1.41/0.63 1.41/0.63 a => f(/\x.g(x)) 1.41/0.63 f(/\x.X) => a 1.41/0.63 g(X) => h(X, X) 1.41/0.63 1.41/0.63 Thus, the original system is terminating if (P_0, R_0, minimal, all) is finite. 1.41/0.63 1.41/0.63 We consider the dependency pair problem (P_0, R_0, minimal, all). 1.41/0.63 1.41/0.63 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 1.41/0.63 1.41/0.63 * 0 : 1.41/0.63 * 1 : 1.41/0.63 * 2 : 0, 1 1.41/0.63 1.41/0.63 This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. 1.41/0.63 1.41/0.63 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 1.41/0.63 1.41/0.63 1.41/0.63 +++ Citations +++ 1.41/0.63 1.41/0.63 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 1.41/0.63 [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. 1.41/0.63 EOF