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