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