3.69/1.73	YES
3.69/1.74	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.69/1.74	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.69/1.74	
3.69/1.74	
3.69/1.74	Quasi decreasingness of the given CTRS could be proven:
3.69/1.74	
3.69/1.74	(0) CTRS
3.69/1.74	(1) CTRSToQTRSProof [SOUND, 0 ms]
3.69/1.74	(2) QTRS
3.69/1.74	(3) QTRSRRRProof [EQUIVALENT, 63 ms]
3.69/1.74	(4) QTRS
3.69/1.74	(5) QTRSRRRProof [EQUIVALENT, 12 ms]
3.69/1.74	(6) QTRS
3.69/1.74	(7) QTRSRRRProof [EQUIVALENT, 0 ms]
3.69/1.74	(8) QTRS
3.69/1.74	(9) RisEmptyProof [EQUIVALENT, 0 ms]
3.69/1.74	(10) YES
3.69/1.74	
3.69/1.74	
3.69/1.74	----------------------------------------
3.69/1.74	
3.69/1.74	(0)
3.69/1.74	Obligation:
3.69/1.74	Conditional term rewrite system:
3.69/1.74	The TRS R consists of the following rules:
3.69/1.74	
3.69/1.74	   size(empty) -> 0
3.69/1.74	   size(push(x, y)) -> s(size(x))
3.69/1.74	   m -> s(s(s(s(0))))
3.69/1.74	   pop(empty) -> empty
3.69/1.74	   top(empty) -> eentry
3.69/1.74	   le(x, 0) -> false
3.69/1.74	   le(0, s(x)) -> true
3.69/1.74	   le(s(x), s(y)) -> le(x, y)
3.69/1.74	
3.69/1.74	The conditional TRS C consists of the following conditional rules:
3.69/1.74	
3.69/1.74	   pop(push(x, y)) -> x <= le(size(x), m) -> true
3.69/1.74	   top(push(x, y)) -> y <= le(size(x), m) -> true
3.69/1.74	
3.69/1.74	
3.69/1.74	----------------------------------------
3.69/1.74	
3.69/1.74	(1) CTRSToQTRSProof (SOUND)
3.69/1.74	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
3.69/1.74	----------------------------------------
3.69/1.74	
3.69/1.74	(2)
3.69/1.74	Obligation:
3.69/1.74	Q restricted rewrite system:
3.69/1.74	The TRS R consists of the following rules:
3.69/1.74	
3.69/1.74	   pop(push(x, y)) -> U1(le(size(x), m), x)
3.69/1.74	   U1(true, x) -> x
3.69/1.74	   top(push(x, y)) -> U2(le(size(x), m), y)
3.69/1.74	   U2(true, y) -> y
3.69/1.74	   size(empty) -> 0
3.69/1.74	   size(push(x, y)) -> s(size(x))
3.69/1.74	   m -> s(s(s(s(0))))
3.69/1.74	   pop(empty) -> empty
3.69/1.74	   top(empty) -> eentry
3.69/1.74	   le(x, 0) -> false
3.69/1.74	   le(0, s(x)) -> true
3.69/1.74	   le(s(x), s(y)) -> le(x, y)
3.69/1.74	
3.69/1.74	Q is empty.
3.69/1.74	
3.69/1.74	----------------------------------------
3.69/1.74	
3.69/1.74	(3) QTRSRRRProof (EQUIVALENT)
3.69/1.74	Used ordering:
3.69/1.74	Polynomial interpretation [POLO]:
3.69/1.74	
3.69/1.74	   POL(0) = 1
3.69/1.74	   POL(U1(x_1, x_2)) = x_1 + x_2
3.69/1.74	   POL(U2(x_1, x_2)) = x_1 + 2*x_2
3.69/1.74	   POL(eentry) = 1
3.69/1.74	   POL(empty) = 2
3.69/1.74	   POL(false) = 0
3.69/1.74	   POL(le(x_1, x_2)) = 2*x_1 + x_2
3.69/1.74	   POL(m) = 1
3.69/1.74	   POL(pop(x_1)) = 1 + 2*x_1
3.69/1.74	   POL(push(x_1, x_2)) = 2*x_1 + x_2
3.69/1.74	   POL(s(x_1)) = x_1
3.69/1.74	   POL(size(x_1)) = x_1
3.69/1.74	   POL(top(x_1)) = 2 + 2*x_1
3.69/1.74	   POL(true) = 1
3.69/1.75	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.69/1.75	
3.69/1.75	   U1(true, x) -> x
3.69/1.75	   top(push(x, y)) -> U2(le(size(x), m), y)
3.69/1.75	   U2(true, y) -> y
3.69/1.75	   size(empty) -> 0
3.69/1.75	   pop(empty) -> empty
3.69/1.75	   top(empty) -> eentry
3.69/1.75	   le(x, 0) -> false
3.69/1.75	   le(0, s(x)) -> true
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(4)
3.69/1.75	Obligation:
3.69/1.75	Q restricted rewrite system:
3.69/1.75	The TRS R consists of the following rules:
3.69/1.75	
3.69/1.75	   pop(push(x, y)) -> U1(le(size(x), m), x)
3.69/1.75	   size(push(x, y)) -> s(size(x))
3.69/1.75	   m -> s(s(s(s(0))))
3.69/1.75	   le(s(x), s(y)) -> le(x, y)
3.69/1.75	
3.69/1.75	Q is empty.
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(5) QTRSRRRProof (EQUIVALENT)
3.69/1.75	Used ordering:
3.69/1.75	Polynomial interpretation [POLO]:
3.69/1.75	
3.69/1.75	   POL(0) = 0
3.69/1.75	   POL(U1(x_1, x_2)) = x_1 + 2*x_2
3.69/1.75	   POL(le(x_1, x_2)) = 2*x_1 + x_2
3.69/1.75	   POL(m) = 1
3.69/1.75	   POL(pop(x_1)) = 2 + 2*x_1
3.69/1.75	   POL(push(x_1, x_2)) = 1 + 2*x_1 + x_2
3.69/1.75	   POL(s(x_1)) = x_1
3.69/1.75	   POL(size(x_1)) = 1 + x_1
3.69/1.75	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.69/1.75	
3.69/1.75	   pop(push(x, y)) -> U1(le(size(x), m), x)
3.69/1.75	   size(push(x, y)) -> s(size(x))
3.69/1.75	   m -> s(s(s(s(0))))
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(6)
3.69/1.75	Obligation:
3.69/1.75	Q restricted rewrite system:
3.69/1.75	The TRS R consists of the following rules:
3.69/1.75	
3.69/1.75	   le(s(x), s(y)) -> le(x, y)
3.69/1.75	
3.69/1.75	Q is empty.
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(7) QTRSRRRProof (EQUIVALENT)
3.69/1.75	Used ordering:
3.69/1.75	Knuth-Bendix order [KBO] with precedence:s_1 > le_2
3.69/1.75	
3.69/1.75	and weight map:
3.69/1.75	
3.69/1.75	   s_1=0
3.69/1.75	   le_2=0
3.69/1.75	
3.69/1.75	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.69/1.75	
3.69/1.75	   le(s(x), s(y)) -> le(x, y)
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(8)
3.69/1.75	Obligation:
3.69/1.75	Q restricted rewrite system:
3.69/1.75	R is empty.
3.69/1.75	Q is empty.
3.69/1.75	
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(9) RisEmptyProof (EQUIVALENT)
3.69/1.75	The TRS R is empty. Hence, termination is trivially proven.
3.69/1.75	----------------------------------------
3.69/1.75	
3.69/1.75	(10)
3.69/1.75	YES
3.89/1.78	EOF