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