1.61/0.89	YES
1.61/0.90	We consider the system theBenchmark.
1.61/0.90	
1.61/0.90	  Alphabet:
1.61/0.90	
1.61/0.90	    0 : [] --> d 
1.61/0.90	    cons : [d * d] --> d 
1.61/0.90	    f : [d] --> a 
1.61/0.90	    false : [] --> c 
1.61/0.90	    filter : [d -> c * d] --> d 
1.61/0.90	    filter2 : [c * d -> c * d * d] --> d 
1.61/0.90	    g : [d] --> d 
1.61/0.90	    h : [d] --> b 
1.61/0.90	    map : [d -> d * d] --> d 
1.61/0.90	    nil : [] --> d 
1.61/0.90	    s : [d] --> d 
1.61/0.90	    true : [] --> c 
1.61/0.90	
1.61/0.90	  Rules:
1.61/0.90	
1.61/0.90	    f(s(x)) => f(x) 
1.61/0.90	    g(cons(0, x)) => g(x) 
1.61/0.90	    g(cons(s(x), y)) => s(x) 
1.61/0.90	    h(cons(x, y)) => h(g(cons(x, y))) 
1.61/0.90	    map(i, nil) => nil 
1.61/0.90	    map(i, cons(x, y)) => cons(i x, map(i, y)) 
1.61/0.90	    filter(i, nil) => nil 
1.61/0.90	    filter(i, cons(x, y)) => filter2(i x, i, x, y) 
1.61/0.90	    filter2(true, i, x, y) => cons(x, filter(i, y)) 
1.61/0.90	    filter2(false, i, x, y) => filter(i, y) 
1.61/0.90	
1.61/0.90	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
1.61/0.90	
1.61/0.90	We use rule removal, following [Kop12, Theorem 2.23].
1.61/0.90	
1.61/0.90	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
1.61/0.90	
1.61/0.90	  f(s(X)) >? f(X) 
1.61/0.90	  g(cons(0, X)) >? g(X) 
1.61/0.90	  g(cons(s(X), Y)) >? s(X) 
1.61/0.90	  h(cons(X, Y)) >? h(g(cons(X, Y))) 
1.61/0.90	  map(F, nil) >? nil 
1.61/0.90	  map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 
1.61/0.90	  filter(F, nil) >? nil 
1.61/0.90	  filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 
1.61/0.90	  filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 
1.61/0.90	  filter2(false, F, X, Y) >? filter(F, Y) 
1.61/0.90	
1.61/0.90	We orient these requirements with a polynomial interpretation in the natural numbers.
1.61/0.90	
1.61/0.90	The following interpretation satisfies the requirements:
1.61/0.90	
1.61/0.90	  0 = 3 
1.61/0.90	  cons = \y0y1.1 + y0 + y1 
1.61/0.90	  f = \y0.2y0 
1.61/0.90	  false = 3 
1.61/0.90	  filter = \G0y1.2y1 + G0(0) + y1G0(y1) 
1.61/0.90	  filter2 = \y0G1y2y3.1 + y0 + y2 + 2y3 + G1(0) + y3G1(y3) 
1.61/0.90	  g = \y0.y0 
1.61/0.90	  h = \y0.2y0 
1.61/0.90	  map = \G0y1.1 + 3y1 + G0(0) + 2y1G0(y1) 
1.61/0.90	  nil = 0 
1.61/0.90	  s = \y0.2y0 
1.61/0.90	  true = 3 
1.61/0.90	
1.61/0.90	Using this interpretation, the requirements translate to:
1.61/0.90	
1.61/0.90	  [[f(s(_x0))]] = 4x0 >= 2x0 = [[f(_x0)]] 
1.61/0.90	  [[g(cons(0, _x0))]] = 4 + x0 > x0 = [[g(_x0)]] 
1.61/0.90	  [[g(cons(s(_x0), _x1))]] = 1 + x1 + 2x0 > 2x0 = [[s(_x0)]] 
1.61/0.90	  [[h(cons(_x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[h(g(cons(_x0, _x1)))]] 
1.61/0.90	  [[map(_F0, nil)]] = 1 + F0(0) > 0 = [[nil]] 
1.61/0.90	  [[map(_F0, cons(_x1, _x2))]] = 4 + 3x1 + 3x2 + F0(0) + 2x1F0(1 + x1 + x2) + 2x2F0(1 + x1 + x2) + 2F0(1 + x1 + x2) > 2 + x1 + 3x2 + F0(0) + F0(x1) + 2x2F0(x2) = [[cons(_F0 _x1, map(_F0, _x2))]] 
1.61/0.90	  [[filter(_F0, nil)]] = F0(0) >= 0 = [[nil]] 
1.61/0.90	  [[filter(_F0, cons(_x1, _x2))]] = 2 + 2x1 + 2x2 + F0(0) + F0(1 + x1 + x2) + x1F0(1 + x1 + x2) + x2F0(1 + x1 + x2) > 1 + 2x1 + 2x2 + F0(0) + F0(x1) + x2F0(x2) = [[filter2(_F0 _x1, _F0, _x1, _x2)]] 
1.61/0.90	  [[filter2(true, _F0, _x1, _x2)]] = 4 + x1 + 2x2 + F0(0) + x2F0(x2) > 1 + x1 + 2x2 + F0(0) + x2F0(x2) = [[cons(_x1, filter(_F0, _x2))]] 
1.61/0.90	  [[filter2(false, _F0, _x1, _x2)]] = 4 + x1 + 2x2 + F0(0) + x2F0(x2) > 2x2 + F0(0) + x2F0(x2) = [[filter(_F0, _x2)]] 
1.61/0.90	
1.61/0.90	We can thus remove the following rules:
1.61/0.90	
1.61/0.90	  g(cons(0, X)) => g(X) 
1.61/0.90	  g(cons(s(X), Y)) => s(X) 
1.61/0.90	  map(F, nil) => nil 
1.61/0.90	  map(F, cons(X, Y)) => cons(F X, map(F, Y)) 
1.61/0.90	  filter(F, cons(X, Y)) => filter2(F X, F, X, Y) 
1.61/0.90	  filter2(true, F, X, Y) => cons(X, filter(F, Y)) 
1.61/0.90	  filter2(false, F, X, Y) => filter(F, Y) 
1.61/0.90	
1.61/0.90	We use rule removal, following [Kop12, Theorem 2.23].
1.61/0.90	
1.61/0.90	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
1.61/0.90	
1.61/0.90	  f(s(X)) >? f(X) 
1.61/0.90	  h(cons(X, Y)) >? h(g(cons(X, Y))) 
1.61/0.90	  filter(F, nil) >? nil 
1.61/0.90	
1.61/0.90	We orient these requirements with a polynomial interpretation in the natural numbers.
1.61/0.90	
1.61/0.90	The following interpretation satisfies the requirements:
1.61/0.90	
1.61/0.90	  cons = \y0y1.y0 + y1 
1.61/0.90	  f = \y0.y0 
1.61/0.90	  filter = \G0y1.3 + 3y1 + G0(0) 
1.61/0.90	  g = \y0.y0 
1.61/0.90	  h = \y0.y0 
1.61/0.90	  nil = 0 
1.61/0.90	  s = \y0.3 + 3y0 
1.61/0.90	
1.61/0.90	Using this interpretation, the requirements translate to:
1.61/0.90	
1.61/0.90	  [[f(s(_x0))]] = 3 + 3x0 > x0 = [[f(_x0)]] 
1.61/0.90	  [[h(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[h(g(cons(_x0, _x1)))]] 
1.61/0.90	  [[filter(_F0, nil)]] = 3 + F0(0) > 0 = [[nil]] 
1.61/0.90	
1.61/0.90	We can thus remove the following rules:
1.61/0.90	
1.61/0.90	  f(s(X)) => f(X) 
1.61/0.90	  filter(F, nil) => nil 
1.61/0.90	
1.61/0.90	We observe that the rules contain a first-order subset:
1.61/0.90	
1.61/0.90	  h(cons(X, Y)) => h(g(cons(X, Y))) 
1.61/0.90	
1.61/0.90	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.61/0.90	
1.61/0.90	According to the external first-order termination prover, this system is indeed terminating:
1.61/0.90	
1.61/0.90	 || proof of resources/system.trs
1.61/0.90	 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616
1.61/0.90	 || 
1.61/0.90	 || 
1.61/0.90	 || Termination w.r.t. Q of the given QTRS could be proven:
1.61/0.90	 || 
1.61/0.90	 || (0) QTRS
1.61/0.90	 || (1) AAECC Innermost [EQUIVALENT]
1.61/0.90	 || (2) QTRS
1.61/0.90	 || (3) DependencyPairsProof [EQUIVALENT]
1.61/0.90	 || (4) QDP
1.61/0.90	 || (5) DependencyGraphProof [EQUIVALENT]
1.61/0.90	 || (6) TRUE
1.61/0.90	 || 
1.61/0.90	 || 
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (0)
1.61/0.90	 || Obligation:
1.61/0.90	 || Q restricted rewrite system:
1.61/0.90	 || The TRS R consists of the following rules:
1.61/0.90	 || 
1.61/0.90	 ||    h(cons(%X, %Y)) -> h(g(cons(%X, %Y)))
1.61/0.90	 || 
1.61/0.90	 || Q is empty.
1.61/0.90	 || 
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (1) AAECC Innermost (EQUIVALENT)
1.61/0.90	 || We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is none
1.61/0.90	 || 
1.61/0.90	 || The TRS R 2 is 
1.61/0.90	 ||    h(cons(%X, %Y)) -> h(g(cons(%X, %Y)))
1.61/0.90	 || 
1.61/0.90	 || The signature Sigma is {h_1}
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (2)
1.61/0.90	 || Obligation:
1.61/0.90	 || Q restricted rewrite system:
1.61/0.90	 || The TRS R consists of the following rules:
1.61/0.90	 || 
1.61/0.90	 ||    h(cons(%X, %Y)) -> h(g(cons(%X, %Y)))
1.61/0.90	 || 
1.61/0.90	 || The set Q consists of the following terms:
1.61/0.90	 || 
1.61/0.90	 ||    h(cons(x0, x1))
1.61/0.90	 || 
1.61/0.90	 || 
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (3) DependencyPairsProof (EQUIVALENT)
1.61/0.90	 || Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (4)
1.61/0.90	 || Obligation:
1.61/0.90	 || Q DP problem:
1.61/0.90	 || The TRS P consists of the following rules:
1.61/0.90	 || 
1.61/0.90	 ||    H(cons(%X, %Y)) -> H(g(cons(%X, %Y)))
1.61/0.90	 || 
1.61/0.90	 || The TRS R consists of the following rules:
1.61/0.90	 || 
1.61/0.90	 ||    h(cons(%X, %Y)) -> h(g(cons(%X, %Y)))
1.61/0.90	 || 
1.61/0.90	 || The set Q consists of the following terms:
1.61/0.90	 || 
1.61/0.90	 ||    h(cons(x0, x1))
1.61/0.90	 || 
1.61/0.90	 || We have to consider all minimal (P,Q,R)-chains.
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (5) DependencyGraphProof (EQUIVALENT)
1.61/0.90	 || The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
1.61/0.90	 || ----------------------------------------
1.61/0.90	 || 
1.61/0.90	 || (6)
1.61/0.90	 || TRUE
1.61/0.90	 || 
1.61/0.90	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.61/0.90	
1.61/0.90	We thus obtain the following dependency pair problem (P_0, R_0, static, formative):
1.61/0.90	
1.61/0.90	  Dependency Pairs P_0:
1.61/0.90	
1.61/0.90	
1.61/0.90	  Rules R_0:
1.61/0.90	
1.61/0.90	    h(cons(X, Y)) => h(g(cons(X, Y))) 
1.61/0.90	
1.61/0.90	Thus, the original system is terminating if (P_0, R_0, static, formative) is finite.
1.61/0.90	
1.61/0.90	We consider the dependency pair problem (P_0, R_0, static, formative).
1.61/0.90	
1.61/0.90	We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:
1.61/0.90	
1.61/0.90	
1.61/0.90	This graph has no strongly connected components.  By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem.
1.61/0.90	
1.61/0.90	As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.
1.61/0.90	
1.61/0.90	
1.61/0.90	+++ Citations +++
1.61/0.90	
1.61/0.90	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
1.61/0.90	[Kop13]  C. Kop.  Static Dependency Pairs with Accessibility.  Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/static.pdf, 2013.
1.61/0.90	[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.61/0.90	EOF