6.17/2.64	YES
6.17/2.65	proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs
6.17/2.65	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.17/2.65	
6.17/2.65	
6.17/2.65	Termination of the given ITRS could be proven:
6.17/2.65	
6.17/2.65	(0) ITRS
6.17/2.65	(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
6.17/2.65	(2) IDP
6.17/2.65	(3) UsableRulesProof [EQUIVALENT, 0 ms]
6.17/2.65	(4) IDP
6.17/2.65	(5) IDependencyGraphProof [EQUIVALENT, 0 ms]
6.17/2.65	(6) AND
6.17/2.65	    (7) IDP
6.17/2.65	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
6.17/2.65	        (9) IDP
6.17/2.65	        (10) IDPtoQDPProof [SOUND, 35 ms]
6.17/2.65	        (11) QDP
6.17/2.65	        (12) QReductionProof [EQUIVALENT, 0 ms]
6.17/2.65	        (13) QDP
6.17/2.65	        (14) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.17/2.65	        (15) YES
6.17/2.65	    (16) IDP
6.17/2.65	        (17) IDPtoQDPProof [SOUND, 0 ms]
6.17/2.65	        (18) QDP
6.17/2.65	        (19) QReductionProof [EQUIVALENT, 0 ms]
6.17/2.65	        (20) QDP
6.17/2.65	        (21) QDPOrderProof [EQUIVALENT, 110 ms]
6.17/2.65	        (22) QDP
6.17/2.65	        (23) DependencyGraphProof [EQUIVALENT, 0 ms]
6.17/2.65	        (24) TRUE
6.17/2.65	
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(0)
6.17/2.65	Obligation:
6.17/2.65	ITRS problem:
6.17/2.65	
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	The TRS R consists of the following rules:
6.17/2.65	min(x, e) -> pair(x, e)
6.17/2.65	min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	msort(e) -> nil
6.17/2.65	msort(ins(x, ys)) -> if_3(min(x, ys), x, ys)
6.17/2.65	if_3(pair(m, zs), x, ys) -> cons(m, msort(zs))
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(1) ITRStoIDPProof (EQUIVALENT)
6.17/2.65	Added dependency pairs
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(2)
6.17/2.65	Obligation:
6.17/2.65	IDP problem:
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	
6.17/2.65	The following domains are used:
6.17/2.65	   Integer
6.17/2.65	
6.17/2.65	The ITRS R consists of the following rules:
6.17/2.65	min(x, e) -> pair(x, e)
6.17/2.65	min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	msort(e) -> nil
6.17/2.65	msort(ins(x, ys)) -> if_3(min(x, ys), x, ys)
6.17/2.65	if_3(pair(m, zs), x, ys) -> cons(m, msort(zs))
6.17/2.65	
6.17/2.65	The integer pair graph contains the following rules and edges:
6.17/2.65	(0): MIN(x[0], ins(y[0], zs[0])) -> IF_1(min(y[0], zs[0]), x[0], y[0], zs[0])
6.17/2.65	(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	(2): IF_1(pair(m[2], zh[2]), x[2], y[2], zs[2]) -> COND_IF_1(m[2] > x[2], pair(m[2], zh[2]), x[2], y[2], zs[2])
6.17/2.65	(3): MIN(x[3], ins(y[3], zs[3])) -> IF_2(min(y[3], zs[3]), x[3], y[3], zs[3])
6.17/2.65	(4): IF_2(pair(m[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_2(x[4] >= m[4], pair(m[4], zh[4]), x[4], y[4], zs[4])
6.17/2.65	(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.65	(6): MSORT(ins(x[6], ys[6])) -> MIN(x[6], ys[6])
6.17/2.65	(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.65	
6.17/2.65	   (0) -> (2), if (min(y[0], zs[0]) ->^* pair(m[2], zh[2]) & x[0] ->^* x[2] & y[0] ->^* y[2] & zs[0] ->^* zs[2])
6.17/2.65	   (1) -> (0), if (y[1] ->^* x[0] & zs[1] ->^* ins(y[0], zs[0]))
6.17/2.65	   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
6.17/2.65	   (1) -> (3), if (y[1] ->^* x[3] & zs[1] ->^* ins(y[3], zs[3]))
6.17/2.65	   (3) -> (4), if (min(y[3], zs[3]) ->^* pair(m[4], zh[4]) & x[3] ->^* x[4] & y[3] ->^* y[4] & zs[3] ->^* zs[4])
6.17/2.65	   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])
6.17/2.65	   (6) -> (0), if (x[6] ->^* x[0] & ys[6] ->^* ins(y[0], zs[0]))
6.17/2.65	   (6) -> (1), if (x[6] ->^* x[1] & ys[6] ->^* ins(y[1], zs[1]))
6.17/2.65	   (6) -> (3), if (x[6] ->^* x[3] & ys[6] ->^* ins(y[3], zs[3]))
6.17/2.65	   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
6.17/2.65	   (7) -> (6), if (zs[7] ->^* ins(x[6], ys[6]))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(3) UsableRulesProof (EQUIVALENT)
6.17/2.65	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.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(4)
6.17/2.65	Obligation:
6.17/2.65	IDP problem:
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	
6.17/2.65	The following domains are used:
6.17/2.65	   Integer
6.17/2.65	
6.17/2.65	The ITRS R consists of the following rules:
6.17/2.65	min(x, e) -> pair(x, e)
6.17/2.65	min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
6.17/2.65	if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	
6.17/2.65	The integer pair graph contains the following rules and edges:
6.17/2.65	(0): MIN(x[0], ins(y[0], zs[0])) -> IF_1(min(y[0], zs[0]), x[0], y[0], zs[0])
6.17/2.65	(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	(2): IF_1(pair(m[2], zh[2]), x[2], y[2], zs[2]) -> COND_IF_1(m[2] > x[2], pair(m[2], zh[2]), x[2], y[2], zs[2])
6.17/2.65	(3): MIN(x[3], ins(y[3], zs[3])) -> IF_2(min(y[3], zs[3]), x[3], y[3], zs[3])
6.17/2.65	(4): IF_2(pair(m[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_2(x[4] >= m[4], pair(m[4], zh[4]), x[4], y[4], zs[4])
6.17/2.65	(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.65	(6): MSORT(ins(x[6], ys[6])) -> MIN(x[6], ys[6])
6.17/2.65	(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.65	
6.17/2.65	   (0) -> (2), if (min(y[0], zs[0]) ->^* pair(m[2], zh[2]) & x[0] ->^* x[2] & y[0] ->^* y[2] & zs[0] ->^* zs[2])
6.17/2.65	   (1) -> (0), if (y[1] ->^* x[0] & zs[1] ->^* ins(y[0], zs[0]))
6.17/2.65	   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
6.17/2.65	   (1) -> (3), if (y[1] ->^* x[3] & zs[1] ->^* ins(y[3], zs[3]))
6.17/2.65	   (3) -> (4), if (min(y[3], zs[3]) ->^* pair(m[4], zh[4]) & x[3] ->^* x[4] & y[3] ->^* y[4] & zs[3] ->^* zs[4])
6.17/2.65	   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])
6.17/2.65	   (6) -> (0), if (x[6] ->^* x[0] & ys[6] ->^* ins(y[0], zs[0]))
6.17/2.65	   (6) -> (1), if (x[6] ->^* x[1] & ys[6] ->^* ins(y[1], zs[1]))
6.17/2.65	   (6) -> (3), if (x[6] ->^* x[3] & ys[6] ->^* ins(y[3], zs[3]))
6.17/2.65	   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
6.17/2.65	   (7) -> (6), if (zs[7] ->^* ins(x[6], ys[6]))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(5) IDependencyGraphProof (EQUIVALENT)
6.17/2.65	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(6)
6.17/2.65	Complex Obligation (AND)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(7)
6.17/2.65	Obligation:
6.17/2.65	IDP problem:
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	
6.17/2.65	The following domains are used:
6.17/2.65	   Integer
6.17/2.65	
6.17/2.65	The ITRS R consists of the following rules:
6.17/2.65	min(x, e) -> pair(x, e)
6.17/2.65	min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
6.17/2.65	if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	
6.17/2.65	The integer pair graph contains the following rules and edges:
6.17/2.65	(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	
6.17/2.65	   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(8) UsableRulesProof (EQUIVALENT)
6.17/2.65	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.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(9)
6.17/2.65	Obligation:
6.17/2.65	IDP problem:
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	
6.17/2.65	The following domains are used:
6.17/2.65	none
6.17/2.65	
6.17/2.65	R is empty.
6.17/2.65	
6.17/2.65	The integer pair graph contains the following rules and edges:
6.17/2.65	(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	
6.17/2.65	   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(10) IDPtoQDPProof (SOUND)
6.17/2.65	Represented integers and predefined function symbols by Terms
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(11)
6.17/2.65	Obligation:
6.17/2.65	Q DP problem:
6.17/2.65	The TRS P consists of the following rules:
6.17/2.65	
6.17/2.65	   MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	
6.17/2.65	R is empty.
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	
6.17/2.65	   min(x0, e)
6.17/2.65	   min(x0, ins(x1, x2))
6.17/2.65	   if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   msort(e)
6.17/2.65	   msort(ins(x0, x1))
6.17/2.65	   if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	We have to consider all minimal (P,Q,R)-chains.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(12) QReductionProof (EQUIVALENT)
6.17/2.65	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
6.17/2.65	
6.17/2.65	   min(x0, e)
6.17/2.65	   min(x0, ins(x1, x2))
6.17/2.65	   if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   msort(e)
6.17/2.65	   msort(ins(x0, x1))
6.17/2.65	   if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(13)
6.17/2.65	Obligation:
6.17/2.65	Q DP problem:
6.17/2.65	The TRS P consists of the following rules:
6.17/2.65	
6.17/2.65	   MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	
6.17/2.65	R is empty.
6.17/2.65	Q is empty.
6.17/2.65	We have to consider all minimal (P,Q,R)-chains.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(14) QDPSizeChangeProof (EQUIVALENT)
6.17/2.65	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. 
6.17/2.65	
6.17/2.65	From the DPs we obtained the following set of size-change graphs:
6.17/2.65	*MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
6.17/2.65	The graph contains the following edges 2 > 1, 2 > 2
6.17/2.65	
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(15)
6.17/2.65	YES
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(16)
6.17/2.65	Obligation:
6.17/2.65	IDP problem:
6.17/2.65	The following function symbols are pre-defined:
6.17/2.65	<<<
6.17/2.65	 & 	~ 	Bwand: (Integer, Integer) -> Integer
6.17/2.65	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
6.17/2.65	 | 	~ 	Bwor: (Integer, Integer) -> Integer
6.17/2.65	 / 	~ 	Div: (Integer, Integer) -> Integer
6.17/2.65	 != 	~ 	Neq: (Integer, Integer) -> Boolean
6.17/2.65	 && 	~ 	Land: (Boolean, Boolean) -> Boolean
6.17/2.65	 ! 	~ 	Lnot: (Boolean) -> Boolean
6.17/2.65	 = 	~ 	Eq: (Integer, Integer) -> Boolean
6.17/2.65	 <= 	~ 	Le: (Integer, Integer) -> Boolean
6.17/2.65	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
6.17/2.65	 % 	~ 	Mod: (Integer, Integer) -> Integer
6.17/2.65	 > 	~ 	Gt: (Integer, Integer) -> Boolean
6.17/2.65	 + 	~ 	Add: (Integer, Integer) -> Integer
6.17/2.65	 -1 	~ 	UnaryMinus: (Integer) -> Integer
6.17/2.65	 < 	~ 	Lt: (Integer, Integer) -> Boolean
6.17/2.65	 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
6.17/2.65	 - 	~ 	Sub: (Integer, Integer) -> Integer
6.17/2.65	 ~ 	~ 	Bwnot: (Integer) -> Integer
6.17/2.65	 * 	~ 	Mul: (Integer, Integer) -> Integer
6.17/2.65	>>>
6.17/2.65	
6.17/2.65	
6.17/2.65	The following domains are used:
6.17/2.65	   Integer
6.17/2.65	
6.17/2.65	The ITRS R consists of the following rules:
6.17/2.65	min(x, e) -> pair(x, e)
6.17/2.65	min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
6.17/2.65	if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
6.17/2.65	Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	
6.17/2.65	The integer pair graph contains the following rules and edges:
6.17/2.65	(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.65	(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.65	
6.17/2.65	   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
6.17/2.65	   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	min(x0, e)
6.17/2.65	min(x0, ins(x1, x2))
6.17/2.65	if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
6.17/2.65	msort(e)
6.17/2.65	msort(ins(x0, x1))
6.17/2.65	if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(17) IDPtoQDPProof (SOUND)
6.17/2.65	Represented integers and predefined function symbols by Terms
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(18)
6.17/2.65	Obligation:
6.17/2.65	Q DP problem:
6.17/2.65	The TRS P consists of the following rules:
6.17/2.65	
6.17/2.65	   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.65	   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.65	
6.17/2.65	The TRS R consists of the following rules:
6.17/2.65	
6.17/2.65	   min(x, e) -> pair(x, e)
6.17/2.65	   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
6.17/2.65	   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
6.17/2.65	   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	   greatereq_int(pos(x), pos(0)) -> true
6.17/2.65	   greatereq_int(neg(0), pos(0)) -> true
6.17/2.65	   greatereq_int(neg(0), neg(y)) -> true
6.17/2.65	   greatereq_int(pos(x), neg(y)) -> true
6.17/2.65	   greatereq_int(pos(0), pos(s(y))) -> false
6.17/2.65	   greatereq_int(neg(x), pos(s(y))) -> false
6.17/2.65	   greatereq_int(neg(s(x)), pos(0)) -> false
6.17/2.65	   greatereq_int(neg(s(x)), neg(0)) -> false
6.17/2.65	   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
6.17/2.65	   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
6.17/2.65	   greater_int(pos(0), pos(0)) -> false
6.17/2.65	   greater_int(pos(0), neg(0)) -> false
6.17/2.65	   greater_int(neg(0), pos(0)) -> false
6.17/2.65	   greater_int(neg(0), neg(0)) -> false
6.17/2.65	   greater_int(pos(0), pos(s(y))) -> false
6.17/2.65	   greater_int(neg(0), pos(s(y))) -> false
6.17/2.65	   greater_int(pos(0), neg(s(y))) -> true
6.17/2.65	   greater_int(neg(0), neg(s(y))) -> true
6.17/2.65	   greater_int(pos(s(x)), pos(0)) -> true
6.17/2.65	   greater_int(neg(s(x)), pos(0)) -> false
6.17/2.65	   greater_int(pos(s(x)), neg(0)) -> true
6.17/2.65	   greater_int(neg(s(x)), neg(0)) -> false
6.17/2.65	   greater_int(pos(s(x)), neg(s(y))) -> true
6.17/2.65	   greater_int(neg(s(x)), pos(s(y))) -> false
6.17/2.65	   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
6.17/2.65	   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	
6.17/2.65	   min(x0, e)
6.17/2.65	   min(x0, ins(x1, x2))
6.17/2.65	   if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   msort(e)
6.17/2.65	   msort(ins(x0, x1))
6.17/2.65	   if_3(pair(x0, x1), x2, x3)
6.17/2.65	   greatereq_int(pos(x0), pos(0))
6.17/2.65	   greatereq_int(neg(0), pos(0))
6.17/2.65	   greatereq_int(neg(0), neg(x0))
6.17/2.65	   greatereq_int(pos(x0), neg(x1))
6.17/2.65	   greatereq_int(pos(0), pos(s(x0)))
6.17/2.65	   greatereq_int(neg(x0), pos(s(x1)))
6.17/2.65	   greatereq_int(neg(s(x0)), pos(0))
6.17/2.65	   greatereq_int(neg(s(x0)), neg(0))
6.17/2.65	   greatereq_int(pos(s(x0)), pos(s(x1)))
6.17/2.65	   greatereq_int(neg(s(x0)), neg(s(x1)))
6.17/2.65	   greater_int(pos(0), pos(0))
6.17/2.65	   greater_int(pos(0), neg(0))
6.17/2.65	   greater_int(neg(0), pos(0))
6.17/2.65	   greater_int(neg(0), neg(0))
6.17/2.65	   greater_int(pos(0), pos(s(x0)))
6.17/2.65	   greater_int(neg(0), pos(s(x0)))
6.17/2.65	   greater_int(pos(0), neg(s(x0)))
6.17/2.65	   greater_int(neg(0), neg(s(x0)))
6.17/2.65	   greater_int(pos(s(x0)), pos(0))
6.17/2.65	   greater_int(neg(s(x0)), pos(0))
6.17/2.65	   greater_int(pos(s(x0)), neg(0))
6.17/2.65	   greater_int(neg(s(x0)), neg(0))
6.17/2.65	   greater_int(pos(s(x0)), neg(s(x1)))
6.17/2.65	   greater_int(neg(s(x0)), pos(s(x1)))
6.17/2.65	   greater_int(pos(s(x0)), pos(s(x1)))
6.17/2.65	   greater_int(neg(s(x0)), neg(s(x1)))
6.17/2.65	
6.17/2.65	We have to consider all minimal (P,Q,R)-chains.
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(19) QReductionProof (EQUIVALENT)
6.17/2.65	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
6.17/2.65	
6.17/2.65	   msort(e)
6.17/2.65	   msort(ins(x0, x1))
6.17/2.65	   if_3(pair(x0, x1), x2, x3)
6.17/2.65	
6.17/2.65	
6.17/2.65	----------------------------------------
6.17/2.65	
6.17/2.65	(20)
6.17/2.65	Obligation:
6.17/2.65	Q DP problem:
6.17/2.65	The TRS P consists of the following rules:
6.17/2.65	
6.17/2.65	   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.65	   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.65	
6.17/2.65	The TRS R consists of the following rules:
6.17/2.65	
6.17/2.65	   min(x, e) -> pair(x, e)
6.17/2.65	   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.65	   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.65	   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
6.17/2.65	   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
6.17/2.65	   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.65	   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.65	   greatereq_int(pos(x), pos(0)) -> true
6.17/2.65	   greatereq_int(neg(0), pos(0)) -> true
6.17/2.65	   greatereq_int(neg(0), neg(y)) -> true
6.17/2.65	   greatereq_int(pos(x), neg(y)) -> true
6.17/2.65	   greatereq_int(pos(0), pos(s(y))) -> false
6.17/2.65	   greatereq_int(neg(x), pos(s(y))) -> false
6.17/2.65	   greatereq_int(neg(s(x)), pos(0)) -> false
6.17/2.65	   greatereq_int(neg(s(x)), neg(0)) -> false
6.17/2.65	   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
6.17/2.65	   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
6.17/2.65	   greater_int(pos(0), pos(0)) -> false
6.17/2.65	   greater_int(pos(0), neg(0)) -> false
6.17/2.65	   greater_int(neg(0), pos(0)) -> false
6.17/2.65	   greater_int(neg(0), neg(0)) -> false
6.17/2.65	   greater_int(pos(0), pos(s(y))) -> false
6.17/2.65	   greater_int(neg(0), pos(s(y))) -> false
6.17/2.65	   greater_int(pos(0), neg(s(y))) -> true
6.17/2.65	   greater_int(neg(0), neg(s(y))) -> true
6.17/2.65	   greater_int(pos(s(x)), pos(0)) -> true
6.17/2.65	   greater_int(neg(s(x)), pos(0)) -> false
6.17/2.65	   greater_int(pos(s(x)), neg(0)) -> true
6.17/2.65	   greater_int(neg(s(x)), neg(0)) -> false
6.17/2.65	   greater_int(pos(s(x)), neg(s(y))) -> true
6.17/2.65	   greater_int(neg(s(x)), pos(s(y))) -> false
6.17/2.65	   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
6.17/2.65	   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
6.17/2.65	
6.17/2.65	The set Q consists of the following terms:
6.17/2.65	
6.17/2.65	   min(x0, e)
6.17/2.65	   min(x0, ins(x1, x2))
6.17/2.65	   if_1(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   if_2(pair(x0, x1), x2, x3, x4)
6.17/2.65	   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
6.17/2.65	   greatereq_int(pos(x0), pos(0))
6.17/2.65	   greatereq_int(neg(0), pos(0))
6.17/2.65	   greatereq_int(neg(0), neg(x0))
6.17/2.65	   greatereq_int(pos(x0), neg(x1))
6.17/2.65	   greatereq_int(pos(0), pos(s(x0)))
6.17/2.65	   greatereq_int(neg(x0), pos(s(x1)))
6.17/2.65	   greatereq_int(neg(s(x0)), pos(0))
6.17/2.65	   greatereq_int(neg(s(x0)), neg(0))
6.17/2.65	   greatereq_int(pos(s(x0)), pos(s(x1)))
6.17/2.65	   greatereq_int(neg(s(x0)), neg(s(x1)))
6.17/2.65	   greater_int(pos(0), pos(0))
6.17/2.65	   greater_int(pos(0), neg(0))
6.17/2.65	   greater_int(neg(0), pos(0))
6.17/2.65	   greater_int(neg(0), neg(0))
6.17/2.65	   greater_int(pos(0), pos(s(x0)))
6.17/2.65	   greater_int(neg(0), pos(s(x0)))
6.17/2.65	   greater_int(pos(0), neg(s(x0)))
6.17/2.65	   greater_int(neg(0), neg(s(x0)))
6.17/2.65	   greater_int(pos(s(x0)), pos(0))
6.17/2.65	   greater_int(neg(s(x0)), pos(0))
6.17/2.65	   greater_int(pos(s(x0)), neg(0))
6.17/2.66	   greater_int(neg(s(x0)), neg(0))
6.17/2.66	   greater_int(pos(s(x0)), neg(s(x1)))
6.17/2.66	   greater_int(neg(s(x0)), pos(s(x1)))
6.17/2.66	   greater_int(pos(s(x0)), pos(s(x1)))
6.17/2.66	   greater_int(neg(s(x0)), neg(s(x1)))
6.17/2.66	
6.17/2.66	We have to consider all minimal (P,Q,R)-chains.
6.17/2.66	----------------------------------------
6.17/2.66	
6.17/2.66	(21) QDPOrderProof (EQUIVALENT)
6.17/2.66	We use the reduction pair processor [LPAR04,JAR06].
6.17/2.66	
6.17/2.66	
6.17/2.66	The following pairs can be oriented strictly and are deleted.
6.17/2.66	
6.17/2.66	   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
6.17/2.66	The remaining pairs can at least be oriented weakly.
6.17/2.66	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
6.17/2.66	
6.17/2.66	POL( IF_3_3(x_1, ..., x_3) ) = max{0, x_1 - 2}
6.17/2.66	POL( min_2(x_1, x_2) ) = 2x_2
6.17/2.66	POL( e ) = 2
6.17/2.66	POL( pair_2(x_1, x_2) ) = x_2 + 2
6.17/2.66	POL( ins_2(x_1, x_2) ) = 2x_2 + 1
6.17/2.66	POL( if_1_4(x_1, ..., x_4) ) = max{0, 2x_1 - 1}
6.17/2.66	POL( if_2_4(x_1, ..., x_4) ) = 2x_1
6.17/2.66	POL( Cond_if_2_5(x_1, ..., x_5) ) = max{0, 2x_2 - 1}
6.17/2.66	POL( greatereq_int_2(x_1, x_2) ) = max{0, -2}
6.17/2.66	POL( Cond_if_1_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_2 - 2}
6.17/2.66	POL( greater_int_2(x_1, x_2) ) = 1
6.17/2.66	POL( pos_1(x_1) ) = 0
6.17/2.66	POL( 0 ) = 0
6.17/2.66	POL( true ) = 1
6.17/2.66	POL( neg_1(x_1) ) = 0
6.17/2.66	POL( s_1(x_1) ) = 0
6.17/2.66	POL( false ) = 0
6.17/2.66	POL( MSORT_1(x_1) ) = x_1
6.17/2.66	
6.17/2.66	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
6.17/2.66	
6.17/2.66	   min(x, e) -> pair(x, e)
6.17/2.66	   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.66	   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.66	   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
6.17/2.66	   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
6.17/2.66	   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.66	   greater_int(pos(0), pos(0)) -> false
6.17/2.66	   greater_int(pos(0), neg(0)) -> false
6.17/2.66	   greater_int(neg(0), pos(0)) -> false
6.17/2.66	   greater_int(neg(0), neg(0)) -> false
6.17/2.66	   greater_int(pos(0), pos(s(y))) -> false
6.17/2.66	   greater_int(neg(0), pos(s(y))) -> false
6.17/2.66	   greater_int(pos(0), neg(s(y))) -> true
6.17/2.66	   greater_int(neg(0), neg(s(y))) -> true
6.17/2.66	   greater_int(pos(s(x)), pos(0)) -> true
6.17/2.66	   greater_int(neg(s(x)), pos(0)) -> false
6.17/2.66	   greater_int(pos(s(x)), neg(0)) -> true
6.17/2.66	   greater_int(neg(s(x)), neg(0)) -> false
6.17/2.66	   greater_int(pos(s(x)), neg(s(y))) -> true
6.17/2.66	   greater_int(neg(s(x)), pos(s(y))) -> false
6.17/2.66	   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
6.17/2.66	   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
6.17/2.66	   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.66	
6.17/2.66	
6.17/2.66	----------------------------------------
6.17/2.66	
6.17/2.66	(22)
6.17/2.66	Obligation:
6.17/2.66	Q DP problem:
6.17/2.66	The TRS P consists of the following rules:
6.17/2.66	
6.17/2.66	   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
6.17/2.66	
6.17/2.66	The TRS R consists of the following rules:
6.17/2.66	
6.17/2.66	   min(x, e) -> pair(x, e)
6.17/2.66	   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
6.17/2.66	   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
6.17/2.66	   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
6.17/2.66	   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
6.17/2.66	   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
6.17/2.66	   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
6.17/2.66	   greatereq_int(pos(x), pos(0)) -> true
6.17/2.66	   greatereq_int(neg(0), pos(0)) -> true
6.17/2.66	   greatereq_int(neg(0), neg(y)) -> true
6.17/2.66	   greatereq_int(pos(x), neg(y)) -> true
6.17/2.66	   greatereq_int(pos(0), pos(s(y))) -> false
6.17/2.66	   greatereq_int(neg(x), pos(s(y))) -> false
6.17/2.66	   greatereq_int(neg(s(x)), pos(0)) -> false
6.17/2.66	   greatereq_int(neg(s(x)), neg(0)) -> false
6.17/2.66	   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
6.17/2.66	   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
6.17/2.66	   greater_int(pos(0), pos(0)) -> false
6.17/2.66	   greater_int(pos(0), neg(0)) -> false
6.17/2.66	   greater_int(neg(0), pos(0)) -> false
6.17/2.66	   greater_int(neg(0), neg(0)) -> false
6.17/2.66	   greater_int(pos(0), pos(s(y))) -> false
6.17/2.66	   greater_int(neg(0), pos(s(y))) -> false
6.17/2.66	   greater_int(pos(0), neg(s(y))) -> true
6.17/2.66	   greater_int(neg(0), neg(s(y))) -> true
6.17/2.66	   greater_int(pos(s(x)), pos(0)) -> true
6.17/2.66	   greater_int(neg(s(x)), pos(0)) -> false
6.17/2.66	   greater_int(pos(s(x)), neg(0)) -> true
6.17/2.66	   greater_int(neg(s(x)), neg(0)) -> false
6.17/2.66	   greater_int(pos(s(x)), neg(s(y))) -> true
6.17/2.66	   greater_int(neg(s(x)), pos(s(y))) -> false
6.17/2.66	   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
6.17/2.66	   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
6.17/2.66	
6.17/2.66	The set Q consists of the following terms:
6.17/2.66	
6.17/2.66	   min(x0, e)
6.17/2.66	   min(x0, ins(x1, x2))
6.17/2.66	   if_1(pair(x0, x1), x2, x3, x4)
6.17/2.66	   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
6.17/2.66	   if_2(pair(x0, x1), x2, x3, x4)
6.17/2.66	   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
6.17/2.66	   greatereq_int(pos(x0), pos(0))
6.17/2.66	   greatereq_int(neg(0), pos(0))
6.17/2.66	   greatereq_int(neg(0), neg(x0))
6.17/2.66	   greatereq_int(pos(x0), neg(x1))
6.17/2.66	   greatereq_int(pos(0), pos(s(x0)))
6.17/2.66	   greatereq_int(neg(x0), pos(s(x1)))
6.17/2.66	   greatereq_int(neg(s(x0)), pos(0))
6.17/2.66	   greatereq_int(neg(s(x0)), neg(0))
6.17/2.66	   greatereq_int(pos(s(x0)), pos(s(x1)))
6.17/2.66	   greatereq_int(neg(s(x0)), neg(s(x1)))
6.17/2.66	   greater_int(pos(0), pos(0))
6.17/2.66	   greater_int(pos(0), neg(0))
6.17/2.66	   greater_int(neg(0), pos(0))
6.17/2.66	   greater_int(neg(0), neg(0))
6.17/2.66	   greater_int(pos(0), pos(s(x0)))
6.17/2.66	   greater_int(neg(0), pos(s(x0)))
6.17/2.66	   greater_int(pos(0), neg(s(x0)))
6.17/2.66	   greater_int(neg(0), neg(s(x0)))
6.17/2.66	   greater_int(pos(s(x0)), pos(0))
6.17/2.66	   greater_int(neg(s(x0)), pos(0))
6.17/2.66	   greater_int(pos(s(x0)), neg(0))
6.17/2.66	   greater_int(neg(s(x0)), neg(0))
6.17/2.66	   greater_int(pos(s(x0)), neg(s(x1)))
6.17/2.66	   greater_int(neg(s(x0)), pos(s(x1)))
6.17/2.66	   greater_int(pos(s(x0)), pos(s(x1)))
6.17/2.66	   greater_int(neg(s(x0)), neg(s(x1)))
6.17/2.66	
6.17/2.66	We have to consider all minimal (P,Q,R)-chains.
6.17/2.66	----------------------------------------
6.17/2.66	
6.17/2.66	(23) DependencyGraphProof (EQUIVALENT)
6.17/2.66	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
6.17/2.66	----------------------------------------
6.17/2.66	
6.17/2.66	(24)
6.17/2.66	TRUE
6.35/2.69	EOF