4.06/1.71	YES
4.06/1.72	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
4.06/1.72	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.06/1.72	
4.06/1.72	
4.06/1.72	Termination of the given CSR could be proven:
4.06/1.72	
4.06/1.72	(0) CSR
4.06/1.72	(1) CSRRRRProof [EQUIVALENT, 45 ms]
4.06/1.72	(2) CSR
4.06/1.72	(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
4.06/1.72	(4) QCSDP
4.06/1.72	(5) QCSDPInstantiationProcessor [EQUIVALENT, 0 ms]
4.06/1.72	(6) QCSDP
4.06/1.72	(7) QCSUsableRulesProof [EQUIVALENT, 0 ms]
4.06/1.72	(8) QCSDP
4.06/1.72	(9) QCSDPInstantiationProcessor [EQUIVALENT, 0 ms]
4.06/1.72	(10) QCSDP
4.06/1.72	(11) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
4.06/1.72	(12) TRUE
4.06/1.72	
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(0)
4.06/1.72	Obligation:
4.06/1.72	Context-sensitive rewrite system:
4.06/1.72	The TRS R consists of the following rules:
4.06/1.72	
4.06/1.72	   h(X) -> g(X, X)
4.06/1.72	   g(a, X) -> f(b, X)
4.06/1.72	   f(X, X) -> h(a)
4.06/1.72	   a -> b
4.06/1.72	
4.06/1.72	The replacement map contains the following entries:
4.06/1.72	
4.06/1.72	h: {1}
4.06/1.72	g: {1}
4.06/1.72	a: empty set
4.06/1.72	f: {1}
4.06/1.72	b: empty set
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(1) CSRRRRProof (EQUIVALENT)
4.06/1.72	The following CSR is given: Context-sensitive rewrite system:
4.06/1.72	The TRS R consists of the following rules:
4.06/1.72	
4.06/1.72	   h(X) -> g(X, X)
4.06/1.72	   g(a, X) -> f(b, X)
4.06/1.72	   f(X, X) -> h(a)
4.06/1.72	   a -> b
4.06/1.72	
4.06/1.72	The replacement map contains the following entries:
4.06/1.72	
4.06/1.72	h: {1}
4.06/1.72	g: {1}
4.06/1.72	a: empty set
4.06/1.72	f: {1}
4.06/1.72	b: empty set
4.06/1.72	Used ordering:
4.06/1.72	Polynomial interpretation [POLO]:
4.06/1.72	
4.06/1.72	   POL(a) = 1
4.06/1.72	   POL(b) = 0
4.06/1.72	   POL(f(x_1, x_2)) = 2 + 2*x_1
4.06/1.72	   POL(g(x_1, x_2)) = 2*x_1
4.06/1.72	   POL(h(x_1)) = 2*x_1
4.06/1.72	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.06/1.72	
4.06/1.72	   a -> b
4.06/1.72	
4.06/1.72	
4.06/1.72	
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(2)
4.06/1.72	Obligation:
4.06/1.72	Context-sensitive rewrite system:
4.06/1.72	The TRS R consists of the following rules:
4.06/1.72	
4.06/1.72	   h(X) -> g(X, X)
4.06/1.72	   g(a, X) -> f(b, X)
4.06/1.72	   f(X, X) -> h(a)
4.06/1.72	
4.06/1.72	The replacement map contains the following entries:
4.06/1.72	
4.06/1.72	h: {1}
4.06/1.72	g: {1}
4.06/1.72	a: empty set
4.06/1.72	f: {1}
4.06/1.72	b: empty set
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(3) CSDependencyPairsProof (EQUIVALENT)
4.06/1.72	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(4)
4.06/1.72	Obligation:
4.06/1.72	Q-restricted context-sensitive dependency pair problem:
4.06/1.72	The symbols in {h_1, H_1} are replacing on all positions.
4.06/1.72	For all symbols f in {g_2, f_2, G_2, F_2} we have mu(f) = {1}.
4.06/1.72	
4.06/1.72	The ordinary context-sensitive dependency pairs DP_o are:
4.06/1.72	   H(X) -> G(X, X)
4.06/1.72	   G(a, X) -> F(b, X)
4.06/1.72	   F(X, X) -> H(a)
4.06/1.72	
4.06/1.72	The TRS R consists of the following rules:
4.06/1.72	
4.06/1.72	   h(X) -> g(X, X)
4.06/1.72	   g(a, X) -> f(b, X)
4.06/1.72	   f(X, X) -> h(a)
4.06/1.72	
4.06/1.72	Q is empty.
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(5) QCSDPInstantiationProcessor (EQUIVALENT)
4.06/1.72	Using the Context-Sensitive Instantiation[LPAR08,DA_EMMES] Processor
4.06/1.72	
4.06/1.72	the pair H(X) -> G(X, X)
4.06/1.72	
4.06/1.72	was transformed to the following new pairs: 
4.06/1.72	   H(a) -> G(a, a)
4.06/1.72	
4.06/1.72	
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(6)
4.06/1.72	Obligation:
4.06/1.72	Q-restricted context-sensitive dependency pair problem:
4.06/1.72	The symbols in {h_1, H_1} are replacing on all positions.
4.06/1.72	For all symbols f in {g_2, f_2, F_2, G_2} we have mu(f) = {1}.
4.06/1.72	
4.06/1.72	The TRS P consists of the following rules:
4.06/1.72	
4.06/1.72	   G(a, X) -> F(b, X)
4.06/1.72	   F(X, X) -> H(a)
4.06/1.72	   H(a) -> G(a, a)
4.06/1.72	
4.06/1.72	The TRS R consists of the following rules:
4.06/1.72	
4.06/1.72	   h(X) -> g(X, X)
4.06/1.72	   g(a, X) -> f(b, X)
4.06/1.72	   f(X, X) -> h(a)
4.06/1.72	
4.06/1.72	Q is empty.
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(7) QCSUsableRulesProof (EQUIVALENT)
4.06/1.72	The following rules are not useable [DA_EMMES] and can be deleted:
4.06/1.72	
4.06/1.72	   h(x0) -> g(x0, x0)
4.06/1.72	   g(a, x0) -> f(b, x0)
4.06/1.72	   f(x0, x0) -> h(a)
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(8)
4.06/1.72	Obligation:
4.06/1.72	Q-restricted context-sensitive dependency pair problem:
4.06/1.72	The symbols in {H_1} are replacing on all positions.
4.06/1.72	For all symbols f in {F_2, G_2} we have mu(f) = {1}.
4.06/1.72	
4.06/1.72	The TRS P consists of the following rules:
4.06/1.72	
4.06/1.72	   G(a, X) -> F(b, X)
4.06/1.72	   F(X, X) -> H(a)
4.06/1.72	   H(a) -> G(a, a)
4.06/1.72	
4.06/1.72	R is empty.
4.06/1.72	Q is empty.
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(9) QCSDPInstantiationProcessor (EQUIVALENT)
4.06/1.72	Using the Context-Sensitive Instantiation[LPAR08,DA_EMMES] Processor
4.06/1.72	
4.06/1.72	the pair G(a, X) -> F(b, X)
4.06/1.72	
4.06/1.72	was transformed to the following new pairs: 
4.06/1.72	   G(a, a) -> F(b, a)
4.06/1.72	
4.06/1.72	
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(10)
4.06/1.72	Obligation:
4.06/1.72	Q-restricted context-sensitive dependency pair problem:
4.06/1.72	The symbols in {H_1} are replacing on all positions.
4.06/1.72	For all symbols f in {F_2, G_2} we have mu(f) = {1}.
4.06/1.72	
4.06/1.72	The TRS P consists of the following rules:
4.06/1.72	
4.06/1.72	   F(X, X) -> H(a)
4.06/1.72	   H(a) -> G(a, a)
4.06/1.72	   G(a, a) -> F(b, a)
4.06/1.72	
4.06/1.72	R is empty.
4.06/1.72	Q is empty.
4.06/1.72	
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(11) QCSDependencyGraphProof (EQUIVALENT)
4.06/1.72	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes.
4.06/1.72	The rules G(a, a) -> F(b, a) and F(x0, x0) -> H(a) form no chain, because ECap^mu(F(b, a)) = F(b, a) does not unify with F(x0, x0). 
4.06/1.72	----------------------------------------
4.06/1.72	
4.06/1.72	(12)
4.06/1.72	TRUE
4.06/1.74	EOF