3.85/1.85	MAYBE
3.85/1.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.85/1.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.85/1.87	
3.85/1.87	
3.85/1.87	Quasi decreasingness of the given CTRS could not be shown:
3.85/1.87	
3.85/1.87	(0) CTRS
3.85/1.87	(1) CTRSToQTRSProof [SOUND, 0 ms]
3.85/1.87	(2) QTRS
3.85/1.87	(3) AAECC Innermost [EQUIVALENT, 1 ms]
3.85/1.87	(4) QTRS
3.85/1.87	(5) DependencyPairsProof [EQUIVALENT, 0 ms]
3.85/1.87	(6) QDP
3.85/1.87	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
3.85/1.87	(8) QDP
3.85/1.87	(9) UsableRulesProof [EQUIVALENT, 0 ms]
3.85/1.87	(10) QDP
3.85/1.87	(11) QReductionProof [EQUIVALENT, 0 ms]
3.85/1.87	(12) QDP
3.85/1.87	(13) TransformationProof [EQUIVALENT, 0 ms]
3.85/1.87	(14) QDP
3.85/1.87	(15) TransformationProof [EQUIVALENT, 0 ms]
3.85/1.87	(16) QDP
3.85/1.87	(17) UsableRulesProof [EQUIVALENT, 0 ms]
3.85/1.87	(18) QDP
3.85/1.87	(19) QReductionProof [EQUIVALENT, 0 ms]
3.85/1.87	(20) QDP
3.85/1.87	(21) TransformationProof [EQUIVALENT, 0 ms]
3.85/1.87	(22) QDP
3.85/1.87	(23) QReductionProof [EQUIVALENT, 0 ms]
3.85/1.87	(24) QDP
3.85/1.87	(25) NonTerminationLoopProof [COMPLETE, 0 ms]
3.85/1.87	(26) NO
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(0)
3.85/1.87	Obligation:
3.85/1.87	Conditional term rewrite system:
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	The conditional TRS C consists of the following conditional rules:
3.85/1.87	
3.85/1.87	   f(x) -> c <= a -> b
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(1) CTRSToQTRSProof (SOUND)
3.85/1.87	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(2)
3.85/1.87	Obligation:
3.85/1.87	Q restricted rewrite system:
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	   U1(b) -> c
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	Q is empty.
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(3) AAECC Innermost (EQUIVALENT)
3.85/1.87	We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	   U1(b) -> c
3.85/1.87	
3.85/1.87	The TRS R 2 is 
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	The signature Sigma is {g_2}
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(4)
3.85/1.87	Obligation:
3.85/1.87	Q restricted rewrite system:
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	   U1(b) -> c
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	   g(x0, x0)
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(5) DependencyPairsProof (EQUIVALENT)
3.85/1.87	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(6)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   F(x) -> U1^1(a)
3.85/1.87	   G(x, x) -> G(f(a), f(b))
3.85/1.87	   G(x, x) -> F(a)
3.85/1.87	   G(x, x) -> F(b)
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	   U1(b) -> c
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	   g(x0, x0)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(7) DependencyGraphProof (EQUIVALENT)
3.85/1.87	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(8)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(f(a), f(b))
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	   U1(b) -> c
3.85/1.87	   g(x, x) -> g(f(a), f(b))
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	   g(x0, x0)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(9) UsableRulesProof (EQUIVALENT)
3.85/1.87	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.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(10)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(f(a), f(b))
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	   g(x0, x0)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(11) QReductionProof (EQUIVALENT)
3.85/1.87	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.85/1.87	
3.85/1.87	   g(x0, x0)
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(12)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(f(a), f(b))
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(13) TransformationProof (EQUIVALENT)
3.85/1.87	By rewriting [LPAR04] the rule G(x, x) -> G(f(a), f(b)) at position [0] we obtained the following new rules [LPAR04]:
3.85/1.87	
3.85/1.87	   (G(x, x) -> G(U1(a), f(b)),G(x, x) -> G(U1(a), f(b)))
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(14)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(U1(a), f(b))
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(15) TransformationProof (EQUIVALENT)
3.85/1.87	By rewriting [LPAR04] the rule G(x, x) -> G(U1(a), f(b)) at position [1] we obtained the following new rules [LPAR04]:
3.85/1.87	
3.85/1.87	   (G(x, x) -> G(U1(a), U1(a)),G(x, x) -> G(U1(a), U1(a)))
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(16)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	The TRS R consists of the following rules:
3.85/1.87	
3.85/1.87	   f(x) -> U1(a)
3.85/1.87	
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(17) UsableRulesProof (EQUIVALENT)
3.85/1.87	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.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(18)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	R is empty.
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(19) QReductionProof (EQUIVALENT)
3.85/1.87	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.85/1.87	
3.85/1.87	   f(x0)
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(20)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(x, x) -> G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	R is empty.
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(21) TransformationProof (EQUIVALENT)
3.85/1.87	By instantiating [LPAR04] the rule G(x, x) -> G(U1(a), U1(a)) we obtained the following new rules [LPAR04]:
3.85/1.87	
3.85/1.87	   (G(U1(a), U1(a)) -> G(U1(a), U1(a)),G(U1(a), U1(a)) -> G(U1(a), U1(a)))
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(22)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(U1(a), U1(a)) -> G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	R is empty.
3.85/1.87	The set Q consists of the following terms:
3.85/1.87	
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	We have to consider all minimal (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(23) QReductionProof (EQUIVALENT)
3.85/1.87	We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN].
3.85/1.87	
3.85/1.87	   U1(b)
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(24)
3.85/1.87	Obligation:
3.85/1.87	Q DP problem:
3.85/1.87	The TRS P consists of the following rules:
3.85/1.87	
3.85/1.87	   G(U1(a), U1(a)) -> G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	R is empty.
3.85/1.87	Q is empty.
3.85/1.87	We have to consider all (P,Q,R)-chains.
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(25) NonTerminationLoopProof (COMPLETE)
3.85/1.87	We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
3.85/1.87	Found a loop by semiunifying a rule from P directly.
3.85/1.87	
3.85/1.87	s = G(U1(a), U1(a)) evaluates to  t =G(U1(a), U1(a))
3.85/1.87	
3.85/1.87	Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
3.85/1.87	* Matcher: [ ]
3.85/1.87	* Semiunifier: [ ]
3.85/1.87	
3.85/1.87	--------------------------------------------------------------------------------
3.85/1.87	Rewriting sequence
3.85/1.87	
3.85/1.87	The DP semiunifies directly so there is only one rewrite step from G(U1(a), U1(a)) to G(U1(a), U1(a)).
3.85/1.87	
3.85/1.87	
3.85/1.87	
3.85/1.87	
3.85/1.87	----------------------------------------
3.85/1.87	
3.85/1.87	(26)
3.85/1.87	NO
3.85/1.90	EOF