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