19.01/5.82	YES
19.01/5.83	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
19.01/5.83	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.01/5.83	
19.01/5.83	
19.01/5.83	Termination w.r.t. Q of the given QTRS could be proven:
19.01/5.83	
19.01/5.83	(0) QTRS
19.01/5.83	(1) QTRSRRRProof [EQUIVALENT, 40 ms]
19.01/5.83	(2) QTRS
19.01/5.83	(3) Overlay + Local Confluence [EQUIVALENT, 0 ms]
19.01/5.83	(4) QTRS
19.01/5.83	(5) DependencyPairsProof [EQUIVALENT, 9 ms]
19.01/5.83	(6) QDP
19.01/5.83	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
19.01/5.83	(8) AND
19.01/5.83	    (9) QDP
19.01/5.83	        (10) UsableRulesProof [EQUIVALENT, 0 ms]
19.01/5.83	        (11) QDP
19.01/5.83	        (12) QReductionProof [EQUIVALENT, 0 ms]
19.01/5.83	        (13) QDP
19.01/5.83	        (14) QDPSizeChangeProof [EQUIVALENT, 0 ms]
19.01/5.83	        (15) YES
19.01/5.83	    (16) QDP
19.01/5.83	        (17) UsableRulesProof [EQUIVALENT, 0 ms]
19.01/5.83	        (18) QDP
19.01/5.83	        (19) QReductionProof [EQUIVALENT, 0 ms]
19.01/5.83	        (20) QDP
19.01/5.83	        (21) QDPSizeChangeProof [EQUIVALENT, 0 ms]
19.01/5.83	        (22) YES
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(0)
19.01/5.83	Obligation:
19.01/5.83	Q restricted rewrite system:
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   f(0(x1)) -> s(0(x1))
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	Q is empty.
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(1) QTRSRRRProof (EQUIVALENT)
19.01/5.83	Used ordering:
19.01/5.83	Polynomial interpretation [POLO]:
19.01/5.83	
19.01/5.83	   POL(0(x_1)) = x_1
19.01/5.83	   POL(d(x_1)) = x_1
19.01/5.83	   POL(f(x_1)) = 1 + x_1
19.01/5.83	   POL(s(x_1)) = x_1
19.01/5.83	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
19.01/5.83	
19.01/5.83	   f(0(x1)) -> s(0(x1))
19.01/5.83	
19.01/5.83	
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(2)
19.01/5.83	Obligation:
19.01/5.83	Q restricted rewrite system:
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	Q is empty.
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(3) Overlay + Local Confluence (EQUIVALENT)
19.01/5.83	The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(4)
19.01/5.83	Obligation:
19.01/5.83	Q restricted rewrite system:
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(5) DependencyPairsProof (EQUIVALENT)
19.01/5.83	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(6)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   D(s(x1)) -> D(x1)
19.01/5.83	   F(s(x1)) -> D(f(x1))
19.01/5.83	   F(s(x1)) -> F(x1)
19.01/5.83	
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(7) DependencyGraphProof (EQUIVALENT)
19.01/5.83	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(8)
19.01/5.83	Complex Obligation (AND)
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(9)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   D(s(x1)) -> D(x1)
19.01/5.83	
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(10) UsableRulesProof (EQUIVALENT)
19.01/5.83	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.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(11)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   D(s(x1)) -> D(x1)
19.01/5.83	
19.01/5.83	R is empty.
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(12) QReductionProof (EQUIVALENT)
19.01/5.83	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(13)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   D(s(x1)) -> D(x1)
19.01/5.83	
19.01/5.83	R is empty.
19.01/5.83	Q is empty.
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(14) QDPSizeChangeProof (EQUIVALENT)
19.01/5.83	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.01/5.83	
19.01/5.83	From the DPs we obtained the following set of size-change graphs:
19.01/5.83	*D(s(x1)) -> D(x1)
19.01/5.83	The graph contains the following edges 1 > 1
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(15)
19.01/5.83	YES
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(16)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   F(s(x1)) -> F(x1)
19.01/5.83	
19.01/5.83	The TRS R consists of the following rules:
19.01/5.83	
19.01/5.83	   d(0(x1)) -> 0(x1)
19.01/5.83	   d(s(x1)) -> s(s(d(x1)))
19.01/5.83	   f(s(x1)) -> d(f(x1))
19.01/5.83	
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(17) UsableRulesProof (EQUIVALENT)
19.01/5.83	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.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(18)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   F(s(x1)) -> F(x1)
19.01/5.83	
19.01/5.83	R is empty.
19.01/5.83	The set Q consists of the following terms:
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(19) QReductionProof (EQUIVALENT)
19.01/5.83	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
19.01/5.83	
19.01/5.83	   d(0(x0))
19.01/5.83	   d(s(x0))
19.01/5.83	   f(s(x0))
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(20)
19.01/5.83	Obligation:
19.01/5.83	Q DP problem:
19.01/5.83	The TRS P consists of the following rules:
19.01/5.83	
19.01/5.83	   F(s(x1)) -> F(x1)
19.01/5.83	
19.01/5.83	R is empty.
19.01/5.83	Q is empty.
19.01/5.83	We have to consider all minimal (P,Q,R)-chains.
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(21) QDPSizeChangeProof (EQUIVALENT)
19.01/5.83	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.01/5.83	
19.01/5.83	From the DPs we obtained the following set of size-change graphs:
19.01/5.83	*F(s(x1)) -> F(x1)
19.01/5.83	The graph contains the following edges 1 > 1
19.01/5.83	
19.01/5.83	
19.01/5.83	----------------------------------------
19.01/5.83	
19.01/5.83	(22)
19.01/5.83	YES
19.46/5.96	EOF