1.65/0.92 YES 1.65/0.92 We consider the system theBenchmark. 1.65/0.92 1.65/0.92 Alphabet: 1.65/0.92 1.65/0.92 0 : [] --> nat 1.65/0.92 false : [] --> bool 1.65/0.92 h : [nat -> bool * nat -> nat * nat] --> nat 1.65/0.92 if : [bool * nat * nat] --> nat 1.65/0.92 s : [nat] --> nat 1.65/0.92 true : [] --> bool 1.65/0.92 1.65/0.92 Rules: 1.65/0.92 1.65/0.92 if(true, x, y) => x 1.65/0.92 if(false, x, y) => y 1.65/0.92 h(f, g, 0) => 0 1.65/0.92 h(f, g, s(x)) => g h(f, g, if(f x, x, 0)) 1.65/0.92 1.65/0.92 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 1.65/0.92 1.65/0.92 We observe that the rules contain a first-order subset: 1.65/0.92 1.65/0.92 if(true, X, Y) => X 1.65/0.92 if(false, X, Y) => Y 1.65/0.92 1.65/0.92 Moreover, the system is orthogonal. 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 terminating when seen as a many-sorted first-order TRS. 1.65/0.92 1.65/0.92 According to the external first-order termination prover, this system is indeed terminating: 1.65/0.92 1.65/0.92 || proof of resources/system.trs 1.65/0.92 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616 1.65/0.92 || 1.65/0.92 || 1.65/0.92 || Termination w.r.t. Q of the given QTRS could be proven: 1.65/0.92 || 1.65/0.92 || (0) QTRS 1.65/0.92 || (1) QTRSRRRProof [EQUIVALENT] 1.65/0.92 || (2) QTRS 1.65/0.92 || (3) RisEmptyProof [EQUIVALENT] 1.65/0.92 || (4) YES 1.65/0.92 || 1.65/0.92 || 1.65/0.92 || ---------------------------------------- 1.65/0.92 || 1.65/0.92 || (0) 1.65/0.92 || Obligation: 1.65/0.92 || Q restricted rewrite system: 1.65/0.92 || The TRS R consists of the following rules: 1.65/0.92 || 1.65/0.92 || if(true, %X, %Y) -> %X 1.65/0.92 || if(false, %X, %Y) -> %Y 1.65/0.92 || 1.65/0.92 || Q is empty. 1.65/0.92 || 1.65/0.92 || ---------------------------------------- 1.65/0.92 || 1.65/0.92 || (1) QTRSRRRProof (EQUIVALENT) 1.65/0.92 || Used ordering: 1.65/0.92 || Polynomial interpretation [POLO]: 1.65/0.92 || 1.65/0.92 || POL(false) = 2 1.65/0.92 || POL(if(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + x_3 1.65/0.92 || POL(true) = 2 1.65/0.92 || With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 1.65/0.92 || 1.65/0.92 || if(true, %X, %Y) -> %X 1.65/0.92 || if(false, %X, %Y) -> %Y 1.65/0.92 || 1.65/0.92 || 1.65/0.92 || 1.65/0.92 || 1.65/0.92 || ---------------------------------------- 1.65/0.92 || 1.65/0.92 || (2) 1.65/0.92 || Obligation: 1.65/0.92 || Q restricted rewrite system: 1.65/0.92 || R is empty. 1.65/0.92 || Q is empty. 1.65/0.93 || 1.65/0.93 || ---------------------------------------- 1.65/0.93 || 1.65/0.93 || (3) RisEmptyProof (EQUIVALENT) 1.65/0.93 || The TRS R is empty. Hence, termination is trivially proven. 1.65/0.93 || ---------------------------------------- 1.65/0.93 || 1.65/0.93 || (4) 1.65/0.93 || YES 1.65/0.93 || 1.65/0.93 We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs and accessible arguments in [Kop13]). 1.65/0.93 1.65/0.93 We thus obtain the following dependency pair problem (P_0, R_0, static, formative): 1.65/0.93 1.65/0.93 Dependency Pairs P_0: 1.65/0.93 1.65/0.93 0] h#(F, G, s(X)) =#> h#(F, G, if(F X, X, 0)) 1.65/0.93 1] h#(F, G, s(X)) =#> if#(F X, X, 0) 1.65/0.93 1.65/0.93 Rules R_0: 1.65/0.93 1.65/0.93 if(true, X, Y) => X 1.65/0.93 if(false, X, Y) => Y 1.65/0.93 h(F, G, 0) => 0 1.65/0.93 h(F, G, s(X)) => G h(F, G, if(F X, X, 0)) 1.65/0.93 1.65/0.93 Thus, the original system is terminating if (P_0, R_0, static, formative) is finite. 1.65/0.93 1.65/0.93 We consider the dependency pair problem (P_0, R_0, static, formative). 1.65/0.93 1.65/0.93 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 1.65/0.93 1.65/0.93 * 0 : 0, 1 1.65/0.93 * 1 : 1.65/0.93 1.65/0.93 This graph has the following strongly connected components: 1.65/0.93 1.65/0.93 P_1: 1.65/0.93 1.65/0.93 h#(F, G, s(X)) =#> h#(F, G, if(F X, X, 0)) 1.65/0.93 1.65/0.93 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). 1.65/0.93 1.65/0.93 Thus, the original system is terminating if (P_1, R_0, static, formative) is finite. 1.65/0.93 1.65/0.93 We consider the dependency pair problem (P_1, R_0, static, formative). 1.65/0.93 1.65/0.93 The formative rules of (P_1, R_0) are R_1 ::= 1.65/0.93 1.65/0.93 if(true, X, Y) => X 1.65/0.93 if(false, X, Y) => Y 1.65/0.93 h(F, G, s(X)) => G h(F, G, if(F X, X, 0)) 1.65/0.93 1.65/0.93 By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, static, formative) by (P_1, R_1, static, formative). 1.65/0.93 1.65/0.93 Thus, the original system is terminating if (P_1, R_1, static, formative) is finite. 1.65/0.93 1.65/0.93 We consider the dependency pair problem (P_1, R_1, static, formative). 1.65/0.93 1.65/0.93 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: 1.65/0.93 1.65/0.93 h#(F, G, s(X)) >? h#(F, G, if(F X, X, 0)) 1.65/0.93 if(true, X, Y) >= X 1.65/0.93 if(false, X, Y) >= Y 1.65/0.93 h(F, G, s(X)) >= G h(F, G, if(F X, X, 0)) 1.65/0.93 1.65/0.93 Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) 1.65/0.93 1.65/0.93 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.65/0.93 1.65/0.93 Argument functions: 1.65/0.93 1.65/0.93 [[0]] = _|_ 1.65/0.93 [[if(x_1, x_2, x_3)]] = if(x_2, x_3) 1.65/0.93 1.65/0.93 We choose Lex = {} and Mul = {@_{o -> o}, false, h, h#, if, s, true}, and the following precedence: h > @_{o -> o} > h# > s > if > true > false 1.65/0.93 1.65/0.93 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 1.65/0.93 1.65/0.93 h#(F, G, s(X)) > h#(F, G, if(X, _|_)) 1.65/0.93 if(X, Y) >= X 1.65/0.93 if(X, Y) >= Y 1.65/0.93 h(F, G, s(X)) >= @_{o -> o}(G, h(F, G, if(X, _|_))) 1.65/0.93 1.65/0.93 With these choices, we have: 1.65/0.93 1.65/0.93 1] h#(F, G, s(X)) > h#(F, G, if(X, _|_)) because [2], by definition 1.65/0.93 2] h#*(F, G, s(X)) >= h#(F, G, if(X, _|_)) because h# in Mul, [3], [4] and [5], by (Stat) 1.65/0.93 3] F >= F by (Meta) 1.65/0.93 4] G >= G by (Meta) 1.65/0.93 5] s(X) > if(X, _|_) because [6], by definition 1.65/0.93 6] s*(X) >= if(X, _|_) because s > if, [7] and [9], by (Copy) 1.65/0.93 7] s*(X) >= X because [8], by (Select) 1.65/0.93 8] X >= X by (Meta) 1.65/0.93 9] s*(X) >= _|_ by (Bot) 1.65/0.93 1.65/0.93 10] if(X, Y) >= X because [11], by (Star) 1.65/0.93 11] if*(X, Y) >= X because [12], by (Select) 1.65/0.93 12] X >= X by (Meta) 1.65/0.93 1.65/0.93 13] if(X, Y) >= Y because [14], by (Star) 1.65/0.93 14] if*(X, Y) >= Y because [15], by (Select) 1.65/0.93 15] Y >= Y by (Meta) 1.65/0.93 1.65/0.93 16] h(F, G, s(X)) >= @_{o -> o}(G, h(F, G, if(X, _|_))) because [17], by (Star) 1.65/0.93 17] h*(F, G, s(X)) >= @_{o -> o}(G, h(F, G, if(X, _|_))) because h > @_{o -> o}, [18] and [19], by (Copy) 1.65/0.93 18] h*(F, G, s(X)) >= G because [4], by (Select) 1.65/0.93 19] h*(F, G, s(X)) >= h(F, G, if(X, _|_)) because h in Mul, [3], [4] and [5], by (Stat) 1.65/0.93 1.65/0.93 By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_1, R_1) by ({}, R_1). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 1.65/0.93 1.65/0.93 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 1.65/0.93 1.65/0.93 1.65/0.93 +++ Citations +++ 1.65/0.93 1.65/0.93 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 1.65/0.93 [Kop13] C. Kop. Static Dependency Pairs with Accessibility. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/static.pdf, 2013. 1.65/0.93 [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.65/0.93 EOF