7.38/2.67	YES
8.07/2.81	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
8.07/2.81	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
8.07/2.81	
8.07/2.81	
8.07/2.81	Termination w.r.t. Q of the given QTRS could be proven:
8.07/2.81	
8.07/2.81	(0) QTRS
8.07/2.81	(1) QTRS Reverse [EQUIVALENT, 0 ms]
8.07/2.81	(2) QTRS
8.07/2.81	(3) FlatCCProof [EQUIVALENT, 0 ms]
8.07/2.81	(4) QTRS
8.07/2.81	(5) RootLabelingProof [EQUIVALENT, 0 ms]
8.07/2.81	(6) QTRS
8.07/2.81	(7) QTRSRRRProof [EQUIVALENT, 16 ms]
8.07/2.81	(8) QTRS
8.07/2.81	(9) QTRSRRRProof [EQUIVALENT, 2 ms]
8.07/2.81	(10) QTRS
8.07/2.81	(11) RisEmptyProof [EQUIVALENT, 3 ms]
8.07/2.81	(12) YES
8.07/2.81	
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(0)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	The TRS R consists of the following rules:
8.07/2.81	
8.07/2.81	   a(a(a(x1))) -> a(c(a(a(x1))))
8.07/2.81	   c(c(c(x1))) -> a(x1)
8.07/2.81	   a(x1) -> x1
8.07/2.81	
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(1) QTRS Reverse (EQUIVALENT)
8.07/2.81	We applied the QTRS Reverse Processor [REVERSE].
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(2)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	The TRS R consists of the following rules:
8.07/2.81	
8.07/2.81	   a(a(a(x1))) -> a(a(c(a(x1))))
8.07/2.81	   c(c(c(x1))) -> a(x1)
8.07/2.81	   a(x1) -> x1
8.07/2.81	
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(3) FlatCCProof (EQUIVALENT)
8.07/2.81	We used flat context closure [ROOTLAB]
8.07/2.81	As Q is empty the flat context closure was sound AND complete.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(4)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	The TRS R consists of the following rules:
8.07/2.81	
8.07/2.81	   a(a(a(x1))) -> a(a(c(a(x1))))
8.07/2.81	   a(c(c(c(x1)))) -> a(a(x1))
8.07/2.81	   c(c(c(c(x1)))) -> c(a(x1))
8.07/2.81	   a(a(x1)) -> a(x1)
8.07/2.81	   c(a(x1)) -> c(x1)
8.07/2.81	
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(5) RootLabelingProof (EQUIVALENT)
8.07/2.81	We used plain root labeling [ROOTLAB] with the following heuristic:
8.07/2.81	LabelAll: All function symbols get labeled
8.07/2.81	
8.07/2.81	As Q is empty the root labeling was sound AND complete.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(6)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	The TRS R consists of the following rules:
8.07/2.81	
8.07/2.81	   a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{a_1}(x1))))
8.07/2.81	   a_{a_1}(a_{a_1}(a_{c_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{c_1}(x1))))
8.07/2.81	   a_{c_1}(c_{c_1}(c_{c_1}(c_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1))
8.07/2.81	   a_{c_1}(c_{c_1}(c_{c_1}(c_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1))
8.07/2.81	   c_{c_1}(c_{c_1}(c_{c_1}(c_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1))
8.07/2.81	   c_{c_1}(c_{c_1}(c_{c_1}(c_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1))
8.07/2.81	   a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(x1)
8.07/2.81	   a_{a_1}(a_{c_1}(x1)) -> a_{c_1}(x1)
8.07/2.81	   c_{a_1}(a_{a_1}(x1)) -> c_{a_1}(x1)
8.07/2.81	   c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1)
8.07/2.81	
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(7) QTRSRRRProof (EQUIVALENT)
8.07/2.81	Used ordering:
8.07/2.81	Polynomial interpretation [POLO]:
8.07/2.81	
8.07/2.81	   POL(a_{a_1}(x_1)) = 3 + x_1
8.07/2.81	   POL(a_{c_1}(x_1)) = x_1
8.07/2.81	   POL(c_{a_1}(x_1)) = 3 + x_1
8.07/2.81	   POL(c_{c_1}(x_1)) = 2 + x_1
8.07/2.81	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
8.07/2.81	
8.07/2.81	   a_{c_1}(c_{c_1}(c_{c_1}(c_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1))
8.07/2.81	   a_{c_1}(c_{c_1}(c_{c_1}(c_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1))
8.07/2.81	   c_{c_1}(c_{c_1}(c_{c_1}(c_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1))
8.07/2.81	   c_{c_1}(c_{c_1}(c_{c_1}(c_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1))
8.07/2.81	   a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(x1)
8.07/2.81	   a_{a_1}(a_{c_1}(x1)) -> a_{c_1}(x1)
8.07/2.81	   c_{a_1}(a_{a_1}(x1)) -> c_{a_1}(x1)
8.07/2.81	   c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1)
8.07/2.81	
8.07/2.81	
8.07/2.81	
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(8)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	The TRS R consists of the following rules:
8.07/2.81	
8.07/2.81	   a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{a_1}(x1))))
8.07/2.81	   a_{a_1}(a_{a_1}(a_{c_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{c_1}(x1))))
8.07/2.81	
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(9) QTRSRRRProof (EQUIVALENT)
8.07/2.81	Used ordering:
8.07/2.81	Polynomial interpretation [POLO]:
8.07/2.81	
8.07/2.81	   POL(a_{a_1}(x_1)) = 1 + x_1
8.07/2.81	   POL(a_{c_1}(x_1)) = x_1
8.07/2.81	   POL(c_{a_1}(x_1)) = x_1
8.07/2.81	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
8.07/2.81	
8.07/2.81	   a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{a_1}(x1))))
8.07/2.81	   a_{a_1}(a_{a_1}(a_{c_1}(x1))) -> a_{a_1}(a_{c_1}(c_{a_1}(a_{c_1}(x1))))
8.07/2.81	
8.07/2.81	
8.07/2.81	
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(10)
8.07/2.81	Obligation:
8.07/2.81	Q restricted rewrite system:
8.07/2.81	R is empty.
8.07/2.81	Q is empty.
8.07/2.81	
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(11) RisEmptyProof (EQUIVALENT)
8.07/2.81	The TRS R is empty. Hence, termination is trivially proven.
8.07/2.81	----------------------------------------
8.07/2.81	
8.07/2.81	(12)
8.07/2.81	YES
8.23/2.90	EOF