4.30/2.10	YES
4.30/2.11	proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs
4.30/2.11	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.30/2.11	
4.30/2.11	
4.30/2.11	Termination of the given ITRS could be proven:
4.30/2.11	
4.30/2.11	(0) ITRS
4.30/2.11	(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
4.30/2.11	(2) IDP
4.30/2.11	(3) UsableRulesProof [EQUIVALENT, 0 ms]
4.30/2.11	(4) IDP
4.30/2.11	(5) IDPtoQDPProof [SOUND, 34 ms]
4.30/2.11	(6) QDP
4.30/2.11	(7) QReductionProof [EQUIVALENT, 0 ms]
4.30/2.11	(8) QDP
4.30/2.11	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.30/2.11	(10) YES
4.30/2.11	
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(0)
4.30/2.11	Obligation:
4.30/2.11	ITRS problem:
4.30/2.11	
4.30/2.11	The following function symbols are pre-defined:
4.30/2.11	<<<
4.30/2.11	 & 	~ 	Bwand: (Integer, Integer) -> Integer
4.30/2.11	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
4.30/2.11	 | 	~ 	Bwor: (Integer, Integer) -> Integer
4.30/2.11	 / 	~ 	Div: (Integer, Integer) -> Integer
4.30/2.11	 != 	~ 	Neq: (Integer, Integer) -> Boolean
4.30/2.11	 = 	~ 	Eq: (Integer, Integer) -> Boolean
4.30/2.11	 <= 	~ 	Le: (Integer, Integer) -> Boolean
4.30/2.11	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
4.30/2.11	 % 	~ 	Mod: (Integer, Integer) -> Integer
4.30/2.11	 + 	~ 	Add: (Integer, Integer) -> Integer
4.30/2.11	 > 	~ 	Gt: (Integer, Integer) -> Boolean
4.30/2.11	 -1 	~ 	UnaryMinus: (Integer) -> Integer
4.30/2.11	 < 	~ 	Lt: (Integer, Integer) -> Boolean
4.30/2.11	 - 	~ 	Sub: (Integer, Integer) -> Integer
4.30/2.11	 ~ 	~ 	Bwnot: (Integer) -> Integer
4.30/2.11	 * 	~ 	Mul: (Integer, Integer) -> Integer
4.30/2.11	>>>
4.30/2.11	
4.30/2.11	The TRS R consists of the following rules:
4.30/2.11	g(x, cons(y, ys)) -> cons(x + y, g(x, ys))
4.30/2.11	The set Q consists of the following terms:
4.30/2.11	g(x0, cons(x1, x2))
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(1) ITRStoIDPProof (EQUIVALENT)
4.30/2.11	Added dependency pairs
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(2)
4.30/2.11	Obligation:
4.30/2.11	IDP problem:
4.30/2.11	The following function symbols are pre-defined:
4.30/2.11	<<<
4.30/2.11	 & 	~ 	Bwand: (Integer, Integer) -> Integer
4.30/2.11	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
4.30/2.11	 | 	~ 	Bwor: (Integer, Integer) -> Integer
4.30/2.11	 / 	~ 	Div: (Integer, Integer) -> Integer
4.30/2.11	 != 	~ 	Neq: (Integer, Integer) -> Boolean
4.30/2.11	 = 	~ 	Eq: (Integer, Integer) -> Boolean
4.30/2.11	 <= 	~ 	Le: (Integer, Integer) -> Boolean
4.30/2.11	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
4.30/2.11	 % 	~ 	Mod: (Integer, Integer) -> Integer
4.30/2.11	 + 	~ 	Add: (Integer, Integer) -> Integer
4.30/2.11	 > 	~ 	Gt: (Integer, Integer) -> Boolean
4.30/2.11	 -1 	~ 	UnaryMinus: (Integer) -> Integer
4.30/2.11	 < 	~ 	Lt: (Integer, Integer) -> Boolean
4.30/2.11	 - 	~ 	Sub: (Integer, Integer) -> Integer
4.30/2.11	 ~ 	~ 	Bwnot: (Integer) -> Integer
4.30/2.11	 * 	~ 	Mul: (Integer, Integer) -> Integer
4.30/2.11	>>>
4.30/2.11	
4.30/2.11	
4.30/2.11	The following domains are used:
4.30/2.11	   Integer
4.30/2.11	
4.30/2.11	The ITRS R consists of the following rules:
4.30/2.11	g(x, cons(y, ys)) -> cons(x + y, g(x, ys))
4.30/2.11	
4.30/2.11	The integer pair graph contains the following rules and edges:
4.30/2.11	(0): G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
4.30/2.11	
4.30/2.11	   (0) -> (0), if (x[0] ->^* x[0]' & ys[0] ->^* cons(y[0]', ys[0]'))
4.30/2.11	
4.30/2.11	The set Q consists of the following terms:
4.30/2.11	g(x0, cons(x1, x2))
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(3) UsableRulesProof (EQUIVALENT)
4.30/2.11	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(4)
4.30/2.11	Obligation:
4.30/2.11	IDP problem:
4.30/2.11	The following function symbols are pre-defined:
4.30/2.11	<<<
4.30/2.11	 & 	~ 	Bwand: (Integer, Integer) -> Integer
4.30/2.11	 >= 	~ 	Ge: (Integer, Integer) -> Boolean
4.30/2.11	 | 	~ 	Bwor: (Integer, Integer) -> Integer
4.30/2.11	 / 	~ 	Div: (Integer, Integer) -> Integer
4.30/2.11	 != 	~ 	Neq: (Integer, Integer) -> Boolean
4.30/2.11	 = 	~ 	Eq: (Integer, Integer) -> Boolean
4.30/2.11	 <= 	~ 	Le: (Integer, Integer) -> Boolean
4.30/2.11	 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
4.30/2.11	 % 	~ 	Mod: (Integer, Integer) -> Integer
4.30/2.11	 + 	~ 	Add: (Integer, Integer) -> Integer
4.30/2.11	 > 	~ 	Gt: (Integer, Integer) -> Boolean
4.30/2.11	 -1 	~ 	UnaryMinus: (Integer) -> Integer
4.30/2.11	 < 	~ 	Lt: (Integer, Integer) -> Boolean
4.30/2.11	 - 	~ 	Sub: (Integer, Integer) -> Integer
4.30/2.11	 ~ 	~ 	Bwnot: (Integer) -> Integer
4.30/2.11	 * 	~ 	Mul: (Integer, Integer) -> Integer
4.30/2.11	>>>
4.30/2.11	
4.30/2.11	
4.30/2.11	The following domains are used:
4.30/2.11	none
4.30/2.11	
4.30/2.11	R is empty.
4.30/2.11	
4.30/2.11	The integer pair graph contains the following rules and edges:
4.30/2.11	(0): G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
4.30/2.11	
4.30/2.11	   (0) -> (0), if (x[0] ->^* x[0]' & ys[0] ->^* cons(y[0]', ys[0]'))
4.30/2.11	
4.30/2.11	The set Q consists of the following terms:
4.30/2.11	g(x0, cons(x1, x2))
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(5) IDPtoQDPProof (SOUND)
4.30/2.11	Represented integers and predefined function symbols by Terms
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(6)
4.30/2.11	Obligation:
4.30/2.11	Q DP problem:
4.30/2.11	The TRS P consists of the following rules:
4.30/2.11	
4.30/2.11	   G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
4.30/2.11	
4.30/2.11	R is empty.
4.30/2.11	The set Q consists of the following terms:
4.30/2.11	
4.30/2.11	   g(x0, cons(x1, x2))
4.30/2.11	
4.30/2.11	We have to consider all minimal (P,Q,R)-chains.
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(7) QReductionProof (EQUIVALENT)
4.30/2.11	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.30/2.11	
4.30/2.11	   g(x0, cons(x1, x2))
4.30/2.11	
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(8)
4.30/2.11	Obligation:
4.30/2.11	Q DP problem:
4.30/2.11	The TRS P consists of the following rules:
4.30/2.11	
4.30/2.11	   G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
4.30/2.11	
4.30/2.11	R is empty.
4.30/2.11	Q is empty.
4.30/2.11	We have to consider all minimal (P,Q,R)-chains.
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(9) QDPSizeChangeProof (EQUIVALENT)
4.30/2.11	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
4.30/2.11	
4.30/2.11	From the DPs we obtained the following set of size-change graphs:
4.30/2.11	*G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
4.30/2.11	The graph contains the following edges 1 >= 1, 2 > 2
4.30/2.11	
4.30/2.11	
4.30/2.11	----------------------------------------
4.30/2.11	
4.30/2.11	(10)
4.30/2.11	YES
4.30/2.14	EOF