3.92/2.04	YES
3.92/2.05	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.92/2.05	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.92/2.05	
3.92/2.05	
3.92/2.05	Termination w.r.t. Q of the given QTRS could be proven:
3.92/2.05	
3.92/2.05	(0) QTRS
3.92/2.05	(1) DependencyPairsProof [EQUIVALENT, 17 ms]
3.92/2.05	(2) QDP
3.92/2.05	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
3.92/2.05	(4) AND
3.92/2.05	    (5) QDP
3.92/2.05	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
3.92/2.05	        (7) QDP
3.92/2.05	        (8) QReductionProof [EQUIVALENT, 0 ms]
3.92/2.05	        (9) QDP
3.92/2.05	        (10) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
3.92/2.05	        (11) QDP
3.92/2.05	        (12) PisEmptyProof [EQUIVALENT, 0 ms]
3.92/2.05	        (13) YES
3.92/2.05	    (14) QDP
3.92/2.05	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
3.92/2.05	        (16) QDP
3.92/2.05	        (17) QReductionProof [EQUIVALENT, 0 ms]
3.92/2.05	        (18) QDP
3.92/2.05	        (19) QDPOrderProof [EQUIVALENT, 14 ms]
3.92/2.05	        (20) QDP
3.92/2.05	        (21) PisEmptyProof [EQUIVALENT, 0 ms]
3.92/2.05	        (22) YES
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(0)
3.92/2.05	Obligation:
3.92/2.05	Q restricted rewrite system:
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	   weight(cons(n, cons(m, x))) -> weight(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	   weight(cons(n, nil)) -> n
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(1) DependencyPairsProof (EQUIVALENT)
3.92/2.05	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(2)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   SUM(cons(s(n), x), cons(m, y)) -> SUM(cons(n, x), cons(s(m), y))
3.92/2.05	   SUM(cons(0, x), y) -> SUM(x, y)
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> WEIGHT(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> SUM(cons(n, cons(m, x)), cons(0, x))
3.92/2.05	
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	   weight(cons(n, cons(m, x))) -> weight(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	   weight(cons(n, nil)) -> n
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(3) DependencyGraphProof (EQUIVALENT)
3.92/2.05	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(4)
3.92/2.05	Complex Obligation (AND)
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(5)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   SUM(cons(0, x), y) -> SUM(x, y)
3.92/2.05	   SUM(cons(s(n), x), cons(m, y)) -> SUM(cons(n, x), cons(s(m), y))
3.92/2.05	
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	   weight(cons(n, cons(m, x))) -> weight(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	   weight(cons(n, nil)) -> n
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(6) UsableRulesProof (EQUIVALENT)
3.92/2.05	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.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(7)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   SUM(cons(0, x), y) -> SUM(x, y)
3.92/2.05	   SUM(cons(s(n), x), cons(m, y)) -> SUM(cons(n, x), cons(s(m), y))
3.92/2.05	
3.92/2.05	R is empty.
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(8) QReductionProof (EQUIVALENT)
3.92/2.05	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(9)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   SUM(cons(0, x), y) -> SUM(x, y)
3.92/2.05	   SUM(cons(s(n), x), cons(m, y)) -> SUM(cons(n, x), cons(s(m), y))
3.92/2.05	
3.92/2.05	R is empty.
3.92/2.05	Q is empty.
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(10) UsableRulesReductionPairsProof (EQUIVALENT)
3.92/2.05	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
3.92/2.05	
3.92/2.05	The following dependency pairs can be deleted:
3.92/2.05	
3.92/2.05	   SUM(cons(0, x), y) -> SUM(x, y)
3.92/2.05	   SUM(cons(s(n), x), cons(m, y)) -> SUM(cons(n, x), cons(s(m), y))
3.92/2.05	No rules are removed from R.
3.92/2.05	
3.92/2.05	Used ordering: POLO with Polynomial interpretation [POLO]:
3.92/2.05	
3.92/2.05	   POL(0) = 0
3.92/2.05	   POL(SUM(x_1, x_2)) = 2*x_1 + x_2
3.92/2.05	   POL(cons(x_1, x_2)) = x_1 + x_2
3.92/2.05	   POL(s(x_1)) = 2 + x_1
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(11)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	P is empty.
3.92/2.05	R is empty.
3.92/2.05	Q is empty.
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(12) PisEmptyProof (EQUIVALENT)
3.92/2.05	The TRS P is empty. Hence, there is no (P,Q,R) chain.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(13)
3.92/2.05	YES
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(14)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> WEIGHT(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	   weight(cons(n, cons(m, x))) -> weight(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	   weight(cons(n, nil)) -> n
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(15) UsableRulesProof (EQUIVALENT)
3.92/2.05	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.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(16)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> WEIGHT(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(17) QReductionProof (EQUIVALENT)
3.92/2.05	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.92/2.05	
3.92/2.05	   weight(cons(x0, cons(x1, x2)))
3.92/2.05	   weight(cons(x0, nil))
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(18)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	The TRS P consists of the following rules:
3.92/2.05	
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> WEIGHT(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(19) QDPOrderProof (EQUIVALENT)
3.92/2.05	We use the reduction pair processor [LPAR04,JAR06].
3.92/2.05	
3.92/2.05	
3.92/2.05	The following pairs can be oriented strictly and are deleted.
3.92/2.05	
3.92/2.05	   WEIGHT(cons(n, cons(m, x))) -> WEIGHT(sum(cons(n, cons(m, x)), cons(0, x)))
3.92/2.05	The remaining pairs can at least be oriented weakly.
3.92/2.05	Used ordering:  Combined order from the following AFS and order.
3.92/2.05	WEIGHT(x1)  =  x1
3.92/2.05	
3.92/2.05	cons(x1, x2)  =  cons(x2)
3.92/2.05	
3.92/2.05	sum(x1, x2)  =  x2
3.92/2.05	
3.92/2.05	
3.92/2.05	Knuth-Bendix order [KBO] with precedence:trivial
3.92/2.05	
3.92/2.05	and weight map:
3.92/2.05	
3.92/2.05	   dummyConstant=1
3.92/2.05	   cons_1=1
3.92/2.05	
3.92/2.05	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
3.92/2.05	
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	
3.92/2.05	
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(20)
3.92/2.05	Obligation:
3.92/2.05	Q DP problem:
3.92/2.05	P is empty.
3.92/2.05	The TRS R consists of the following rules:
3.92/2.05	
3.92/2.05	   sum(cons(0, x), y) -> sum(x, y)
3.92/2.05	   sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y))
3.92/2.05	   sum(nil, y) -> y
3.92/2.05	
3.92/2.05	The set Q consists of the following terms:
3.92/2.05	
3.92/2.05	   sum(cons(s(x0), x1), cons(x2, x3))
3.92/2.05	   sum(cons(0, x0), x1)
3.92/2.05	   sum(nil, x0)
3.92/2.05	
3.92/2.05	We have to consider all minimal (P,Q,R)-chains.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(21) PisEmptyProof (EQUIVALENT)
3.92/2.05	The TRS P is empty. Hence, there is no (P,Q,R) chain.
3.92/2.05	----------------------------------------
3.92/2.05	
3.92/2.05	(22)
3.92/2.05	YES
3.92/2.08	EOF