3.42/1.69	YES
3.42/1.71	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.42/1.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.42/1.71	
3.42/1.71	
3.42/1.71	Termination w.r.t. Q of the given QTRS could be proven:
3.42/1.71	
3.42/1.71	(0) QTRS
3.42/1.71	(1) QTRS Reverse [EQUIVALENT, 0 ms]
3.42/1.71	(2) QTRS
3.42/1.71	(3) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms]
3.42/1.71	(4) YES
3.42/1.71	
3.42/1.71	
3.42/1.71	----------------------------------------
3.42/1.71	
3.42/1.71	(0)
3.42/1.71	Obligation:
3.42/1.71	Q restricted rewrite system:
3.42/1.71	The TRS R consists of the following rules:
3.42/1.71	
3.42/1.71	   q0(a(x1)) -> x(q1(x1))
3.42/1.71	   q1(a(x1)) -> a(q1(x1))
3.42/1.71	   q1(y(x1)) -> y(q1(x1))
3.42/1.71	   a(q1(b(x1))) -> q2(a(y(x1)))
3.42/1.71	   a(q2(a(x1))) -> q2(a(a(x1)))
3.42/1.71	   a(q2(y(x1))) -> q2(a(y(x1)))
3.42/1.71	   y(q1(b(x1))) -> q2(y(y(x1)))
3.42/1.71	   y(q2(a(x1))) -> q2(y(a(x1)))
3.42/1.71	   y(q2(y(x1))) -> q2(y(y(x1)))
3.42/1.71	   q2(x(x1)) -> x(q0(x1))
3.42/1.71	   q0(y(x1)) -> y(q3(x1))
3.42/1.71	   q3(y(x1)) -> y(q3(x1))
3.42/1.71	   q3(bl(x1)) -> bl(q4(x1))
3.42/1.71	
3.42/1.71	Q is empty.
3.42/1.71	
3.42/1.71	----------------------------------------
3.42/1.71	
3.42/1.71	(1) QTRS Reverse (EQUIVALENT)
3.42/1.71	We applied the QTRS Reverse Processor [REVERSE].
3.42/1.71	----------------------------------------
3.42/1.71	
3.42/1.71	(2)
3.42/1.71	Obligation:
3.42/1.71	Q restricted rewrite system:
3.42/1.71	The TRS R consists of the following rules:
3.42/1.71	
3.42/1.71	   a(q0(x1)) -> q1(x(x1))
3.42/1.71	   a(q1(x1)) -> q1(a(x1))
3.42/1.71	   y(q1(x1)) -> q1(y(x1))
3.42/1.71	   b(q1(a(x1))) -> y(a(q2(x1)))
3.42/1.71	   a(q2(a(x1))) -> a(a(q2(x1)))
3.42/1.71	   y(q2(a(x1))) -> y(a(q2(x1)))
3.42/1.71	   b(q1(y(x1))) -> y(y(q2(x1)))
3.42/1.71	   a(q2(y(x1))) -> a(y(q2(x1)))
3.42/1.71	   y(q2(y(x1))) -> y(y(q2(x1)))
3.42/1.71	   x(q2(x1)) -> q0(x(x1))
3.42/1.71	   y(q0(x1)) -> q3(y(x1))
3.42/1.71	   y(q3(x1)) -> q3(y(x1))
3.42/1.71	   bl(q3(x1)) -> q4(bl(x1))
3.42/1.71	
3.42/1.71	Q is empty.
3.42/1.71	
3.42/1.71	----------------------------------------
3.42/1.71	
3.42/1.71	(3) RFCMatchBoundsTRSProof (EQUIVALENT)
3.42/1.71	Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R.
3.42/1.71	The following rules were used to construct the certificate:
3.42/1.71	
3.42/1.71	   a(q0(x1)) -> q1(x(x1))
3.42/1.71	   a(q1(x1)) -> q1(a(x1))
3.42/1.71	   y(q1(x1)) -> q1(y(x1))
3.42/1.71	   b(q1(a(x1))) -> y(a(q2(x1)))
3.42/1.71	   a(q2(a(x1))) -> a(a(q2(x1)))
3.42/1.71	   y(q2(a(x1))) -> y(a(q2(x1)))
3.42/1.71	   b(q1(y(x1))) -> y(y(q2(x1)))
3.42/1.71	   a(q2(y(x1))) -> a(y(q2(x1)))
3.42/1.71	   y(q2(y(x1))) -> y(y(q2(x1)))
3.42/1.71	   x(q2(x1)) -> q0(x(x1))
3.42/1.71	   y(q0(x1)) -> q3(y(x1))
3.42/1.71	   y(q3(x1)) -> q3(y(x1))
3.42/1.71	   bl(q3(x1)) -> q4(bl(x1))
3.42/1.71	
3.42/1.71	The certificate found is represented by the following graph.
3.42/1.71	The certificate consists of the following enumerated nodes:
3.42/1.71	43, 44, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64
3.42/1.71	
3.42/1.71	Node 43 is start node and node 44 is final node.
3.42/1.71	
3.42/1.71	Those nodes are connected through the following edges:
3.42/1.71	
3.42/1.71	* 43 to 53 labelled q1_1(0), q0_1(0), q3_1(0)* 43 to 54 labelled y_1(0), a_1(0)* 43 to 56 labelled y_1(0), a_1(0)* 43 to 58 labelled q4_1(0)* 44 to 44 labelled #_1(0)* 53 to 44 labelled x_1(0), a_1(0), y_1(0)* 53 to 59 labelled q0_1(1), q1_1(1), q3_1(1)* 53 to 60 labelled a_1(1), y_1(1)* 53 to 62 labelled a_1(1), y_1(1)* 54 to 55 labelled a_1(0)* 54 to 60 labelled a_1(1)* 54 to 62 labelled a_1(1)* 55 to 44 labelled q2_1(0)* 56 to 57 labelled y_1(0)* 56 to 60 labelled y_1(1)* 56 to 62 labelled y_1(1)* 57 to 44 labelled q2_1(0)* 58 to 44 labelled bl_1(0)* 58 to 64 labelled q4_1(1)* 59 to 44 labelled x_1(1), a_1(1), y_1(1)* 59 to 59 labelled q0_1(1), q1_1(1), q3_1(1)* 59 to 60 labelled a_1(1), y_1(1)* 59 to 62 labelled a_1(1), y_1(1)* 60 to 61 labelled a_1(1)* 60 to 60 labelled a_1(1)* 60 to 62 labelled a_1(1)* 61 to 44 labelled q2_1(1)* 62 to 63 labelled y_1(1)* 62 to 60 labelled y_1(1)* 62 to 62 labelled y_1(1)* 63 to 44 labelled q2_1(1)* 64 to 44 labelled bl_1(1)* 64 to 64 labelled q4_1(1)
3.42/1.71	
3.42/1.71	
3.42/1.71	----------------------------------------
3.42/1.71	
3.42/1.71	(4)
3.42/1.71	YES
3.42/1.74	EOF