10.07/3.74	MAYBE
10.32/3.75	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
10.32/3.75	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
10.32/3.75	
10.32/3.75	
10.32/3.75	Quasi decreasingness of the given CTRS could not be shown:
10.32/3.75	
10.32/3.75	(0) CTRS
10.32/3.75	(1) CTRSToQTRSProof [SOUND, 0 ms]
10.32/3.75	(2) QTRS
10.32/3.75	(3) QTRSRRRProof [EQUIVALENT, 71 ms]
10.32/3.75	(4) QTRS
10.32/3.75	(5) DependencyPairsProof [EQUIVALENT, 0 ms]
10.32/3.75	(6) QDP
10.32/3.75	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
10.32/3.75	(8) AND
10.32/3.75	    (9) QDP
10.32/3.75	        (10) UsableRulesProof [EQUIVALENT, 0 ms]
10.32/3.75	        (11) QDP
10.32/3.75	        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
10.32/3.75	        (13) YES
10.32/3.75	    (14) QDP
10.32/3.75	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
10.32/3.75	        (16) QDP
10.32/3.75	        (17) TransformationProof [EQUIVALENT, 0 ms]
10.32/3.75	        (18) QDP
10.32/3.75	        (19) TransformationProof [EQUIVALENT, 0 ms]
10.32/3.75	        (20) QDP
10.32/3.75	        (21) MRRProof [EQUIVALENT, 0 ms]
10.32/3.75	        (22) QDP
10.32/3.75	        (23) TransformationProof [EQUIVALENT, 0 ms]
10.32/3.75	        (24) QDP
10.32/3.75	        (25) NonTerminationLoopProof [COMPLETE, 0 ms]
10.32/3.75	        (26) NO
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(0)
10.32/3.75	Obligation:
10.32/3.75	Conditional term rewrite system:
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(x, 0) -> x
10.32/3.75	   gcd(0, x) -> x
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	   iadd(add(x, y)) -> tp2(x, y)
10.32/3.75	
10.32/3.75	The conditional TRS C consists of the following conditional rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> gcd(x, y) <= iadd(z) -> tp2(x, y)
10.32/3.75	   gcd(y, z) -> gcd(x, y) <= iadd(z) -> tp2(x, y)
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(1) CTRSToQTRSProof (SOUND)
10.32/3.75	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(2)
10.32/3.75	Obligation:
10.32/3.75	Q restricted rewrite system:
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> U1(iadd(z), y)
10.32/3.75	   U1(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(y, z) -> U2(iadd(z), y)
10.32/3.75	   U2(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(x, 0) -> x
10.32/3.75	   gcd(0, x) -> x
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	   iadd(add(x, y)) -> tp2(x, y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(3) QTRSRRRProof (EQUIVALENT)
10.32/3.75	Used ordering:
10.32/3.75	Polynomial interpretation [POLO]:
10.32/3.75	
10.32/3.75	   POL(0) = 0
10.32/3.75	   POL(U1(x_1, x_2)) = x_1 + x_2
10.32/3.75	   POL(U2(x_1, x_2)) = x_1 + 2*x_2
10.32/3.75	   POL(add(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
10.32/3.75	   POL(gcd(x_1, x_2)) = 1 + 2*x_1 + x_2
10.32/3.75	   POL(iadd(x_1)) = 1 + x_1
10.32/3.75	   POL(s(x_1)) = x_1
10.32/3.75	   POL(tp2(x_1, x_2)) = 1 + 2*x_1 + x_2
10.32/3.75	   POL(u1(x_1)) = x_1
10.32/3.75	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
10.32/3.75	
10.32/3.75	   gcd(x, 0) -> x
10.32/3.75	   gcd(0, x) -> x
10.32/3.75	   iadd(add(x, y)) -> tp2(x, y)
10.32/3.75	
10.32/3.75	
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(4)
10.32/3.75	Obligation:
10.32/3.75	Q restricted rewrite system:
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> U1(iadd(z), y)
10.32/3.75	   U1(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(y, z) -> U2(iadd(z), y)
10.32/3.75	   U2(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(5) DependencyPairsProof (EQUIVALENT)
10.32/3.75	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(6)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   GCD(z, y) -> U1^1(iadd(z), y)
10.32/3.75	   GCD(z, y) -> IADD(z)
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(y, z) -> U2^1(iadd(z), y)
10.32/3.75	   GCD(y, z) -> IADD(z)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   IADD(s(z)) -> U1(iadd(z))
10.32/3.75	   IADD(s(z)) -> IADD(z)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> U1(iadd(z), y)
10.32/3.75	   U1(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(y, z) -> U2(iadd(z), y)
10.32/3.75	   U2(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(7) DependencyGraphProof (EQUIVALENT)
10.32/3.75	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(8)
10.32/3.75	Complex Obligation (AND)
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(9)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   IADD(s(z)) -> IADD(z)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> U1(iadd(z), y)
10.32/3.75	   U1(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(y, z) -> U2(iadd(z), y)
10.32/3.75	   U2(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(10) UsableRulesProof (EQUIVALENT)
10.32/3.75	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(11)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   IADD(s(z)) -> IADD(z)
10.32/3.75	
10.32/3.75	R is empty.
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(12) QDPSizeChangeProof (EQUIVALENT)
10.32/3.75	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. 
10.32/3.75	
10.32/3.75	From the DPs we obtained the following set of size-change graphs:
10.32/3.75	*IADD(s(z)) -> IADD(z)
10.32/3.75	The graph contains the following edges 1 > 1
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(13)
10.32/3.75	YES
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(14)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(z, y) -> U1^1(iadd(z), y)
10.32/3.75	   GCD(y, z) -> U2^1(iadd(z), y)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   gcd(z, y) -> U1(iadd(z), y)
10.32/3.75	   U1(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   gcd(y, z) -> U2(iadd(z), y)
10.32/3.75	   U2(tp2(x, y), y) -> gcd(x, y)
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(15) UsableRulesProof (EQUIVALENT)
10.32/3.75	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(16)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(z, y) -> U1^1(iadd(z), y)
10.32/3.75	   GCD(y, z) -> U2^1(iadd(z), y)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(17) TransformationProof (EQUIVALENT)
10.32/3.75	By narrowing [LPAR04] the rule GCD(z, y) -> U1^1(iadd(z), y) at position [0] we obtained the following new rules [LPAR04]:
10.32/3.75	
10.32/3.75	   (GCD(x0, y1) -> U1^1(tp2(0, x0), y1),GCD(x0, y1) -> U1^1(tp2(0, x0), y1))
10.32/3.75	   (GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1),GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1))
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(18)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(y, z) -> U2^1(iadd(z), y)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(x0, y1) -> U1^1(tp2(0, x0), y1)
10.32/3.75	   GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(19) TransformationProof (EQUIVALENT)
10.32/3.75	By narrowing [LPAR04] the rule GCD(y, z) -> U2^1(iadd(z), y) at position [0] we obtained the following new rules [LPAR04]:
10.32/3.75	
10.32/3.75	   (GCD(y0, x0) -> U2^1(tp2(0, x0), y0),GCD(y0, x0) -> U2^1(tp2(0, x0), y0))
10.32/3.75	   (GCD(y0, s(x0)) -> U2^1(u1(iadd(x0)), y0),GCD(y0, s(x0)) -> U2^1(u1(iadd(x0)), y0))
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(20)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(x0, y1) -> U1^1(tp2(0, x0), y1)
10.32/3.75	   GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1)
10.32/3.75	   GCD(y0, x0) -> U2^1(tp2(0, x0), y0)
10.32/3.75	   GCD(y0, s(x0)) -> U2^1(u1(iadd(x0)), y0)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(21) MRRProof (EQUIVALENT)
10.32/3.75	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
10.32/3.75	
10.32/3.75	Strictly oriented dependency pairs:
10.32/3.75	
10.32/3.75	   GCD(y0, s(x0)) -> U2^1(u1(iadd(x0)), y0)
10.32/3.75	
10.32/3.75	
10.32/3.75	Used ordering: Polynomial interpretation [POLO]:
10.32/3.75	
10.32/3.75	   POL(0) = 0
10.32/3.75	   POL(GCD(x_1, x_2)) = x_1 + 2*x_2
10.32/3.75	   POL(U1^1(x_1, x_2)) = x_1 + x_2
10.32/3.75	   POL(U2^1(x_1, x_2)) = x_1 + x_2
10.32/3.75	   POL(iadd(x_1)) = x_1
10.32/3.75	   POL(s(x_1)) = 1 + 2*x_1
10.32/3.75	   POL(tp2(x_1, x_2)) = x_1 + x_2
10.32/3.75	   POL(u1(x_1)) = 1 + 2*x_1
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(22)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   U2^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(x0, y1) -> U1^1(tp2(0, x0), y1)
10.32/3.75	   GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1)
10.32/3.75	   GCD(y0, x0) -> U2^1(tp2(0, x0), y0)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(23) TransformationProof (EQUIVALENT)
10.32/3.75	By instantiating [LPAR04] the rule U2^1(tp2(x, y), y) -> GCD(x, y) we obtained the following new rules [LPAR04]:
10.32/3.75	
10.32/3.75	   (U2^1(tp2(0, y_0), y_0) -> GCD(0, y_0),U2^1(tp2(0, y_0), y_0) -> GCD(0, y_0))
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(24)
10.32/3.75	Obligation:
10.32/3.75	Q DP problem:
10.32/3.75	The TRS P consists of the following rules:
10.32/3.75	
10.32/3.75	   U1^1(tp2(x, y), y) -> GCD(x, y)
10.32/3.75	   GCD(x0, y1) -> U1^1(tp2(0, x0), y1)
10.32/3.75	   GCD(s(x0), y1) -> U1^1(u1(iadd(x0)), y1)
10.32/3.75	   GCD(y0, x0) -> U2^1(tp2(0, x0), y0)
10.32/3.75	   U2^1(tp2(0, y_0), y_0) -> GCD(0, y_0)
10.32/3.75	
10.32/3.75	The TRS R consists of the following rules:
10.32/3.75	
10.32/3.75	   iadd(y) -> tp2(0, y)
10.32/3.75	   iadd(s(z)) -> u1(iadd(z))
10.32/3.75	   u1(tp2(x, y)) -> tp2(s(x), y)
10.32/3.75	
10.32/3.75	Q is empty.
10.32/3.75	We have to consider all minimal (P,Q,R)-chains.
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(25) NonTerminationLoopProof (COMPLETE)
10.32/3.75	We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
10.32/3.75	Found a loop by narrowing to the right:
10.32/3.75	
10.32/3.75	s = U1^1(tp2(x0, y1), y1) evaluates to  t =U1^1(tp2(0, x0), y1)
10.32/3.75	
10.32/3.75	Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
10.32/3.75	* Matcher: [ ]
10.32/3.75	* Semiunifier: [x0 / 0, y1 / 0]
10.32/3.75	
10.32/3.75	--------------------------------------------------------------------------------
10.32/3.75	Rewriting sequence
10.32/3.75	
10.32/3.75	U1^1(tp2(0, 0), 0) -> GCD(0, 0)
10.32/3.75	 with rule U1^1(tp2(x, y), y) -> GCD(x, y) and matcher [x / 0, y / 0].
10.32/3.75	
10.32/3.75	GCD(0, 0) -> U1^1(tp2(0, 0), 0)
10.32/3.75	with rule GCD(x0, y1) -> U1^1(tp2(0, x0), y1) at position [] and matcher [x0 / 0, y1 / 0]
10.32/3.75	
10.32/3.75	Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence
10.32/3.75	
10.32/3.75	
10.32/3.75	All these steps are and every following step will be a correct step w.r.t to Q.
10.32/3.75	
10.32/3.75	
10.32/3.75	
10.32/3.75	
10.32/3.75	----------------------------------------
10.32/3.75	
10.32/3.75	(26)
10.32/3.75	NO
10.35/3.79	EOF