4.92/2.21	MAYBE
4.92/2.22	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.92/2.22	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.92/2.22	
4.92/2.22	
4.92/2.22	Quasi decreasingness of the given CTRS could not be shown:
4.92/2.22	
4.92/2.22	(0) CTRS
4.92/2.22	(1) CTRSToQTRSProof [SOUND, 0 ms]
4.92/2.22	(2) QTRS
4.92/2.22	(3) QTRSRRRProof [EQUIVALENT, 61 ms]
4.92/2.22	(4) QTRS
4.92/2.22	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
4.92/2.22	(6) QTRS
4.92/2.22	(7) AAECC Innermost [EQUIVALENT, 0 ms]
4.92/2.22	(8) QTRS
4.92/2.22	(9) DependencyPairsProof [EQUIVALENT, 14 ms]
4.92/2.22	(10) QDP
4.92/2.22	(11) UsableRulesProof [EQUIVALENT, 0 ms]
4.92/2.22	(12) QDP
4.92/2.22	(13) QReductionProof [EQUIVALENT, 0 ms]
4.92/2.22	(14) QDP
4.92/2.22	(15) NonTerminationLoopProof [COMPLETE, 0 ms]
4.92/2.22	(16) NO
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(0)
4.92/2.22	Obligation:
4.92/2.22	Conditional term rewrite system:
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   g(s(x)) -> x
4.92/2.22	   h(s(x)) -> x
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	The conditional TRS C consists of the following conditional rules:
4.92/2.22	
4.92/2.22	   f(x, y) -> g(s(x)) <= c(g(x)) -> c(a)
4.92/2.22	   f(x, y) -> h(s(x)) <= c(h(x)) -> c(a)
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(1) CTRSToQTRSProof (SOUND)
4.92/2.22	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(2)
4.92/2.22	Obligation:
4.92/2.22	Q restricted rewrite system:
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   f(x, y) -> U1(c(g(x)), x)
4.92/2.22	   U1(c(a), x) -> g(s(x))
4.92/2.22	   f(x, y) -> U2(c(h(x)), x)
4.92/2.22	   U2(c(a), x) -> h(s(x))
4.92/2.22	   g(s(x)) -> x
4.92/2.22	   h(s(x)) -> x
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	Q is empty.
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(3) QTRSRRRProof (EQUIVALENT)
4.92/2.22	Used ordering:
4.92/2.22	Polynomial interpretation [POLO]:
4.92/2.22	
4.92/2.22	   POL(U1(x_1, x_2)) = x_1 + x_2
4.92/2.22	   POL(U2(x_1, x_2)) = x_1 + x_2
4.92/2.22	   POL(a) = 0
4.92/2.22	   POL(b) = 0
4.92/2.22	   POL(c(x_1)) = x_1
4.92/2.22	   POL(f(x_1, x_2)) = 1 + 2*x_1 + x_2
4.92/2.22	   POL(g(x_1)) = x_1
4.92/2.22	   POL(h(x_1)) = x_1
4.92/2.22	   POL(s(x_1)) = x_1
4.92/2.22	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.92/2.22	
4.92/2.22	   f(x, y) -> U1(c(g(x)), x)
4.92/2.22	   f(x, y) -> U2(c(h(x)), x)
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(4)
4.92/2.22	Obligation:
4.92/2.22	Q restricted rewrite system:
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   U1(c(a), x) -> g(s(x))
4.92/2.22	   U2(c(a), x) -> h(s(x))
4.92/2.22	   g(s(x)) -> x
4.92/2.22	   h(s(x)) -> x
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	Q is empty.
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(5) QTRSRRRProof (EQUIVALENT)
4.92/2.22	Used ordering:
4.92/2.22	Knuth-Bendix order [KBO] with precedence:U2_2 > s_1 > g_1 > b > h_1 > a > U1_2 > c_1
4.92/2.22	
4.92/2.22	and weight map:
4.92/2.22	
4.92/2.22	   a=1
4.92/2.22	   b=1
4.92/2.22	   c_1=1
4.92/2.22	   g_1=1
4.92/2.22	   s_1=1
4.92/2.22	   h_1=1
4.92/2.22	   U1_2=1
4.92/2.22	   U2_2=1
4.92/2.22	
4.92/2.22	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.92/2.22	
4.92/2.22	   U1(c(a), x) -> g(s(x))
4.92/2.22	   U2(c(a), x) -> h(s(x))
4.92/2.22	   g(s(x)) -> x
4.92/2.22	   h(s(x)) -> x
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(6)
4.92/2.22	Obligation:
4.92/2.22	Q restricted rewrite system:
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	Q is empty.
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(7) AAECC Innermost (EQUIVALENT)
4.92/2.22	We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is none
4.92/2.22	
4.92/2.22	The TRS R 2 is 
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	The signature Sigma is {b}
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(8)
4.92/2.22	Obligation:
4.92/2.22	Q restricted rewrite system:
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	The set Q consists of the following terms:
4.92/2.22	
4.92/2.22	   b
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(9) DependencyPairsProof (EQUIVALENT)
4.92/2.22	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(10)
4.92/2.22	Obligation:
4.92/2.22	Q DP problem:
4.92/2.22	The TRS P consists of the following rules:
4.92/2.22	
4.92/2.22	   B -> B
4.92/2.22	
4.92/2.22	The TRS R consists of the following rules:
4.92/2.22	
4.92/2.22	   b -> b
4.92/2.22	
4.92/2.22	The set Q consists of the following terms:
4.92/2.22	
4.92/2.22	   b
4.92/2.22	
4.92/2.22	We have to consider all minimal (P,Q,R)-chains.
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(11) UsableRulesProof (EQUIVALENT)
4.92/2.22	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.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(12)
4.92/2.22	Obligation:
4.92/2.22	Q DP problem:
4.92/2.22	The TRS P consists of the following rules:
4.92/2.22	
4.92/2.22	   B -> B
4.92/2.22	
4.92/2.22	R is empty.
4.92/2.22	The set Q consists of the following terms:
4.92/2.22	
4.92/2.22	   b
4.92/2.22	
4.92/2.22	We have to consider all minimal (P,Q,R)-chains.
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(13) QReductionProof (EQUIVALENT)
4.92/2.22	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.92/2.22	
4.92/2.22	   b
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(14)
4.92/2.22	Obligation:
4.92/2.22	Q DP problem:
4.92/2.22	The TRS P consists of the following rules:
4.92/2.22	
4.92/2.22	   B -> B
4.92/2.22	
4.92/2.22	R is empty.
4.92/2.22	Q is empty.
4.92/2.22	We have to consider all minimal (P,Q,R)-chains.
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(15) NonTerminationLoopProof (COMPLETE)
4.92/2.22	We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
4.92/2.22	Found a loop by semiunifying a rule from P directly.
4.92/2.22	
4.92/2.22	s = B evaluates to  t =B
4.92/2.22	
4.92/2.22	Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
4.92/2.22	* Matcher: [ ]
4.92/2.22	* Semiunifier: [ ]
4.92/2.22	
4.92/2.22	--------------------------------------------------------------------------------
4.92/2.22	Rewriting sequence
4.92/2.22	
4.92/2.22	The DP semiunifies directly so there is only one rewrite step from B to B.
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	
4.92/2.22	----------------------------------------
4.92/2.22	
4.92/2.22	(16)
4.92/2.22	NO
5.03/2.28	EOF