4.14/1.94	YES
4.33/1.95	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.33/1.95	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.33/1.95	
4.33/1.95	
4.33/1.95	Termination w.r.t. Q of the given QTRS could be proven:
4.33/1.95	
4.33/1.95	(0) QTRS
4.33/1.95	(1) QTRSRRRProof [EQUIVALENT, 80 ms]
4.33/1.95	(2) QTRS
4.33/1.95	(3) QTRSRRRProof [EQUIVALENT, 16 ms]
4.33/1.95	(4) QTRS
4.33/1.95	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
4.33/1.95	(6) QTRS
4.33/1.95	(7) QTRSRRRProof [EQUIVALENT, 7 ms]
4.33/1.95	(8) QTRS
4.33/1.95	(9) QTRSRRRProof [EQUIVALENT, 0 ms]
4.33/1.95	(10) QTRS
4.33/1.95	(11) DependencyPairsProof [EQUIVALENT, 8 ms]
4.33/1.95	(12) QDP
4.33/1.95	(13) DependencyGraphProof [EQUIVALENT, 0 ms]
4.33/1.95	(14) QDP
4.33/1.95	(15) UsableRulesProof [EQUIVALENT, 0 ms]
4.33/1.95	(16) QDP
4.33/1.95	(17) QReductionProof [EQUIVALENT, 0 ms]
4.33/1.95	(18) QDP
4.33/1.95	(19) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.33/1.95	(20) YES
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(0)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(0) -> cons(0, f(s(0)))
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(f(X)) -> a__f(mark(X))
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   mark(0) -> 0
4.33/1.95	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	   a__f(X) -> f(X)
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(1) QTRSRRRProof (EQUIVALENT)
4.33/1.95	Used ordering:
4.33/1.95	Polynomial interpretation [POLO]:
4.33/1.95	
4.33/1.95	   POL(0) = 0
4.33/1.95	   POL(a__f(x_1)) = 2 + 2*x_1
4.33/1.95	   POL(a__p(x_1)) = 2*x_1
4.33/1.95	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
4.33/1.95	   POL(f(x_1)) = 2 + 2*x_1
4.33/1.95	   POL(mark(x_1)) = 2*x_1
4.33/1.95	   POL(p(x_1)) = 2*x_1
4.33/1.95	   POL(s(x_1)) = 2*x_1
4.33/1.95	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.33/1.95	
4.33/1.95	   mark(f(X)) -> a__f(mark(X))
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(2)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(0) -> cons(0, f(s(0)))
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   mark(0) -> 0
4.33/1.95	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	   a__f(X) -> f(X)
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(3) QTRSRRRProof (EQUIVALENT)
4.33/1.95	Used ordering:
4.33/1.95	Polynomial interpretation [POLO]:
4.33/1.95	
4.33/1.95	   POL(0) = 0
4.33/1.95	   POL(a__f(x_1)) = 1 + 2*x_1
4.33/1.95	   POL(a__p(x_1)) = 2*x_1
4.33/1.95	   POL(cons(x_1, x_2)) = x_1 + x_2
4.33/1.95	   POL(f(x_1)) = x_1
4.33/1.95	   POL(mark(x_1)) = x_1
4.33/1.95	   POL(p(x_1)) = 2*x_1
4.33/1.95	   POL(s(x_1)) = 2*x_1
4.33/1.95	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.33/1.95	
4.33/1.95	   a__f(0) -> cons(0, f(s(0)))
4.33/1.95	   a__f(X) -> f(X)
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(4)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   mark(0) -> 0
4.33/1.95	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(5) QTRSRRRProof (EQUIVALENT)
4.33/1.95	Used ordering:
4.33/1.95	Polynomial interpretation [POLO]:
4.33/1.95	
4.33/1.95	   POL(0) = 0
4.33/1.95	   POL(a__f(x_1)) = 2*x_1
4.33/1.95	   POL(a__p(x_1)) = 2*x_1
4.33/1.95	   POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2
4.33/1.95	   POL(mark(x_1)) = 2*x_1
4.33/1.95	   POL(p(x_1)) = 2*x_1
4.33/1.95	   POL(s(x_1)) = 2*x_1
4.33/1.95	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.33/1.95	
4.33/1.95	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(6)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   mark(0) -> 0
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(7) QTRSRRRProof (EQUIVALENT)
4.33/1.95	Used ordering:
4.33/1.95	Polynomial interpretation [POLO]:
4.33/1.95	
4.33/1.95	   POL(0) = 2
4.33/1.95	   POL(a__f(x_1)) = 2*x_1
4.33/1.95	   POL(a__p(x_1)) = x_1
4.33/1.95	   POL(mark(x_1)) = 2*x_1
4.33/1.95	   POL(p(x_1)) = x_1
4.33/1.95	   POL(s(x_1)) = 2*x_1
4.33/1.95	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.33/1.95	
4.33/1.95	   mark(0) -> 0
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(8)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(9) QTRSRRRProof (EQUIVALENT)
4.33/1.95	Used ordering:
4.33/1.95	Polynomial interpretation [POLO]:
4.33/1.95	
4.33/1.95	   POL(0) = 0
4.33/1.95	   POL(a__f(x_1)) = x_1
4.33/1.95	   POL(a__p(x_1)) = x_1
4.33/1.95	   POL(mark(x_1)) = 2*x_1
4.33/1.95	   POL(p(x_1)) = x_1
4.33/1.95	   POL(s(x_1)) = 1 + 2*x_1
4.33/1.95	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.33/1.95	
4.33/1.95	   a__p(s(X)) -> mark(X)
4.33/1.95	   mark(s(X)) -> s(mark(X))
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(10)
4.33/1.95	Obligation:
4.33/1.95	Q restricted rewrite system:
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(11) DependencyPairsProof (EQUIVALENT)
4.33/1.95	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(12)
4.33/1.95	Obligation:
4.33/1.95	Q DP problem:
4.33/1.95	The TRS P consists of the following rules:
4.33/1.95	
4.33/1.95	   A__F(s(0)) -> A__F(a__p(s(0)))
4.33/1.95	   A__F(s(0)) -> A__P(s(0))
4.33/1.95	   MARK(p(X)) -> A__P(mark(X))
4.33/1.95	   MARK(p(X)) -> MARK(X)
4.33/1.95	
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	We have to consider all minimal (P,Q,R)-chains.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(13) DependencyGraphProof (EQUIVALENT)
4.33/1.95	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(14)
4.33/1.95	Obligation:
4.33/1.95	Q DP problem:
4.33/1.95	The TRS P consists of the following rules:
4.33/1.95	
4.33/1.95	   MARK(p(X)) -> MARK(X)
4.33/1.95	
4.33/1.95	The TRS R consists of the following rules:
4.33/1.95	
4.33/1.95	   a__f(s(0)) -> a__f(a__p(s(0)))
4.33/1.95	   mark(p(X)) -> a__p(mark(X))
4.33/1.95	   a__p(X) -> p(X)
4.33/1.95	
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	We have to consider all minimal (P,Q,R)-chains.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(15) UsableRulesProof (EQUIVALENT)
4.33/1.95	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.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(16)
4.33/1.95	Obligation:
4.33/1.95	Q DP problem:
4.33/1.95	The TRS P consists of the following rules:
4.33/1.95	
4.33/1.95	   MARK(p(X)) -> MARK(X)
4.33/1.95	
4.33/1.95	R is empty.
4.33/1.95	The set Q consists of the following terms:
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	We have to consider all minimal (P,Q,R)-chains.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(17) QReductionProof (EQUIVALENT)
4.33/1.95	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.33/1.95	
4.33/1.95	   mark(f(x0))
4.33/1.95	   mark(p(x0))
4.33/1.95	   mark(0)
4.33/1.95	   mark(cons(x0, x1))
4.33/1.95	   mark(s(x0))
4.33/1.95	   a__f(x0)
4.33/1.95	   a__p(x0)
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(18)
4.33/1.95	Obligation:
4.33/1.95	Q DP problem:
4.33/1.95	The TRS P consists of the following rules:
4.33/1.95	
4.33/1.95	   MARK(p(X)) -> MARK(X)
4.33/1.95	
4.33/1.95	R is empty.
4.33/1.95	Q is empty.
4.33/1.95	We have to consider all minimal (P,Q,R)-chains.
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(19) QDPSizeChangeProof (EQUIVALENT)
4.33/1.95	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.33/1.95	
4.33/1.95	From the DPs we obtained the following set of size-change graphs:
4.33/1.95	*MARK(p(X)) -> MARK(X)
4.33/1.95	The graph contains the following edges 1 > 1
4.33/1.95	
4.33/1.95	
4.33/1.95	----------------------------------------
4.33/1.95	
4.33/1.95	(20)
4.33/1.95	YES
4.36/1.99	EOF