4.32/2.06	YES
4.36/2.06	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.36/2.06	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.36/2.06	
4.36/2.06	
4.36/2.06	Termination w.r.t. Q of the given QTRS could be proven:
4.36/2.06	
4.36/2.06	(0) QTRS
4.36/2.06	(1) DependencyPairsProof [EQUIVALENT, 0 ms]
4.36/2.06	(2) QDP
4.36/2.06	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
4.36/2.06	(4) AND
4.36/2.06	    (5) QDP
4.36/2.06	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
4.36/2.06	        (7) QDP
4.36/2.06	        (8) QReductionProof [EQUIVALENT, 0 ms]
4.36/2.06	        (9) QDP
4.36/2.06	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.36/2.06	        (11) YES
4.36/2.06	    (12) QDP
4.36/2.06	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
4.36/2.06	        (14) QDP
4.36/2.06	        (15) QReductionProof [EQUIVALENT, 0 ms]
4.36/2.06	        (16) QDP
4.36/2.06	        (17) TransformationProof [EQUIVALENT, 0 ms]
4.36/2.06	        (18) QDP
4.36/2.06	        (19) UsableRulesProof [EQUIVALENT, 0 ms]
4.36/2.06	        (20) QDP
4.36/2.06	        (21) QReductionProof [EQUIVALENT, 0 ms]
4.36/2.06	        (22) QDP
4.36/2.06	        (23) TransformationProof [EQUIVALENT, 0 ms]
4.36/2.06	        (24) QDP
4.36/2.06	        (25) DependencyGraphProof [EQUIVALENT, 0 ms]
4.36/2.06	        (26) TRUE
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(0)
4.36/2.06	Obligation:
4.36/2.06	Q restricted rewrite system:
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   f(0, s(0), X) -> f(X, double(X), X)
4.36/2.06	   g(X, Y) -> X
4.36/2.06	   g(X, Y) -> Y
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(1) DependencyPairsProof (EQUIVALENT)
4.36/2.06	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(2)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   +^1(X, s(Y)) -> +^1(X, Y)
4.36/2.06	   DOUBLE(X) -> +^1(X, X)
4.36/2.06	   F(0, s(0), X) -> F(X, double(X), X)
4.36/2.06	   F(0, s(0), X) -> DOUBLE(X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   f(0, s(0), X) -> f(X, double(X), X)
4.36/2.06	   g(X, Y) -> X
4.36/2.06	   g(X, Y) -> Y
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(3) DependencyGraphProof (EQUIVALENT)
4.36/2.06	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(4)
4.36/2.06	Complex Obligation (AND)
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(5)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   +^1(X, s(Y)) -> +^1(X, Y)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   f(0, s(0), X) -> f(X, double(X), X)
4.36/2.06	   g(X, Y) -> X
4.36/2.06	   g(X, Y) -> Y
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(6) UsableRulesProof (EQUIVALENT)
4.36/2.06	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.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(7)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   +^1(X, s(Y)) -> +^1(X, Y)
4.36/2.06	
4.36/2.06	R is empty.
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(8) QReductionProof (EQUIVALENT)
4.36/2.06	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(9)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   +^1(X, s(Y)) -> +^1(X, Y)
4.36/2.06	
4.36/2.06	R is empty.
4.36/2.06	Q is empty.
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(10) QDPSizeChangeProof (EQUIVALENT)
4.36/2.06	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. 
4.36/2.06	
4.36/2.06	From the DPs we obtained the following set of size-change graphs:
4.36/2.06	*+^1(X, s(Y)) -> +^1(X, Y)
4.36/2.06	The graph contains the following edges 1 >= 1, 2 > 2
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(11)
4.36/2.06	YES
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(12)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, double(X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   f(0, s(0), X) -> f(X, double(X), X)
4.36/2.06	   g(X, Y) -> X
4.36/2.06	   g(X, Y) -> Y
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(13) UsableRulesProof (EQUIVALENT)
4.36/2.06	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.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(14)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, double(X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(15) QReductionProof (EQUIVALENT)
4.36/2.06	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.36/2.06	
4.36/2.06	   f(0, s(0), x0)
4.36/2.06	   g(x0, x1)
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(16)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, double(X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(17) TransformationProof (EQUIVALENT)
4.36/2.06	By rewriting [LPAR04] the rule F(0, s(0), X) -> F(X, double(X), X) at position [1] we obtained the following new rules [LPAR04]:
4.36/2.06	
4.36/2.06	   (F(0, s(0), X) -> F(X, +(X, X), X),F(0, s(0), X) -> F(X, +(X, X), X))
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(18)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, +(X, X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   double(X) -> +(X, X)
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(19) UsableRulesProof (EQUIVALENT)
4.36/2.06	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.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(20)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, +(X, X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	   double(x0)
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(21) QReductionProof (EQUIVALENT)
4.36/2.06	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.36/2.06	
4.36/2.06	   double(x0)
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(22)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), X) -> F(X, +(X, X), X)
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(23) TransformationProof (EQUIVALENT)
4.36/2.06	By narrowing [LPAR04] the rule F(0, s(0), X) -> F(X, +(X, X), X) at position [1] we obtained the following new rules [LPAR04]:
4.36/2.06	
4.36/2.06	   (F(0, s(0), 0) -> F(0, 0, 0),F(0, s(0), 0) -> F(0, 0, 0))
4.36/2.06	   (F(0, s(0), s(x1)) -> F(s(x1), s(+(s(x1), x1)), s(x1)),F(0, s(0), s(x1)) -> F(s(x1), s(+(s(x1), x1)), s(x1)))
4.36/2.06	
4.36/2.06	
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(24)
4.36/2.06	Obligation:
4.36/2.06	Q DP problem:
4.36/2.06	The TRS P consists of the following rules:
4.36/2.06	
4.36/2.06	   F(0, s(0), 0) -> F(0, 0, 0)
4.36/2.06	   F(0, s(0), s(x1)) -> F(s(x1), s(+(s(x1), x1)), s(x1))
4.36/2.06	
4.36/2.06	The TRS R consists of the following rules:
4.36/2.06	
4.36/2.06	   +(X, 0) -> X
4.36/2.06	   +(X, s(Y)) -> s(+(X, Y))
4.36/2.06	
4.36/2.06	The set Q consists of the following terms:
4.36/2.06	
4.36/2.06	   +(x0, 0)
4.36/2.06	   +(x0, s(x1))
4.36/2.06	
4.36/2.06	We have to consider all minimal (P,Q,R)-chains.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(25) DependencyGraphProof (EQUIVALENT)
4.36/2.06	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
4.36/2.06	----------------------------------------
4.36/2.06	
4.36/2.06	(26)
4.36/2.06	TRUE
4.36/2.09	EOF