1.56/0.71 YES 1.56/0.71 We consider the system theBenchmark. 1.56/0.71 1.56/0.71 Alphabet: 1.56/0.71 1.56/0.71 0 : [] --> nat 1.56/0.71 apply : [nat * nat] --> nat 1.56/0.71 avg : [nat * nat] --> nat 1.56/0.71 check : [nat] --> nat 1.56/0.71 fun : [nat -> nat] --> nat 1.56/0.71 s : [nat] --> nat 1.56/0.71 1.56/0.71 Rules: 1.56/0.71 1.56/0.71 avg(s(x), y) => avg(x, s(y)) 1.56/0.71 avg(x, s(s(s(y)))) => s(avg(s(x), y)) 1.56/0.71 avg(0, 0) => 0 1.56/0.71 avg(0, s(0)) => 0 1.56/0.71 avg(0, s(s(0))) => s(0) 1.56/0.71 apply(fun(f), x) => f check(x) 1.56/0.71 check(s(x)) => s(check(x)) 1.56/0.71 check(0) => 0 1.56/0.71 1.56/0.71 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 1.56/0.71 1.56/0.71 We observe that the rules contain a first-order subset: 1.56/0.71 1.56/0.71 avg(s(X), Y) => avg(X, s(Y)) 1.56/0.71 avg(X, s(s(s(Y)))) => s(avg(s(X), Y)) 1.56/0.71 avg(0, 0) => 0 1.56/0.71 avg(0, s(0)) => 0 1.56/0.71 avg(0, s(s(0))) => s(0) 1.56/0.71 check(s(X)) => s(check(X)) 1.56/0.71 check(0) => 0 1.56/0.71 1.56/0.71 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.56/0.71 1.56/0.71 According to the external first-order termination prover, this system is indeed Ce-terminating: 1.56/0.71 1.56/0.71 || proof of resources/system.trs 1.56/0.71 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616 1.56/0.71 || 1.56/0.71 || 1.56/0.71 || Termination w.r.t. Q of the given QTRS could be proven: 1.56/0.71 || 1.56/0.71 || (0) QTRS 1.56/0.71 || (1) QTRSRRRProof [EQUIVALENT] 1.56/0.71 || (2) QTRS 1.56/0.71 || (3) RisEmptyProof [EQUIVALENT] 1.56/0.71 || (4) YES 1.56/0.71 || 1.56/0.71 || 1.56/0.71 || ---------------------------------------- 1.56/0.71 || 1.56/0.71 || (0) 1.56/0.71 || Obligation: 1.56/0.71 || Q restricted rewrite system: 1.56/0.71 || The TRS R consists of the following rules: 1.56/0.71 || 1.56/0.71 || avg(s(%X), %Y) -> avg(%X, s(%Y)) 1.56/0.71 || avg(%X, s(s(s(%Y)))) -> s(avg(s(%X), %Y)) 1.56/0.71 || avg(0, 0) -> 0 1.56/0.71 || avg(0, s(0)) -> 0 1.56/0.71 || avg(0, s(s(0))) -> s(0) 1.56/0.71 || check(s(%X)) -> s(check(%X)) 1.56/0.71 || check(0) -> 0 1.56/0.71 || ~PAIR(%X, %Y) -> %X 1.56/0.71 || ~PAIR(%X, %Y) -> %Y 1.56/0.71 || 1.56/0.71 || Q is empty. 1.56/0.71 || 1.56/0.71 || ---------------------------------------- 1.56/0.71 || 1.56/0.71 || (1) QTRSRRRProof (EQUIVALENT) 1.56/0.71 || Used ordering: 1.56/0.71 || Knuth-Bendix order [KBO] with precedence:check_1 > ~PAIR_2 > 0 > s_1 > avg_2 1.56/0.71 || 1.56/0.71 || and weight map: 1.56/0.71 || 1.56/0.71 || 0=1 1.56/0.71 || s_1=1 1.56/0.71 || check_1=0 1.56/0.71 || avg_2=0 1.56/0.71 || ~PAIR_2=0 1.56/0.71 || 1.56/0.71 || The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 1.56/0.71 || 1.56/0.71 || avg(s(%X), %Y) -> avg(%X, s(%Y)) 1.56/0.71 || avg(%X, s(s(s(%Y)))) -> s(avg(s(%X), %Y)) 1.56/0.71 || avg(0, 0) -> 0 1.56/0.71 || avg(0, s(0)) -> 0 1.56/0.71 || avg(0, s(s(0))) -> s(0) 1.56/0.71 || check(s(%X)) -> s(check(%X)) 1.56/0.71 || check(0) -> 0 1.56/0.71 || ~PAIR(%X, %Y) -> %X 1.56/0.71 || ~PAIR(%X, %Y) -> %Y 1.56/0.71 || 1.56/0.71 || 1.56/0.71 || 1.56/0.71 || 1.56/0.71 || ---------------------------------------- 1.56/0.71 || 1.56/0.71 || (2) 1.56/0.71 || Obligation: 1.56/0.71 || Q restricted rewrite system: 1.56/0.71 || R is empty. 1.56/0.71 || Q is empty. 1.56/0.71 || 1.56/0.71 || ---------------------------------------- 1.56/0.71 || 1.56/0.71 || (3) RisEmptyProof (EQUIVALENT) 1.56/0.71 || The TRS R is empty. Hence, termination is trivially proven. 1.56/0.71 || ---------------------------------------- 1.56/0.71 || 1.56/0.71 || (4) 1.56/0.71 || YES 1.56/0.71 || 1.56/0.71 We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. 1.56/0.71 1.56/0.71 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): 1.56/0.71 1.56/0.71 Dependency Pairs P_0: 1.56/0.71 1.56/0.71 0] apply#(fun(F), X) =#> F(check(X)) 1.56/0.71 1] apply#(fun(F), X) =#> check#(X) 1.56/0.71 1.56/0.71 Rules R_0: 1.56/0.71 1.56/0.71 avg(s(X), Y) => avg(X, s(Y)) 1.56/0.71 avg(X, s(s(s(Y)))) => s(avg(s(X), Y)) 1.56/0.71 avg(0, 0) => 0 1.56/0.71 avg(0, s(0)) => 0 1.56/0.71 avg(0, s(s(0))) => s(0) 1.56/0.71 apply(fun(F), X) => F check(X) 1.56/0.71 check(s(X)) => s(check(X)) 1.56/0.71 check(0) => 0 1.56/0.71 1.56/0.71 Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. 1.56/0.71 1.56/0.71 We consider the dependency pair problem (P_0, R_0, minimal, formative). 1.56/0.71 1.56/0.71 We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: 1.56/0.71 1.56/0.71 * 0 : 0, 1 1.56/0.71 * 1 : 1.56/0.71 1.56/0.71 This graph has the following strongly connected components: 1.56/0.71 1.56/0.71 P_1: 1.56/0.71 1.56/0.71 apply#(fun(F), X) =#> F(check(X)) 1.56/0.71 1.56/0.71 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.56/0.71 1.56/0.71 Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. 1.56/0.71 1.56/0.71 We consider the dependency pair problem (P_1, R_0, minimal, formative). 1.56/0.71 1.56/0.71 The formative rules of (P_1, R_0) are R_1 ::= 1.56/0.71 1.56/0.71 apply(fun(F), X) => F check(X) 1.56/0.71 1.56/0.71 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). 1.56/0.71 1.56/0.71 Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. 1.56/0.71 1.56/0.71 We consider the dependency pair problem (P_1, R_1, minimal, formative). 1.56/0.71 1.56/0.71 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: 1.56/0.71 1.56/0.71 apply#(fun(F), X) >? F(check(X)) 1.56/0.71 apply(fun(F), X) >= F check(X) 1.56/0.71 1.56/0.71 We orient these requirements with a polynomial interpretation in the natural numbers. 1.56/0.71 1.56/0.71 The following interpretation satisfies the requirements: 1.56/0.71 1.56/0.71 apply = \y0y1.3 + 3y0 1.56/0.71 apply# = \y0y1.3 + y0 1.56/0.71 check = \y0.0 1.56/0.71 fun = \G0.3 + G0(0) 1.56/0.71 1.56/0.71 Using this interpretation, the requirements translate to: 1.56/0.71 1.56/0.71 [[apply#(fun(_F0), _x1)]] = 6 + F0(0) > F0(0) = [[_F0(check(_x1))]] 1.56/0.71 [[apply(fun(_F0), _x1)]] = 12 + 3F0(0) >= F0(0) = [[_F0 check(_x1)]] 1.56/0.71 1.56/0.71 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.56/0.71 1.56/0.71 As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. 1.56/0.71 1.56/0.71 1.56/0.71 +++ Citations +++ 1.56/0.71 1.56/0.71 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 1.56/0.71 EOF