4.04/1.89	YES
4.32/1.90	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
4.32/1.90	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.32/1.90	
4.32/1.90	
4.32/1.90	Termination w.r.t. Q of the given QTRS could be proven:
4.32/1.90	
4.32/1.90	(0) QTRS
4.32/1.90	(1) DependencyPairsProof [EQUIVALENT, 55 ms]
4.32/1.90	(2) QDP
4.32/1.90	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
4.32/1.90	(4) QDP
4.32/1.90	(5) UsableRulesProof [EQUIVALENT, 0 ms]
4.32/1.90	(6) QDP
4.32/1.90	(7) QReductionProof [EQUIVALENT, 0 ms]
4.32/1.90	(8) QDP
4.32/1.90	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.32/1.90	(10) YES
4.32/1.90	
4.32/1.90	
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(0)
4.32/1.90	Obligation:
4.32/1.90	Q restricted rewrite system:
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   app(f, app(s, x)) -> app(f, app(app(g, x), x))
4.32/1.90	   app(app(g, 0), 1) -> app(s, 0)
4.32/1.90	   0 -> 1
4.32/1.90	   app(app(map, fun), nil) -> nil
4.32/1.90	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.32/1.90	   app(app(filter, fun), nil) -> nil
4.32/1.90	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.32/1.90	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.32/1.90	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   app(f, app(s, x0))
4.32/1.90	   0
4.32/1.90	   app(app(map, x0), nil)
4.32/1.90	   app(app(map, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(filter, x0), nil)
4.32/1.90	   app(app(filter, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(app(app(filter2, true), x0), x1), x2)
4.32/1.90	   app(app(app(app(filter2, false), x0), x1), x2)
4.32/1.90	
4.32/1.90	
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(1) DependencyPairsProof (EQUIVALENT)
4.32/1.90	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(2)
4.32/1.90	Obligation:
4.32/1.90	Q DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   APP(f, app(s, x)) -> APP(f, app(app(g, x), x))
4.32/1.90	   APP(f, app(s, x)) -> APP(app(g, x), x)
4.32/1.90	   APP(f, app(s, x)) -> APP(g, x)
4.32/1.90	   APP(app(g, 0), 1) -> APP(s, 0)
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(cons, app(fun, x)), app(app(map, fun), xs))
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(cons, app(fun, x))
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(filter2, app(fun, x)), fun), x)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(filter2, app(fun, x)), fun)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(filter2, app(fun, x))
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(cons, x), app(app(filter, fun), xs))
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(cons, x)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(filter, fun)
4.32/1.90	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(filter, fun)
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   app(f, app(s, x)) -> app(f, app(app(g, x), x))
4.32/1.90	   app(app(g, 0), 1) -> app(s, 0)
4.32/1.90	   0 -> 1
4.32/1.90	   app(app(map, fun), nil) -> nil
4.32/1.90	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.32/1.90	   app(app(filter, fun), nil) -> nil
4.32/1.90	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.32/1.90	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.32/1.90	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   app(f, app(s, x0))
4.32/1.90	   0
4.32/1.90	   app(app(map, x0), nil)
4.32/1.90	   app(app(map, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(filter, x0), nil)
4.32/1.90	   app(app(filter, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(app(app(filter2, true), x0), x1), x2)
4.32/1.90	   app(app(app(app(filter2, false), x0), x1), x2)
4.32/1.90	
4.32/1.90	We have to consider all minimal (P,Q,R)-chains.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(3) DependencyGraphProof (EQUIVALENT)
4.32/1.90	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 14 less nodes.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(4)
4.32/1.90	Obligation:
4.32/1.90	Q DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   app(f, app(s, x)) -> app(f, app(app(g, x), x))
4.32/1.90	   app(app(g, 0), 1) -> app(s, 0)
4.32/1.90	   0 -> 1
4.32/1.90	   app(app(map, fun), nil) -> nil
4.32/1.90	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.32/1.90	   app(app(filter, fun), nil) -> nil
4.32/1.90	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.32/1.90	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.32/1.90	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   app(f, app(s, x0))
4.32/1.90	   0
4.32/1.90	   app(app(map, x0), nil)
4.32/1.90	   app(app(map, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(filter, x0), nil)
4.32/1.90	   app(app(filter, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(app(app(filter2, true), x0), x1), x2)
4.32/1.90	   app(app(app(app(filter2, false), x0), x1), x2)
4.32/1.90	
4.32/1.90	We have to consider all minimal (P,Q,R)-chains.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(5) UsableRulesProof (EQUIVALENT)
4.32/1.90	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(6)
4.32/1.90	Obligation:
4.32/1.90	Q DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	R is empty.
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   app(f, app(s, x0))
4.32/1.90	   0
4.32/1.90	   app(app(map, x0), nil)
4.32/1.90	   app(app(map, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(filter, x0), nil)
4.32/1.90	   app(app(filter, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(app(app(filter2, true), x0), x1), x2)
4.32/1.90	   app(app(app(app(filter2, false), x0), x1), x2)
4.32/1.90	
4.32/1.90	We have to consider all minimal (P,Q,R)-chains.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(7) QReductionProof (EQUIVALENT)
4.32/1.90	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.32/1.90	
4.32/1.90	   0
4.32/1.90	
4.32/1.90	
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(8)
4.32/1.90	Obligation:
4.32/1.90	Q DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.32/1.90	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	
4.32/1.90	R is empty.
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   app(f, app(s, x0))
4.32/1.90	   app(app(map, x0), nil)
4.32/1.90	   app(app(map, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(filter, x0), nil)
4.32/1.90	   app(app(filter, x0), app(app(cons, x1), x2))
4.32/1.90	   app(app(app(app(filter2, true), x0), x1), x2)
4.32/1.90	   app(app(app(app(filter2, false), x0), x1), x2)
4.32/1.90	
4.32/1.90	We have to consider all minimal (P,Q,R)-chains.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(9) QDPSizeChangeProof (EQUIVALENT)
4.32/1.90	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
4.32/1.90	
4.32/1.90	From the DPs we obtained the following set of size-change graphs:
4.32/1.90	*APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	The graph contains the following edges 1 > 1, 2 > 2
4.32/1.90	
4.32/1.90	
4.32/1.90	*APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.32/1.90	The graph contains the following edges 1 > 1, 2 > 2
4.32/1.90	
4.32/1.90	
4.32/1.90	*APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.32/1.90	The graph contains the following edges 1 >= 1, 2 > 2
4.32/1.90	
4.32/1.90	
4.32/1.90	*APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	The graph contains the following edges 2 >= 2
4.32/1.90	
4.32/1.90	
4.32/1.90	*APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.32/1.90	The graph contains the following edges 2 >= 2
4.32/1.90	
4.32/1.90	
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(10)
4.32/1.90	YES
4.32/1.93	EOF