5.25/2.29	YES
5.25/2.30	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
5.25/2.30	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.25/2.30	
5.25/2.30	
5.25/2.30	Termination w.r.t. Q of the given QTRS could be proven:
5.25/2.30	
5.25/2.30	(0) QTRS
5.25/2.30	(1) DependencyPairsProof [EQUIVALENT, 6 ms]
5.25/2.30	(2) QDP
5.25/2.30	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
5.25/2.30	(4) AND
5.25/2.30	    (5) QDP
5.25/2.30	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
5.25/2.30	        (7) QDP
5.25/2.30	        (8) ATransformationProof [EQUIVALENT, 2 ms]
5.25/2.30	        (9) QDP
5.25/2.30	        (10) QReductionProof [EQUIVALENT, 0 ms]
5.25/2.30	        (11) QDP
5.25/2.30	        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
5.25/2.30	        (13) YES
5.25/2.30	    (14) QDP
5.25/2.30	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
5.25/2.30	        (16) QDP
5.25/2.30	        (17) ATransformationProof [EQUIVALENT, 0 ms]
5.25/2.30	        (18) QDP
5.25/2.30	        (19) QReductionProof [EQUIVALENT, 0 ms]
5.25/2.30	        (20) QDP
5.25/2.30	        (21) QDPOrderProof [EQUIVALENT, 53 ms]
5.25/2.30	        (22) QDP
5.25/2.30	        (23) DependencyGraphProof [EQUIVALENT, 0 ms]
5.25/2.30	        (24) TRUE
5.25/2.30	    (25) QDP
5.25/2.30	        (26) QDPSizeChangeProof [EQUIVALENT, 3 ms]
5.25/2.30	        (27) YES
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(0)
5.25/2.30	Obligation:
5.25/2.30	Q restricted rewrite system:
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	   app(app(minus, x), y) -> app(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   app(app(app(if, true), x), y) -> 0
5.25/2.30	   app(app(app(if, false), x), y) -> app(s, app(app(minus, app(p, x)), y))
5.25/2.30	   app(app(map, f), nil) -> nil
5.25/2.30	   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   app(app(filter, f), nil) -> nil
5.25/2.30	   app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(1) DependencyPairsProof (EQUIVALENT)
5.25/2.30	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(2)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(le, app(s, x)), app(s, y)) -> APP(app(le, x), y)
5.25/2.30	   APP(app(le, app(s, x)), app(s, y)) -> APP(le, x)
5.25/2.30	   APP(app(minus, x), y) -> APP(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   APP(app(minus, x), y) -> APP(app(if, app(app(le, x), y)), x)
5.25/2.30	   APP(app(minus, x), y) -> APP(if, app(app(le, x), y))
5.25/2.30	   APP(app(minus, x), y) -> APP(app(le, x), y)
5.25/2.30	   APP(app(minus, x), y) -> APP(le, x)
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(s, app(app(minus, app(p, x)), y))
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(app(minus, app(p, x)), y)
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(minus, app(p, x))
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(p, x)
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(cons, app(f, x))
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(filter2, app(f, x)), f), x)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(filter2, app(f, x)), f)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(filter2, app(f, x))
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	   APP(app(app(app(filter2, true), f), x), xs) -> APP(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   APP(app(app(app(filter2, true), f), x), xs) -> APP(cons, x)
5.25/2.30	   APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	   APP(app(app(app(filter2, true), f), x), xs) -> APP(filter, f)
5.25/2.30	   APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	   APP(app(app(app(filter2, false), f), x), xs) -> APP(filter, f)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	   app(app(minus, x), y) -> app(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   app(app(app(if, true), x), y) -> 0
5.25/2.30	   app(app(app(if, false), x), y) -> app(s, app(app(minus, app(p, x)), y))
5.25/2.30	   app(app(map, f), nil) -> nil
5.25/2.30	   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   app(app(filter, f), nil) -> nil
5.25/2.30	   app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(3) DependencyGraphProof (EQUIVALENT)
5.25/2.30	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 17 less nodes.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(4)
5.25/2.30	Complex Obligation (AND)
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(5)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(le, app(s, x)), app(s, y)) -> APP(app(le, x), y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	   app(app(minus, x), y) -> app(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   app(app(app(if, true), x), y) -> 0
5.25/2.30	   app(app(app(if, false), x), y) -> app(s, app(app(minus, app(p, x)), y))
5.25/2.30	   app(app(map, f), nil) -> nil
5.25/2.30	   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   app(app(filter, f), nil) -> nil
5.25/2.30	   app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(6) UsableRulesProof (EQUIVALENT)
5.25/2.30	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.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(7)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(le, app(s, x)), app(s, y)) -> APP(app(le, x), y)
5.25/2.30	
5.25/2.30	R is empty.
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(8) ATransformationProof (EQUIVALENT)
5.25/2.30	We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(9)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   le1(s(x), s(y)) -> le1(x, y)
5.25/2.30	
5.25/2.30	R is empty.
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   p(0)
5.25/2.30	   p(s(x0))
5.25/2.30	   le(0, x0)
5.25/2.30	   le(s(x0), 0)
5.25/2.30	   le(s(x0), s(x1))
5.25/2.30	   minus(x0, x1)
5.25/2.30	   if(true, x0, x1)
5.25/2.30	   if(false, x0, x1)
5.25/2.30	   map(x0, nil)
5.25/2.30	   map(x0, cons(x1, x2))
5.25/2.30	   filter(x0, nil)
5.25/2.30	   filter(x0, cons(x1, x2))
5.25/2.30	   filter2(true, x0, x1, x2)
5.25/2.30	   filter2(false, x0, x1, x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(10) QReductionProof (EQUIVALENT)
5.25/2.30	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.25/2.30	
5.25/2.30	   p(0)
5.25/2.30	   p(s(x0))
5.25/2.30	   le(0, x0)
5.25/2.30	   le(s(x0), 0)
5.25/2.30	   le(s(x0), s(x1))
5.25/2.30	   minus(x0, x1)
5.25/2.30	   if(true, x0, x1)
5.25/2.30	   if(false, x0, x1)
5.25/2.30	   map(x0, nil)
5.25/2.30	   map(x0, cons(x1, x2))
5.25/2.30	   filter(x0, nil)
5.25/2.30	   filter(x0, cons(x1, x2))
5.25/2.30	   filter2(true, x0, x1, x2)
5.25/2.30	   filter2(false, x0, x1, x2)
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(11)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   le1(s(x), s(y)) -> le1(x, y)
5.25/2.30	
5.25/2.30	R is empty.
5.25/2.30	Q is empty.
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(12) QDPSizeChangeProof (EQUIVALENT)
5.25/2.30	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. 
5.25/2.30	
5.25/2.30	From the DPs we obtained the following set of size-change graphs:
5.25/2.30	*le1(s(x), s(y)) -> le1(x, y)
5.25/2.30	The graph contains the following edges 1 > 1, 2 > 2
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(13)
5.25/2.30	YES
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(14)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(minus, x), y) -> APP(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(app(minus, app(p, x)), y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	   app(app(minus, x), y) -> app(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   app(app(app(if, true), x), y) -> 0
5.25/2.30	   app(app(app(if, false), x), y) -> app(s, app(app(minus, app(p, x)), y))
5.25/2.30	   app(app(map, f), nil) -> nil
5.25/2.30	   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   app(app(filter, f), nil) -> nil
5.25/2.30	   app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(15) UsableRulesProof (EQUIVALENT)
5.25/2.30	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.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(16)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(minus, x), y) -> APP(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   APP(app(app(if, false), x), y) -> APP(app(minus, app(p, x)), y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(17) ATransformationProof (EQUIVALENT)
5.25/2.30	We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(18)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   minus1(x, y) -> if1(le(x, y), x, y)
5.25/2.30	   if1(false, x, y) -> minus1(p(x), y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   p(0) -> 0
5.25/2.30	   p(s(x)) -> x
5.25/2.30	   le(0, y) -> true
5.25/2.30	   le(s(x), 0) -> false
5.25/2.30	   le(s(x), s(y)) -> le(x, y)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   p(0)
5.25/2.30	   p(s(x0))
5.25/2.30	   le(0, x0)
5.25/2.30	   le(s(x0), 0)
5.25/2.30	   le(s(x0), s(x1))
5.25/2.30	   minus(x0, x1)
5.25/2.30	   if(true, x0, x1)
5.25/2.30	   if(false, x0, x1)
5.25/2.30	   map(x0, nil)
5.25/2.30	   map(x0, cons(x1, x2))
5.25/2.30	   filter(x0, nil)
5.25/2.30	   filter(x0, cons(x1, x2))
5.25/2.30	   filter2(true, x0, x1, x2)
5.25/2.30	   filter2(false, x0, x1, x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(19) QReductionProof (EQUIVALENT)
5.25/2.30	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.25/2.30	
5.25/2.30	   minus(x0, x1)
5.25/2.30	   if(true, x0, x1)
5.25/2.30	   if(false, x0, x1)
5.25/2.30	   map(x0, nil)
5.25/2.30	   map(x0, cons(x1, x2))
5.25/2.30	   filter(x0, nil)
5.25/2.30	   filter(x0, cons(x1, x2))
5.25/2.30	   filter2(true, x0, x1, x2)
5.25/2.30	   filter2(false, x0, x1, x2)
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(20)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   minus1(x, y) -> if1(le(x, y), x, y)
5.25/2.30	   if1(false, x, y) -> minus1(p(x), y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   p(0) -> 0
5.25/2.30	   p(s(x)) -> x
5.25/2.30	   le(0, y) -> true
5.25/2.30	   le(s(x), 0) -> false
5.25/2.30	   le(s(x), s(y)) -> le(x, y)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   p(0)
5.25/2.30	   p(s(x0))
5.25/2.30	   le(0, x0)
5.25/2.30	   le(s(x0), 0)
5.25/2.30	   le(s(x0), s(x1))
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(21) QDPOrderProof (EQUIVALENT)
5.25/2.30	We use the reduction pair processor [LPAR04,JAR06].
5.25/2.30	
5.25/2.30	
5.25/2.30	The following pairs can be oriented strictly and are deleted.
5.25/2.30	
5.25/2.30	   if1(false, x, y) -> minus1(p(x), y)
5.25/2.30	The remaining pairs can at least be oriented weakly.
5.25/2.30	Used ordering:  Polynomial interpretation [POLO,RATPOLO]:
5.25/2.30	
5.25/2.30	   POL(0) = 0
5.25/2.30	   POL(false) = [1/4]
5.25/2.30	   POL(if1(x_1, x_2, x_3)) = [4]x_1 + [1/2]x_2
5.25/2.30	   POL(le(x_1, x_2)) = [1/4]x_1
5.25/2.30	   POL(minus1(x_1, x_2)) = [2]x_1
5.25/2.30	   POL(p(x_1)) = [1/4]x_1
5.25/2.30	   POL(s(x_1)) = [4] + [4]x_1
5.25/2.30	   POL(true) = 0
5.25/2.30	The value of delta used in the strict ordering is 1.
5.25/2.30	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
5.25/2.30	
5.25/2.30	   le(0, y) -> true
5.25/2.30	   le(s(x), 0) -> false
5.25/2.30	   le(s(x), s(y)) -> le(x, y)
5.25/2.30	   p(0) -> 0
5.25/2.30	   p(s(x)) -> x
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(22)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   minus1(x, y) -> if1(le(x, y), x, y)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   p(0) -> 0
5.25/2.30	   p(s(x)) -> x
5.25/2.30	   le(0, y) -> true
5.25/2.30	   le(s(x), 0) -> false
5.25/2.30	   le(s(x), s(y)) -> le(x, y)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   p(0)
5.25/2.30	   p(s(x0))
5.25/2.30	   le(0, x0)
5.25/2.30	   le(s(x0), 0)
5.25/2.30	   le(s(x0), s(x1))
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(23) DependencyGraphProof (EQUIVALENT)
5.25/2.30	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(24)
5.25/2.30	TRUE
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(25)
5.25/2.30	Obligation:
5.25/2.30	Q DP problem:
5.25/2.30	The TRS P consists of the following rules:
5.25/2.30	
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
5.25/2.30	   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	   APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	   APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The TRS R consists of the following rules:
5.25/2.30	
5.25/2.30	   app(p, 0) -> 0
5.25/2.30	   app(p, app(s, x)) -> x
5.25/2.30	   app(app(le, 0), y) -> true
5.25/2.30	   app(app(le, app(s, x)), 0) -> false
5.25/2.30	   app(app(le, app(s, x)), app(s, y)) -> app(app(le, x), y)
5.25/2.30	   app(app(minus, x), y) -> app(app(app(if, app(app(le, x), y)), x), y)
5.25/2.30	   app(app(app(if, true), x), y) -> 0
5.25/2.30	   app(app(app(if, false), x), y) -> app(s, app(app(minus, app(p, x)), y))
5.25/2.30	   app(app(map, f), nil) -> nil
5.25/2.30	   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
5.25/2.30	   app(app(filter, f), nil) -> nil
5.25/2.30	   app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	   app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs))
5.25/2.30	   app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs)
5.25/2.30	
5.25/2.30	The set Q consists of the following terms:
5.25/2.30	
5.25/2.30	   app(p, 0)
5.25/2.30	   app(p, app(s, x0))
5.25/2.30	   app(app(le, 0), x0)
5.25/2.30	   app(app(le, app(s, x0)), 0)
5.25/2.30	   app(app(le, app(s, x0)), app(s, x1))
5.25/2.30	   app(app(minus, x0), x1)
5.25/2.30	   app(app(app(if, true), x0), x1)
5.25/2.30	   app(app(app(if, false), x0), x1)
5.25/2.30	   app(app(map, x0), nil)
5.25/2.30	   app(app(map, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(filter, x0), nil)
5.25/2.30	   app(app(filter, x0), app(app(cons, x1), x2))
5.25/2.30	   app(app(app(app(filter2, true), x0), x1), x2)
5.25/2.30	   app(app(app(app(filter2, false), x0), x1), x2)
5.25/2.30	
5.25/2.30	We have to consider all minimal (P,Q,R)-chains.
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(26) QDPSizeChangeProof (EQUIVALENT)
5.25/2.30	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. 
5.25/2.30	
5.25/2.30	From the DPs we obtained the following set of size-change graphs:
5.25/2.30	*APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	The graph contains the following edges 1 > 1, 2 > 2
5.25/2.30	
5.25/2.30	
5.25/2.30	*APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)
5.25/2.30	The graph contains the following edges 1 > 1, 2 > 2
5.25/2.30	
5.25/2.30	
5.25/2.30	*APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
5.25/2.30	The graph contains the following edges 1 >= 1, 2 > 2
5.25/2.30	
5.25/2.30	
5.25/2.30	*APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs)
5.25/2.30	The graph contains the following edges 2 > 2
5.25/2.30	
5.25/2.30	
5.25/2.30	*APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	The graph contains the following edges 2 >= 2
5.25/2.30	
5.25/2.30	
5.25/2.30	*APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs)
5.25/2.30	The graph contains the following edges 2 >= 2
5.25/2.30	
5.25/2.30	
5.25/2.30	----------------------------------------
5.25/2.30	
5.25/2.30	(27)
5.25/2.30	YES
5.36/2.33	EOF