19.37/5.90	YES
19.61/5.96	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
19.61/5.96	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.61/5.96	
19.61/5.96	
19.61/5.96	Termination w.r.t. Q of the given QTRS could be proven:
19.61/5.96	
19.61/5.96	(0) QTRS
19.61/5.96	(1) DependencyPairsProof [EQUIVALENT, 17 ms]
19.61/5.96	(2) QDP
19.61/5.96	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
19.61/5.96	(4) AND
19.61/5.96	    (5) QDP
19.61/5.96	        (6) UsableRulesProof [EQUIVALENT, 2 ms]
19.61/5.96	        (7) QDP
19.61/5.96	        (8) QDPSizeChangeProof [EQUIVALENT, 2 ms]
19.61/5.96	        (9) YES
19.61/5.96	    (10) QDP
19.61/5.96	        (11) MNOCProof [EQUIVALENT, 0 ms]
19.61/5.96	        (12) QDP
19.61/5.96	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
19.61/5.96	        (14) QDP
19.61/5.96	        (15) QReductionProof [EQUIVALENT, 0 ms]
19.61/5.96	        (16) QDP
19.61/5.96	        (17) QDPOrderProof [EQUIVALENT, 34 ms]
19.61/5.96	        (18) QDP
19.61/5.96	        (19) DependencyGraphProof [EQUIVALENT, 0 ms]
19.61/5.96	        (20) TRUE
19.61/5.96	
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(0)
19.61/5.96	Obligation:
19.61/5.96	Q restricted rewrite system:
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   a(s(x1)) -> s(s(s(p(s(b(p(p(s(s(x1))))))))))
19.61/5.96	   b(s(x1)) -> s(s(s(p(p(s(s(c(p(s(p(s(x1))))))))))))
19.61/5.96	   c(s(x1)) -> p(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   p(p(s(x1))) -> p(x1)
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	Q is empty.
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(1) DependencyPairsProof (EQUIVALENT)
19.61/5.96	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(2)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> P(s(b(p(p(s(s(x1)))))))
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   A(s(x1)) -> P(p(s(s(x1))))
19.61/5.96	   A(s(x1)) -> P(s(s(x1)))
19.61/5.96	   B(s(x1)) -> P(p(s(s(c(p(s(p(s(x1)))))))))
19.61/5.96	   B(s(x1)) -> P(s(s(c(p(s(p(s(x1))))))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	   B(s(x1)) -> P(s(p(s(x1))))
19.61/5.96	   B(s(x1)) -> P(s(x1))
19.61/5.96	   C(s(x1)) -> P(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   C(s(x1)) -> P(s(a(p(s(p(s(x1)))))))
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	   C(s(x1)) -> P(s(p(s(x1))))
19.61/5.96	   C(s(x1)) -> P(s(x1))
19.61/5.96	   P(p(s(x1))) -> P(x1)
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   a(s(x1)) -> s(s(s(p(s(b(p(p(s(s(x1))))))))))
19.61/5.96	   b(s(x1)) -> s(s(s(p(p(s(s(c(p(s(p(s(x1))))))))))))
19.61/5.96	   c(s(x1)) -> p(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   p(p(s(x1))) -> p(x1)
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	Q is empty.
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(3) DependencyGraphProof (EQUIVALENT)
19.61/5.96	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 11 less nodes.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(4)
19.61/5.96	Complex Obligation (AND)
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(5)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   P(p(s(x1))) -> P(x1)
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   a(s(x1)) -> s(s(s(p(s(b(p(p(s(s(x1))))))))))
19.61/5.96	   b(s(x1)) -> s(s(s(p(p(s(s(c(p(s(p(s(x1))))))))))))
19.61/5.96	   c(s(x1)) -> p(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   p(p(s(x1))) -> p(x1)
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	Q is empty.
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(6) UsableRulesProof (EQUIVALENT)
19.61/5.96	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(7)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   P(p(s(x1))) -> P(x1)
19.61/5.96	
19.61/5.96	R is empty.
19.61/5.96	Q is empty.
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(8) QDPSizeChangeProof (EQUIVALENT)
19.61/5.96	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
19.61/5.96	
19.61/5.96	From the DPs we obtained the following set of size-change graphs:
19.61/5.96	*P(p(s(x1))) -> P(x1)
19.61/5.96	The graph contains the following edges 1 > 1
19.61/5.96	
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(9)
19.61/5.96	YES
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(10)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   a(s(x1)) -> s(s(s(p(s(b(p(p(s(s(x1))))))))))
19.61/5.96	   b(s(x1)) -> s(s(s(p(p(s(s(c(p(s(p(s(x1))))))))))))
19.61/5.96	   c(s(x1)) -> p(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   p(p(s(x1))) -> p(x1)
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	Q is empty.
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(11) MNOCProof (EQUIVALENT)
19.61/5.96	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(12)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   a(s(x1)) -> s(s(s(p(s(b(p(p(s(s(x1))))))))))
19.61/5.96	   b(s(x1)) -> s(s(s(p(p(s(s(c(p(s(p(s(x1))))))))))))
19.61/5.96	   c(s(x1)) -> p(s(p(s(a(p(s(p(s(x1)))))))))
19.61/5.96	   p(p(s(x1))) -> p(x1)
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	The set Q consists of the following terms:
19.61/5.96	
19.61/5.96	   a(s(x0))
19.61/5.96	   b(s(x0))
19.61/5.96	   c(s(x0))
19.61/5.96	   p(s(x0))
19.61/5.96	
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(13) UsableRulesProof (EQUIVALENT)
19.61/5.96	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(14)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	The set Q consists of the following terms:
19.61/5.96	
19.61/5.96	   a(s(x0))
19.61/5.96	   b(s(x0))
19.61/5.96	   c(s(x0))
19.61/5.96	   p(s(x0))
19.61/5.96	
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(15) QReductionProof (EQUIVALENT)
19.61/5.96	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
19.61/5.96	
19.61/5.96	   a(s(x0))
19.61/5.96	   b(s(x0))
19.61/5.96	   c(s(x0))
19.61/5.96	
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(16)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	The set Q consists of the following terms:
19.61/5.96	
19.61/5.96	   p(s(x0))
19.61/5.96	
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(17) QDPOrderProof (EQUIVALENT)
19.61/5.96	We use the reduction pair processor [LPAR04,JAR06].
19.61/5.96	
19.61/5.96	
19.61/5.96	The following pairs can be oriented strictly and are deleted.
19.61/5.96	
19.61/5.96	   C(s(x1)) -> A(p(s(p(s(x1)))))
19.61/5.96	The remaining pairs can at least be oriented weakly.
19.61/5.96	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
19.61/5.96	
19.61/5.96	POL( A_1(x_1) ) = max{0, 2x_1 - 2}
19.61/5.96	POL( B_1(x_1) ) = max{0, 2x_1 - 2}
19.61/5.96	POL( C_1(x_1) ) = max{0, 2x_1 - 1}
19.61/5.96	POL( p_1(x_1) ) = max{0, x_1 - 1}
19.61/5.96	POL( s_1(x_1) ) = x_1 + 1
19.61/5.96	
19.61/5.96	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
19.61/5.96	
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(18)
19.61/5.96	Obligation:
19.61/5.96	Q DP problem:
19.61/5.96	The TRS P consists of the following rules:
19.61/5.96	
19.61/5.96	   A(s(x1)) -> B(p(p(s(s(x1)))))
19.61/5.96	   B(s(x1)) -> C(p(s(p(s(x1)))))
19.61/5.96	
19.61/5.96	The TRS R consists of the following rules:
19.61/5.96	
19.61/5.96	   p(s(x1)) -> x1
19.61/5.96	
19.61/5.96	The set Q consists of the following terms:
19.61/5.96	
19.61/5.96	   p(s(x0))
19.61/5.96	
19.61/5.96	We have to consider all minimal (P,Q,R)-chains.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(19) DependencyGraphProof (EQUIVALENT)
19.61/5.96	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
19.61/5.96	----------------------------------------
19.61/5.96	
19.61/5.96	(20)
19.61/5.96	TRUE
19.61/6.01	EOF