3.23/1.63	YES
3.23/1.63	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.23/1.63	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.23/1.63	
3.23/1.63	
3.23/1.63	Termination of the given RelTRS could be proven:
3.23/1.63	
3.23/1.63	(0) RelTRS
3.23/1.63	(1) RelTRStoQDPProof [SOUND, 0 ms]
3.23/1.63	(2) QDP
3.23/1.63	(3) MRRProof [EQUIVALENT, 52 ms]
3.23/1.63	(4) QDP
3.23/1.63	(5) PisEmptyProof [EQUIVALENT, 0 ms]
3.23/1.63	(6) YES
3.23/1.63	
3.23/1.63	
3.23/1.63	----------------------------------------
3.23/1.63	
3.23/1.63	(0)
3.23/1.63	Obligation:
3.23/1.63	Relative term rewrite system:
3.23/1.63	The relative TRS consists of the following R rules:
3.23/1.63	
3.23/1.63	   t(f(x), g(y), f(z)) -> t(z, g(x), g(y))
3.23/1.63	   t(g(x), g(y), f(z)) -> t(f(y), f(z), x)
3.23/1.63	
3.23/1.63	The relative TRS consists of the following S rules:
3.23/1.63	
3.23/1.63	   f(g(x)) -> g(f(x))
3.23/1.63	   g(f(x)) -> f(g(x))
3.23/1.63	   f(f(x)) -> g(g(x))
3.23/1.63	   g(g(x)) -> f(f(x))
3.23/1.63	
3.23/1.63	
3.23/1.63	----------------------------------------
3.23/1.63	
3.23/1.63	(1) RelTRStoQDPProof (SOUND)
3.23/1.63	The relative termination problem is root-restricted. We can therefore treat it as a dependency pair problem.
3.23/1.63	----------------------------------------
3.23/1.63	
3.23/1.63	(2)
3.23/1.63	Obligation:
3.23/1.63	Q DP problem:
3.23/1.63	The TRS P consists of the following rules:
3.23/1.63	
3.23/1.63	   t(f(x), g(y), f(z)) -> t(z, g(x), g(y))
3.23/1.64	   t(g(x), g(y), f(z)) -> t(f(y), f(z), x)
3.23/1.64	
3.23/1.64	The TRS R consists of the following rules:
3.23/1.64	
3.23/1.64	   f(g(x)) -> g(f(x))
3.23/1.64	   g(f(x)) -> f(g(x))
3.23/1.64	   f(f(x)) -> g(g(x))
3.23/1.64	   g(g(x)) -> f(f(x))
3.23/1.64	
3.23/1.64	Q is empty.
3.23/1.64	We have to consider all (P,Q,R)-chains.
3.23/1.64	----------------------------------------
3.23/1.64	
3.23/1.64	(3) MRRProof (EQUIVALENT)
3.23/1.64	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
3.23/1.64	
3.23/1.64	Strictly oriented dependency pairs:
3.23/1.64	
3.23/1.64	   t(f(x), g(y), f(z)) -> t(z, g(x), g(y))
3.23/1.64	   t(g(x), g(y), f(z)) -> t(f(y), f(z), x)
3.23/1.64	
3.23/1.64	
3.23/1.64	Used ordering: Polynomial interpretation [POLO]:
3.23/1.64	
3.23/1.64	   POL(f(x_1)) = 2 + 2*x_1
3.23/1.64	   POL(g(x_1)) = 2 + 2*x_1
3.23/1.64	   POL(t(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
3.23/1.64	
3.23/1.64	
3.23/1.64	----------------------------------------
3.23/1.64	
3.23/1.64	(4)
3.23/1.64	Obligation:
3.23/1.64	Q DP problem:
3.23/1.64	P is empty.
3.23/1.64	The TRS R consists of the following rules:
3.23/1.64	
3.23/1.64	   f(g(x)) -> g(f(x))
3.23/1.64	   g(f(x)) -> f(g(x))
3.23/1.64	   f(f(x)) -> g(g(x))
3.23/1.64	   g(g(x)) -> f(f(x))
3.23/1.64	
3.23/1.64	Q is empty.
3.23/1.64	We have to consider all (P,Q,R)-chains.
3.23/1.64	----------------------------------------
3.23/1.64	
3.23/1.64	(5) PisEmptyProof (EQUIVALENT)
3.23/1.64	The TRS P is empty. Hence, there is no (P,Q,R) chain.
3.23/1.64	----------------------------------------
3.23/1.64	
3.23/1.64	(6)
3.23/1.64	YES
3.23/1.65	EOF