4.89/2.04	YES
5.20/2.15	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
5.20/2.15	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.20/2.15	
5.20/2.15	
5.20/2.15	Quasi decreasingness of the given CTRS could be proven:
5.20/2.15	
5.20/2.15	(0) CTRS
5.20/2.15	(1) CTRSToQTRSProof [SOUND, 0 ms]
5.20/2.15	(2) QTRS
5.20/2.15	(3) Overlay + Local Confluence [EQUIVALENT, 0 ms]
5.20/2.15	(4) QTRS
5.20/2.15	(5) DependencyPairsProof [EQUIVALENT, 0 ms]
5.20/2.15	(6) QDP
5.20/2.15	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
5.20/2.15	(8) AND
5.20/2.15	    (9) QDP
5.20/2.15	        (10) UsableRulesProof [EQUIVALENT, 0 ms]
5.20/2.15	        (11) QDP
5.20/2.15	        (12) QReductionProof [EQUIVALENT, 0 ms]
5.20/2.15	        (13) QDP
5.20/2.15	        (14) QDPSizeChangeProof [EQUIVALENT, 0 ms]
5.20/2.15	        (15) YES
5.20/2.15	    (16) QDP
5.20/2.15	        (17) UsableRulesProof [EQUIVALENT, 0 ms]
5.20/2.15	        (18) QDP
5.20/2.15	        (19) QReductionProof [EQUIVALENT, 0 ms]
5.20/2.15	        (20) QDP
5.20/2.15	        (21) QDPSizeChangeProof [EQUIVALENT, 0 ms]
5.20/2.15	        (22) YES
5.20/2.15	    (23) QDP
5.20/2.15	        (24) UsableRulesProof [EQUIVALENT, 0 ms]
5.20/2.15	        (25) QDP
5.20/2.15	        (26) QReductionProof [EQUIVALENT, 0 ms]
5.20/2.15	        (27) QDP
5.20/2.15	        (28) QDPSizeChangeProof [EQUIVALENT, 0 ms]
5.20/2.15	        (29) YES
5.20/2.15	    (30) QDP
5.20/2.15	        (31) UsableRulesProof [EQUIVALENT, 0 ms]
5.20/2.15	        (32) QDP
5.20/2.15	        (33) QReductionProof [EQUIVALENT, 0 ms]
5.20/2.15	        (34) QDP
5.20/2.15	        (35) QDPOrderProof [EQUIVALENT, 36 ms]
5.20/2.15	        (36) QDP
5.20/2.15	        (37) PisEmptyProof [EQUIVALENT, 0 ms]
5.20/2.15	        (38) YES
5.20/2.15	
5.20/2.15	
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(0)
5.20/2.15	Obligation:
5.20/2.15	Conditional term rewrite system:
5.20/2.15	The TRS R consists of the following rules:
5.20/2.15	
5.20/2.15	   le(0, x) -> true
5.20/2.15	   le(s(x), 0) -> false
5.20/2.15	   le(s(x), s(y)) -> le(x, y)
5.20/2.15	   app(nil, x) -> x
5.20/2.15	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.15	   split(x, nil) -> pair(nil, nil)
5.20/2.15	   qsort(nil) -> nil
5.20/2.15	
5.20/2.15	The conditional TRS C consists of the following conditional rules:
5.20/2.15	
5.20/2.15	   split(x, cons(y, ys)) -> pair(xs, cons(y, zs)) <= split(x, ys) -> pair(xs, zs), le(x, y) -> true
5.20/2.15	   split(x, cons(y, ys)) -> pair(cons(y, xs), zs) <= split(x, ys) -> pair(xs, zs), le(x, y) -> false
5.20/2.15	   qsort(cons(x, xs)) -> app(qsort(ys), cons(x, qsort(zs))) <= split(x, xs) -> pair(ys, zs)
5.20/2.15	
5.20/2.15	
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(1) CTRSToQTRSProof (SOUND)
5.20/2.15	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(2)
5.20/2.15	Obligation:
5.20/2.15	Q restricted rewrite system:
5.20/2.15	The TRS R consists of the following rules:
5.20/2.15	
5.20/2.15	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.15	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.15	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.15	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.15	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.15	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.15	   le(0, x) -> true
5.20/2.15	   le(s(x), 0) -> false
5.20/2.15	   le(s(x), s(y)) -> le(x, y)
5.20/2.15	   app(nil, x) -> x
5.20/2.15	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.15	   split(x, nil) -> pair(nil, nil)
5.20/2.15	   qsort(nil) -> nil
5.20/2.15	
5.20/2.15	Q is empty.
5.20/2.15	
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(3) Overlay + Local Confluence (EQUIVALENT)
5.20/2.15	The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(4)
5.20/2.15	Obligation:
5.20/2.15	Q restricted rewrite system:
5.20/2.15	The TRS R consists of the following rules:
5.20/2.15	
5.20/2.15	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.15	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.15	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.15	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.15	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.15	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.15	   le(0, x) -> true
5.20/2.15	   le(s(x), 0) -> false
5.20/2.15	   le(s(x), s(y)) -> le(x, y)
5.20/2.15	   app(nil, x) -> x
5.20/2.15	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.15	   split(x, nil) -> pair(nil, nil)
5.20/2.15	   qsort(nil) -> nil
5.20/2.15	
5.20/2.15	The set Q consists of the following terms:
5.20/2.15	
5.20/2.15	   split(x0, cons(x1, x2))
5.20/2.15	   U1(pair(x0, x1), x2, x3)
5.20/2.15	   U2(false, x0, x1, x2)
5.20/2.15	   U2(true, x0, x1, x2)
5.20/2.15	   qsort(cons(x0, x1))
5.20/2.15	   U3(pair(x0, x1), x2)
5.20/2.15	   le(0, x0)
5.20/2.15	   le(s(x0), 0)
5.20/2.15	   le(s(x0), s(x1))
5.20/2.15	   app(nil, x0)
5.20/2.15	   app(cons(x0, x1), x2)
5.20/2.15	   split(x0, nil)
5.20/2.15	   qsort(nil)
5.20/2.15	
5.20/2.15	
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(5) DependencyPairsProof (EQUIVALENT)
5.20/2.15	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(6)
5.20/2.15	Obligation:
5.20/2.15	Q DP problem:
5.20/2.15	The TRS P consists of the following rules:
5.20/2.15	
5.20/2.15	   SPLIT(x, cons(y, ys)) -> U1^1(split(x, ys), x, y)
5.20/2.15	   SPLIT(x, cons(y, ys)) -> SPLIT(x, ys)
5.20/2.15	   U1^1(pair(xs, zs), x, y) -> U2^1(le(x, y), y, xs, zs)
5.20/2.15	   U1^1(pair(xs, zs), x, y) -> LE(x, y)
5.20/2.15	   QSORT(cons(x, xs)) -> U3^1(split(x, xs), x)
5.20/2.15	   QSORT(cons(x, xs)) -> SPLIT(x, xs)
5.20/2.15	   U3^1(pair(ys, zs), x) -> APP(qsort(ys), cons(x, qsort(zs)))
5.20/2.15	   U3^1(pair(ys, zs), x) -> QSORT(ys)
5.20/2.15	   U3^1(pair(ys, zs), x) -> QSORT(zs)
5.20/2.15	   LE(s(x), s(y)) -> LE(x, y)
5.20/2.15	   APP(cons(x, xs), ys) -> APP(xs, ys)
5.20/2.15	
5.20/2.15	The TRS R consists of the following rules:
5.20/2.15	
5.20/2.15	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.15	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.15	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.15	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.15	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.15	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.15	   le(0, x) -> true
5.20/2.15	   le(s(x), 0) -> false
5.20/2.15	   le(s(x), s(y)) -> le(x, y)
5.20/2.15	   app(nil, x) -> x
5.20/2.15	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.15	   split(x, nil) -> pair(nil, nil)
5.20/2.15	   qsort(nil) -> nil
5.20/2.15	
5.20/2.15	The set Q consists of the following terms:
5.20/2.15	
5.20/2.15	   split(x0, cons(x1, x2))
5.20/2.15	   U1(pair(x0, x1), x2, x3)
5.20/2.15	   U2(false, x0, x1, x2)
5.20/2.15	   U2(true, x0, x1, x2)
5.20/2.15	   qsort(cons(x0, x1))
5.20/2.15	   U3(pair(x0, x1), x2)
5.20/2.15	   le(0, x0)
5.20/2.15	   le(s(x0), 0)
5.20/2.15	   le(s(x0), s(x1))
5.20/2.15	   app(nil, x0)
5.20/2.15	   app(cons(x0, x1), x2)
5.20/2.15	   split(x0, nil)
5.20/2.15	   qsort(nil)
5.20/2.15	
5.20/2.15	We have to consider all minimal (P,Q,R)-chains.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(7) DependencyGraphProof (EQUIVALENT)
5.20/2.15	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 5 less nodes.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(8)
5.20/2.15	Complex Obligation (AND)
5.20/2.15	
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(9)
5.20/2.15	Obligation:
5.20/2.15	Q DP problem:
5.20/2.15	The TRS P consists of the following rules:
5.20/2.15	
5.20/2.15	   APP(cons(x, xs), ys) -> APP(xs, ys)
5.20/2.15	
5.20/2.15	The TRS R consists of the following rules:
5.20/2.15	
5.20/2.15	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.15	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.15	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.15	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.15	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.15	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.15	   le(0, x) -> true
5.20/2.15	   le(s(x), 0) -> false
5.20/2.15	   le(s(x), s(y)) -> le(x, y)
5.20/2.15	   app(nil, x) -> x
5.20/2.15	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.15	   split(x, nil) -> pair(nil, nil)
5.20/2.15	   qsort(nil) -> nil
5.20/2.15	
5.20/2.15	The set Q consists of the following terms:
5.20/2.15	
5.20/2.15	   split(x0, cons(x1, x2))
5.20/2.15	   U1(pair(x0, x1), x2, x3)
5.20/2.15	   U2(false, x0, x1, x2)
5.20/2.15	   U2(true, x0, x1, x2)
5.20/2.15	   qsort(cons(x0, x1))
5.20/2.15	   U3(pair(x0, x1), x2)
5.20/2.15	   le(0, x0)
5.20/2.15	   le(s(x0), 0)
5.20/2.15	   le(s(x0), s(x1))
5.20/2.15	   app(nil, x0)
5.20/2.15	   app(cons(x0, x1), x2)
5.20/2.15	   split(x0, nil)
5.20/2.15	   qsort(nil)
5.20/2.15	
5.20/2.15	We have to consider all minimal (P,Q,R)-chains.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(10) UsableRulesProof (EQUIVALENT)
5.20/2.15	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.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(11)
5.20/2.15	Obligation:
5.20/2.15	Q DP problem:
5.20/2.15	The TRS P consists of the following rules:
5.20/2.15	
5.20/2.15	   APP(cons(x, xs), ys) -> APP(xs, ys)
5.20/2.15	
5.20/2.15	R is empty.
5.20/2.15	The set Q consists of the following terms:
5.20/2.15	
5.20/2.15	   split(x0, cons(x1, x2))
5.20/2.15	   U1(pair(x0, x1), x2, x3)
5.20/2.15	   U2(false, x0, x1, x2)
5.20/2.15	   U2(true, x0, x1, x2)
5.20/2.15	   qsort(cons(x0, x1))
5.20/2.15	   U3(pair(x0, x1), x2)
5.20/2.15	   le(0, x0)
5.20/2.15	   le(s(x0), 0)
5.20/2.15	   le(s(x0), s(x1))
5.20/2.15	   app(nil, x0)
5.20/2.15	   app(cons(x0, x1), x2)
5.20/2.15	   split(x0, nil)
5.20/2.15	   qsort(nil)
5.20/2.15	
5.20/2.15	We have to consider all minimal (P,Q,R)-chains.
5.20/2.15	----------------------------------------
5.20/2.15	
5.20/2.15	(12) QReductionProof (EQUIVALENT)
5.20/2.15	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.20/2.15	
5.20/2.15	   split(x0, cons(x1, x2))
5.20/2.15	   U1(pair(x0, x1), x2, x3)
5.20/2.15	   U2(false, x0, x1, x2)
5.20/2.15	   U2(true, x0, x1, x2)
5.20/2.15	   qsort(cons(x0, x1))
5.20/2.15	   U3(pair(x0, x1), x2)
5.20/2.15	   le(0, x0)
5.20/2.15	   le(s(x0), 0)
5.20/2.15	   le(s(x0), s(x1))
5.20/2.15	   app(nil, x0)
5.20/2.15	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(13)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   APP(cons(x, xs), ys) -> APP(xs, ys)
5.20/2.16	
5.20/2.16	R is empty.
5.20/2.16	Q is empty.
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(14) QDPSizeChangeProof (EQUIVALENT)
5.20/2.16	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.20/2.16	
5.20/2.16	From the DPs we obtained the following set of size-change graphs:
5.20/2.16	*APP(cons(x, xs), ys) -> APP(xs, ys)
5.20/2.16	The graph contains the following edges 1 > 1, 2 >= 2
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(15)
5.20/2.16	YES
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(16)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   LE(s(x), s(y)) -> LE(x, y)
5.20/2.16	
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.16	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   app(nil, x) -> x
5.20/2.16	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   qsort(nil) -> nil
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(17) UsableRulesProof (EQUIVALENT)
5.20/2.16	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.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(18)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   LE(s(x), s(y)) -> LE(x, y)
5.20/2.16	
5.20/2.16	R is empty.
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(19) QReductionProof (EQUIVALENT)
5.20/2.16	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(20)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   LE(s(x), s(y)) -> LE(x, y)
5.20/2.16	
5.20/2.16	R is empty.
5.20/2.16	Q is empty.
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(21) QDPSizeChangeProof (EQUIVALENT)
5.20/2.16	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.20/2.16	
5.20/2.16	From the DPs we obtained the following set of size-change graphs:
5.20/2.16	*LE(s(x), s(y)) -> LE(x, y)
5.20/2.16	The graph contains the following edges 1 > 1, 2 > 2
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(22)
5.20/2.16	YES
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(23)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   SPLIT(x, cons(y, ys)) -> SPLIT(x, ys)
5.20/2.16	
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.16	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   app(nil, x) -> x
5.20/2.16	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   qsort(nil) -> nil
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(24) UsableRulesProof (EQUIVALENT)
5.20/2.16	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.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(25)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   SPLIT(x, cons(y, ys)) -> SPLIT(x, ys)
5.20/2.16	
5.20/2.16	R is empty.
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(26) QReductionProof (EQUIVALENT)
5.20/2.16	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(27)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   SPLIT(x, cons(y, ys)) -> SPLIT(x, ys)
5.20/2.16	
5.20/2.16	R is empty.
5.20/2.16	Q is empty.
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(28) QDPSizeChangeProof (EQUIVALENT)
5.20/2.16	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.20/2.16	
5.20/2.16	From the DPs we obtained the following set of size-change graphs:
5.20/2.16	*SPLIT(x, cons(y, ys)) -> SPLIT(x, ys)
5.20/2.16	The graph contains the following edges 1 >= 1, 2 > 2
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(29)
5.20/2.16	YES
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(30)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   QSORT(cons(x, xs)) -> U3^1(split(x, xs), x)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(ys)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(zs)
5.20/2.16	
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	   qsort(cons(x, xs)) -> U3(split(x, xs), x)
5.20/2.16	   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   app(nil, x) -> x
5.20/2.16	   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   qsort(nil) -> nil
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(31) UsableRulesProof (EQUIVALENT)
5.20/2.16	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.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(32)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   QSORT(cons(x, xs)) -> U3^1(split(x, xs), x)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(ys)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(zs)
5.20/2.16	
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   split(x0, nil)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(33) QReductionProof (EQUIVALENT)
5.20/2.16	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.20/2.16	
5.20/2.16	   qsort(cons(x0, x1))
5.20/2.16	   U3(pair(x0, x1), x2)
5.20/2.16	   app(nil, x0)
5.20/2.16	   app(cons(x0, x1), x2)
5.20/2.16	   qsort(nil)
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(34)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	The TRS P consists of the following rules:
5.20/2.16	
5.20/2.16	   QSORT(cons(x, xs)) -> U3^1(split(x, xs), x)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(ys)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(zs)
5.20/2.16	
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   split(x0, nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(35) QDPOrderProof (EQUIVALENT)
5.20/2.16	We use the reduction pair processor [LPAR04,JAR06].
5.20/2.16	
5.20/2.16	
5.20/2.16	The following pairs can be oriented strictly and are deleted.
5.20/2.16	
5.20/2.16	   QSORT(cons(x, xs)) -> U3^1(split(x, xs), x)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(ys)
5.20/2.16	   U3^1(pair(ys, zs), x) -> QSORT(zs)
5.20/2.16	The remaining pairs can at least be oriented weakly.
5.20/2.16	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
5.20/2.16	
5.20/2.16	POL( U3^1_2(x_1, x_2) ) = max{0, 2x_1 - 1}
5.20/2.16	POL( split_2(x_1, x_2) ) = x_2 + 2
5.20/2.16	POL( cons_2(x_1, x_2) ) = x_2 + 2
5.20/2.16	POL( U1_3(x_1, ..., x_3) ) = x_1 + 2
5.20/2.16	POL( nil ) = 0
5.20/2.16	POL( pair_2(x_1, x_2) ) = x_1 + x_2 + 2
5.20/2.16	POL( U2_4(x_1, ..., x_4) ) = 2x_1 + x_3 + x_4
5.20/2.16	POL( le_2(x_1, x_2) ) = 2
5.20/2.16	POL( 0 ) = 0
5.20/2.16	POL( true ) = 2
5.20/2.16	POL( s_1(x_1) ) = 2x_1 + 2
5.20/2.16	POL( false ) = 2
5.20/2.16	POL( QSORT_1(x_1) ) = 2x_1
5.20/2.16	
5.20/2.16	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	
5.20/2.16	
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(36)
5.20/2.16	Obligation:
5.20/2.16	Q DP problem:
5.20/2.16	P is empty.
5.20/2.16	The TRS R consists of the following rules:
5.20/2.16	
5.20/2.16	   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
5.20/2.16	   split(x, nil) -> pair(nil, nil)
5.20/2.16	   U1(pair(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
5.20/2.16	   le(0, x) -> true
5.20/2.16	   le(s(x), 0) -> false
5.20/2.16	   le(s(x), s(y)) -> le(x, y)
5.20/2.16	   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
5.20/2.16	   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
5.20/2.16	
5.20/2.16	The set Q consists of the following terms:
5.20/2.16	
5.20/2.16	   split(x0, cons(x1, x2))
5.20/2.16	   U1(pair(x0, x1), x2, x3)
5.20/2.16	   U2(false, x0, x1, x2)
5.20/2.16	   U2(true, x0, x1, x2)
5.20/2.16	   le(0, x0)
5.20/2.16	   le(s(x0), 0)
5.20/2.16	   le(s(x0), s(x1))
5.20/2.16	   split(x0, nil)
5.20/2.16	
5.20/2.16	We have to consider all minimal (P,Q,R)-chains.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(37) PisEmptyProof (EQUIVALENT)
5.20/2.16	The TRS P is empty. Hence, there is no (P,Q,R) chain.
5.20/2.16	----------------------------------------
5.20/2.16	
5.20/2.16	(38)
5.20/2.16	YES
5.31/2.20	EOF