4.06/1.87	YES
4.06/1.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.06/1.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.06/1.87	
4.06/1.87	
4.06/1.87	Termination w.r.t. Q of the given QTRS could be proven:
4.06/1.87	
4.06/1.87	(0) QTRS
4.06/1.87	(1) DependencyPairsProof [EQUIVALENT, 60 ms]
4.06/1.87	(2) QDP
4.06/1.87	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
4.06/1.87	(4) QDP
4.06/1.87	(5) UsableRulesProof [EQUIVALENT, 0 ms]
4.06/1.87	(6) QDP
4.06/1.87	(7) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.06/1.87	(8) YES
4.06/1.87	
4.06/1.87	
4.06/1.87	----------------------------------------
4.06/1.87	
4.06/1.87	(0)
4.06/1.87	Obligation:
4.06/1.87	Q restricted rewrite system:
4.06/1.87	The TRS R consists of the following rules:
4.06/1.87	
4.06/1.87	   app(app(f, x), app(g, x)) -> app(app(f, 1), app(g, x))
4.06/1.87	   app(g, 1) -> app(g, 0)
4.06/1.87	   app(app(map, fun), nil) -> nil
4.06/1.87	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.06/1.87	   app(app(filter, fun), nil) -> nil
4.06/1.87	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.06/1.87	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.06/1.87	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.06/1.88	
4.06/1.88	The set Q consists of the following terms:
4.06/1.88	
4.06/1.88	   app(app(f, x0), app(g, x0))
4.06/1.88	   app(g, 1)
4.06/1.88	   app(app(map, x0), nil)
4.06/1.88	   app(app(map, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(filter, x0), nil)
4.06/1.88	   app(app(filter, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(app(app(filter2, true), x0), x1), x2)
4.06/1.88	   app(app(app(app(filter2, false), x0), x1), x2)
4.06/1.88	
4.06/1.88	
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(1) DependencyPairsProof (EQUIVALENT)
4.06/1.88	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(2)
4.06/1.88	Obligation:
4.06/1.88	Q DP problem:
4.06/1.88	The TRS P consists of the following rules:
4.06/1.88	
4.06/1.88	   APP(app(f, x), app(g, x)) -> APP(app(f, 1), app(g, x))
4.06/1.88	   APP(app(f, x), app(g, x)) -> APP(f, 1)
4.06/1.88	   APP(g, 1) -> APP(g, 0)
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(cons, app(fun, x)), app(app(map, fun), xs))
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(cons, app(fun, x))
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(filter2, app(fun, x)), fun), x)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(filter2, app(fun, x)), fun)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(filter2, app(fun, x))
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(cons, x), app(app(filter, fun), xs))
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(cons, x)
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(filter, fun)
4.06/1.88	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(filter, fun)
4.06/1.88	
4.06/1.88	The TRS R consists of the following rules:
4.06/1.88	
4.06/1.88	   app(app(f, x), app(g, x)) -> app(app(f, 1), app(g, x))
4.06/1.88	   app(g, 1) -> app(g, 0)
4.06/1.88	   app(app(map, fun), nil) -> nil
4.06/1.88	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.06/1.88	   app(app(filter, fun), nil) -> nil
4.06/1.88	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.06/1.88	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.06/1.88	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.06/1.88	
4.06/1.88	The set Q consists of the following terms:
4.06/1.88	
4.06/1.88	   app(app(f, x0), app(g, x0))
4.06/1.88	   app(g, 1)
4.06/1.88	   app(app(map, x0), nil)
4.06/1.88	   app(app(map, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(filter, x0), nil)
4.06/1.88	   app(app(filter, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(app(app(filter2, true), x0), x1), x2)
4.06/1.88	   app(app(app(app(filter2, false), x0), x1), x2)
4.06/1.88	
4.06/1.88	We have to consider all minimal (P,Q,R)-chains.
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(3) DependencyGraphProof (EQUIVALENT)
4.06/1.88	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 13 less nodes.
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(4)
4.06/1.88	Obligation:
4.06/1.88	Q DP problem:
4.06/1.88	The TRS P consists of the following rules:
4.06/1.88	
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	
4.06/1.88	The TRS R consists of the following rules:
4.06/1.88	
4.06/1.88	   app(app(f, x), app(g, x)) -> app(app(f, 1), app(g, x))
4.06/1.88	   app(g, 1) -> app(g, 0)
4.06/1.88	   app(app(map, fun), nil) -> nil
4.06/1.88	   app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs))
4.06/1.88	   app(app(filter, fun), nil) -> nil
4.06/1.88	   app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs)
4.06/1.88	   app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs))
4.06/1.88	   app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs)
4.06/1.88	
4.06/1.88	The set Q consists of the following terms:
4.06/1.88	
4.06/1.88	   app(app(f, x0), app(g, x0))
4.06/1.88	   app(g, 1)
4.06/1.88	   app(app(map, x0), nil)
4.06/1.88	   app(app(map, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(filter, x0), nil)
4.06/1.88	   app(app(filter, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(app(app(filter2, true), x0), x1), x2)
4.06/1.88	   app(app(app(app(filter2, false), x0), x1), x2)
4.06/1.88	
4.06/1.88	We have to consider all minimal (P,Q,R)-chains.
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(5) UsableRulesProof (EQUIVALENT)
4.06/1.88	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.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(6)
4.06/1.88	Obligation:
4.06/1.88	Q DP problem:
4.06/1.88	The TRS P consists of the following rules:
4.06/1.88	
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.06/1.88	   APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	   APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	   APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	
4.06/1.88	R is empty.
4.06/1.88	The set Q consists of the following terms:
4.06/1.88	
4.06/1.88	   app(app(f, x0), app(g, x0))
4.06/1.88	   app(g, 1)
4.06/1.88	   app(app(map, x0), nil)
4.06/1.88	   app(app(map, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(filter, x0), nil)
4.06/1.88	   app(app(filter, x0), app(app(cons, x1), x2))
4.06/1.88	   app(app(app(app(filter2, true), x0), x1), x2)
4.06/1.88	   app(app(app(app(filter2, false), x0), x1), x2)
4.06/1.88	
4.06/1.88	We have to consider all minimal (P,Q,R)-chains.
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(7) QDPSizeChangeProof (EQUIVALENT)
4.06/1.88	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.06/1.88	
4.06/1.88	From the DPs we obtained the following set of size-change graphs:
4.06/1.88	*APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	The graph contains the following edges 1 > 1, 2 > 2
4.06/1.88	
4.06/1.88	
4.06/1.88	*APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x)
4.06/1.88	The graph contains the following edges 1 > 1, 2 > 2
4.06/1.88	
4.06/1.88	
4.06/1.88	*APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs)
4.06/1.88	The graph contains the following edges 1 >= 1, 2 > 2
4.06/1.88	
4.06/1.88	
4.06/1.88	*APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	The graph contains the following edges 2 >= 2
4.06/1.88	
4.06/1.88	
4.06/1.88	*APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs)
4.06/1.88	The graph contains the following edges 2 >= 2
4.06/1.88	
4.06/1.88	
4.06/1.88	----------------------------------------
4.06/1.88	
4.06/1.88	(8)
4.06/1.88	YES
4.06/1.91	EOF