45.19/12.68	YES
47.21/13.23	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
47.21/13.23	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
47.21/13.23	
47.21/13.23	
47.21/13.23	Termination w.r.t. Q of the given QTRS could be proven:
47.21/13.23	
47.21/13.23	(0) QTRS
47.21/13.23	(1) QTRSRRRProof [EQUIVALENT, 89 ms]
47.21/13.23	(2) QTRS
47.21/13.23	(3) DependencyPairsProof [EQUIVALENT, 65 ms]
47.21/13.23	(4) QDP
47.21/13.23	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
47.21/13.23	(6) AND
47.21/13.23	    (7) QDP
47.21/13.23	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
47.21/13.23	        (9) QDP
47.21/13.23	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
47.21/13.23	        (11) YES
47.21/13.23	    (12) QDP
47.21/13.23	        (13) MNOCProof [EQUIVALENT, 3 ms]
47.21/13.23	        (14) QDP
47.21/13.23	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
47.21/13.23	        (16) QDP
47.21/13.23	        (17) QReductionProof [EQUIVALENT, 0 ms]
47.21/13.23	        (18) QDP
47.21/13.23	        (19) QDPOrderProof [EQUIVALENT, 26 ms]
47.21/13.23	        (20) QDP
47.21/13.23	        (21) PisEmptyProof [EQUIVALENT, 0 ms]
47.21/13.23	        (22) YES
47.21/13.23	    (23) QDP
47.21/13.23	        (24) MNOCProof [EQUIVALENT, 0 ms]
47.21/13.23	        (25) QDP
47.21/13.23	        (26) UsableRulesProof [EQUIVALENT, 0 ms]
47.21/13.23	        (27) QDP
47.21/13.23	        (28) QReductionProof [EQUIVALENT, 0 ms]
47.21/13.23	        (29) QDP
47.21/13.23	        (30) QDPOrderProof [EQUIVALENT, 102 ms]
47.21/13.23	        (31) QDP
47.21/13.23	        (32) PisEmptyProof [EQUIVALENT, 0 ms]
47.21/13.23	        (33) YES
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(0)
47.21/13.23	Obligation:
47.21/13.23	Q restricted rewrite system:
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(0(x1)) -> p(s(p(s(p(p(p(p(s(s(s(s(0(p(s(p(s(x1)))))))))))))))))
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	   0(x1) -> x1
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(1) QTRSRRRProof (EQUIVALENT)
47.21/13.23	Used ordering:
47.21/13.23	Polynomial interpretation [POLO]:
47.21/13.23	
47.21/13.23	   POL(0(x_1)) = 1 + x_1
47.21/13.23	   POL(p(x_1)) = x_1
47.21/13.23	   POL(s(x_1)) = x_1
47.21/13.23	   POL(sq(x_1)) = 1 + x_1
47.21/13.23	   POL(twice(x_1)) = x_1
47.21/13.23	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
47.21/13.23	
47.21/13.23	   sq(0(x1)) -> p(s(p(s(p(p(p(p(s(s(s(s(0(p(s(p(s(x1)))))))))))))))))
47.21/13.23	   0(x1) -> x1
47.21/13.23	
47.21/13.23	
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(2)
47.21/13.23	Obligation:
47.21/13.23	Q restricted rewrite system:
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(3) DependencyPairsProof (EQUIVALENT)
47.21/13.23	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(4)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> P(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> TWICE(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(p(p(p(p(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(p(p(p(s(s(s(s(s(s(x1)))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(p(p(s(s(s(s(s(s(x1))))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(p(s(s(s(s(s(s(x1)))))))))
47.21/13.23	   SQ(s(x1)) -> P(p(s(s(s(s(s(s(x1))))))))
47.21/13.23	   SQ(s(x1)) -> P(s(s(s(s(s(s(x1)))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1))))))))))))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1))))))))))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1))))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(s(s(p(p(s(s(p(s(p(s(p(s(x1))))))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(p(s(s(p(s(p(s(p(s(x1))))))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(s(p(s(p(s(p(s(x1)))))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(p(s(p(s(x1))))))
47.21/13.23	   TWICE(0(x1)) -> P(s(p(s(x1))))
47.21/13.23	   TWICE(0(x1)) -> P(s(x1))
47.21/13.23	   TWICE(s(x1)) -> P(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   TWICE(s(x1)) -> P(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1))))))))))))))
47.21/13.23	   TWICE(s(x1)) -> P(p(s(s(s(twice(p(s(p(s(x1))))))))))
47.21/13.23	   TWICE(s(x1)) -> P(s(s(s(twice(p(s(p(s(x1)))))))))
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	   TWICE(s(x1)) -> P(s(p(s(x1))))
47.21/13.23	   TWICE(s(x1)) -> P(s(x1))
47.21/13.23	   P(p(s(x1))) -> P(x1)
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(5) DependencyGraphProof (EQUIVALENT)
47.21/13.23	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 35 less nodes.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(6)
47.21/13.23	Complex Obligation (AND)
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(7)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   P(p(s(x1))) -> P(x1)
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(8) UsableRulesProof (EQUIVALENT)
47.21/13.23	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.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(9)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   P(p(s(x1))) -> P(x1)
47.21/13.23	
47.21/13.23	R is empty.
47.21/13.23	Q is empty.
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(10) QDPSizeChangeProof (EQUIVALENT)
47.21/13.23	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. 
47.21/13.23	
47.21/13.23	From the DPs we obtained the following set of size-change graphs:
47.21/13.23	*P(p(s(x1))) -> P(x1)
47.21/13.23	The graph contains the following edges 1 > 1
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(11)
47.21/13.23	YES
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(12)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(13) MNOCProof (EQUIVALENT)
47.21/13.23	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(14)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(15) UsableRulesProof (EQUIVALENT)
47.21/13.23	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.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(16)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(17) QReductionProof (EQUIVALENT)
47.21/13.23	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(18)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(19) QDPOrderProof (EQUIVALENT)
47.21/13.23	We use the reduction pair processor [LPAR04,JAR06].
47.21/13.23	
47.21/13.23	
47.21/13.23	The following pairs can be oriented strictly and are deleted.
47.21/13.23	
47.21/13.23	   TWICE(s(x1)) -> TWICE(p(s(p(s(x1)))))
47.21/13.23	The remaining pairs can at least be oriented weakly.
47.21/13.23	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
47.21/13.23	
47.21/13.23	POL( TWICE_1(x_1) ) = x_1 + 2
47.21/13.23	POL( p_1(x_1) ) = max{0, x_1 - 1}
47.21/13.23	POL( s_1(x_1) ) = x_1 + 1
47.21/13.23	
47.21/13.23	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(20)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	P is empty.
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(21) PisEmptyProof (EQUIVALENT)
47.21/13.23	The TRS P is empty. Hence, there is no (P,Q,R) chain.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(22)
47.21/13.23	YES
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(23)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	Q is empty.
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(24) MNOCProof (EQUIVALENT)
47.21/13.23	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(25)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   sq(s(x1)) -> s(p(s(p(s(p(p(s(s(twice(p(s(p(s(p(p(p(s(s(s(sq(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))))))))))))))))))))))
47.21/13.23	   twice(0(x1)) -> p(p(p(p(s(s(p(s(s(s(0(p(p(p(s(s(s(p(p(s(s(p(s(p(s(p(s(x1)))))))))))))))))))))))))))
47.21/13.23	   twice(s(x1)) -> p(p(s(s(s(p(p(s(s(s(twice(p(s(p(s(x1)))))))))))))))
47.21/13.23	   p(p(s(x1))) -> p(x1)
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(26) UsableRulesProof (EQUIVALENT)
47.21/13.23	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.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(27)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(28) QReductionProof (EQUIVALENT)
47.21/13.23	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
47.21/13.23	
47.21/13.23	   sq(s(x0))
47.21/13.23	   twice(0(x0))
47.21/13.23	   twice(s(x0))
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(29)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	The TRS P consists of the following rules:
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(30) QDPOrderProof (EQUIVALENT)
47.21/13.23	We use the reduction pair processor [LPAR04,JAR06].
47.21/13.23	
47.21/13.23	
47.21/13.23	The following pairs can be oriented strictly and are deleted.
47.21/13.23	
47.21/13.23	   SQ(s(x1)) -> SQ(p(p(p(p(p(p(s(s(s(s(s(s(x1)))))))))))))
47.21/13.23	The remaining pairs can at least be oriented weakly.
47.21/13.23	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
47.21/13.23	
47.21/13.23	POL( SQ_1(x_1) ) = 2x_1 + 2
47.21/13.23	POL( p_1(x_1) ) = max{0, x_1 - 2}
47.21/13.23	POL( s_1(x_1) ) = x_1 + 2
47.21/13.23	POL( 0_1(x_1) ) = max{0, -2}
47.21/13.23	
47.21/13.23	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(31)
47.21/13.23	Obligation:
47.21/13.23	Q DP problem:
47.21/13.23	P is empty.
47.21/13.23	The TRS R consists of the following rules:
47.21/13.23	
47.21/13.23	   p(s(x1)) -> x1
47.21/13.23	   p(0(x1)) -> 0(s(s(s(s(s(s(s(s(s(s(s(x1))))))))))))
47.21/13.23	
47.21/13.23	The set Q consists of the following terms:
47.21/13.23	
47.21/13.23	   p(s(x0))
47.21/13.23	   p(0(x0))
47.21/13.23	
47.21/13.23	We have to consider all minimal (P,Q,R)-chains.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(32) PisEmptyProof (EQUIVALENT)
47.21/13.23	The TRS P is empty. Hence, there is no (P,Q,R) chain.
47.21/13.23	----------------------------------------
47.21/13.23	
47.21/13.23	(33)
47.21/13.23	YES
47.38/13.27	EOF