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