6.19/2.51	YES
6.23/2.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.23/2.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.23/2.54	
6.23/2.54	
6.23/2.54	Termination w.r.t. Q of the given QTRS could be proven:
6.23/2.54	
6.23/2.54	(0) QTRS
6.23/2.54	(1) QTRSRRRProof [EQUIVALENT, 57 ms]
6.23/2.54	(2) QTRS
6.23/2.54	(3) QTRSRRRProof [EQUIVALENT, 11 ms]
6.23/2.54	(4) QTRS
6.23/2.54	(5) QTRSRRRProof [EQUIVALENT, 13 ms]
6.23/2.54	(6) QTRS
6.23/2.54	(7) QTRSRRRProof [EQUIVALENT, 15 ms]
6.23/2.54	(8) QTRS
6.23/2.54	(9) QTRSRRRProof [EQUIVALENT, 0 ms]
6.23/2.54	(10) QTRS
6.23/2.54	(11) QTRSRRRProof [EQUIVALENT, 0 ms]
6.23/2.54	(12) QTRS
6.23/2.54	(13) QTRSRRRProof [EQUIVALENT, 9 ms]
6.23/2.54	(14) QTRS
6.23/2.54	(15) DependencyPairsProof [EQUIVALENT, 23 ms]
6.23/2.54	(16) QDP
6.23/2.54	(17) DependencyGraphProof [EQUIVALENT, 0 ms]
6.23/2.54	(18) QDP
6.23/2.54	(19) QReductionProof [EQUIVALENT, 0 ms]
6.23/2.54	(20) QDP
6.23/2.54	(21) MRRProof [EQUIVALENT, 0 ms]
6.23/2.54	(22) QDP
6.23/2.54	(23) DependencyGraphProof [EQUIVALENT, 0 ms]
6.23/2.54	(24) QDP
6.23/2.54	(25) QDPOrderProof [EQUIVALENT, 20 ms]
6.23/2.54	(26) QDP
6.23/2.54	(27) UsableRulesProof [EQUIVALENT, 0 ms]
6.23/2.54	(28) QDP
6.23/2.54	(29) QReductionProof [EQUIVALENT, 0 ms]
6.23/2.54	(30) QDP
6.23/2.54	(31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.23/2.54	(32) YES
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(0)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   a__head(cons(X, XS)) -> mark(X)
6.23/2.54	   a__tail(cons(X, XS)) -> mark(XS)
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(head(X)) -> a__head(mark(X))
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__head(X) -> head(X)
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(1) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__head(x_1)) = 1 + x_1
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = x_1
6.23/2.54	   POL(cons(x_1, x_2)) = x_1 + 2*x_2
6.23/2.54	   POL(head(x_1)) = 1 + x_1
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	   POL(tail(x_1)) = x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   a__head(cons(X, XS)) -> mark(X)
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(2)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   a__tail(cons(X, XS)) -> mark(XS)
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(head(X)) -> a__head(mark(X))
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__head(X) -> head(X)
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(3) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__head(x_1)) = 1 + 2*x_1
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = 2*x_1
6.23/2.54	   POL(cons(x_1, x_2)) = x_1 + 2*x_2
6.23/2.54	   POL(head(x_1)) = 1 + 2*x_1
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = 2*x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	   POL(tail(x_1)) = 2*x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   mark(head(X)) -> a__head(mark(X))
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(4)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   a__tail(cons(X, XS)) -> mark(XS)
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__head(X) -> head(X)
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(5) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__head(x_1)) = 1 + 2*x_1
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = 2*x_1
6.23/2.54	   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
6.23/2.54	   POL(head(x_1)) = 2*x_1
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = 2*x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	   POL(tail(x_1)) = 2*x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   a__head(X) -> head(X)
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(6)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   a__tail(cons(X, XS)) -> mark(XS)
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(7) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = 1 + 2*x_1
6.23/2.54	   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = 2*x_1
6.23/2.54	   POL(tail(x_1)) = 1 + 2*x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   a__tail(cons(X, XS)) -> mark(XS)
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(8)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(9) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = 1 + 2*x_1
6.23/2.54	   POL(cons(x_1, x_2)) = x_1 + 2*x_2
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = 2*x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	   POL(tail(x_1)) = 1 + 2*x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   mark(tail(X)) -> a__tail(mark(X))
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(10)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(11) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(a__tail(x_1)) = 1 + x_1
6.23/2.54	   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = 2*x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	   POL(tail(x_1)) = x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   a__tail(X) -> tail(X)
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(12)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__nats -> nats
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(13) QTRSRRRProof (EQUIVALENT)
6.23/2.54	Used ordering:
6.23/2.54	Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(a__incr(x_1)) = 2*x_1
6.23/2.54	   POL(a__nats) = 2
6.23/2.54	   POL(a__odds) = 0
6.23/2.54	   POL(a__pairs) = 0
6.23/2.54	   POL(cons(x_1, x_2)) = x_1 + x_2
6.23/2.54	   POL(incr(x_1)) = 2*x_1
6.23/2.54	   POL(mark(x_1)) = 2*x_1
6.23/2.54	   POL(nats) = 1
6.23/2.54	   POL(odds) = 0
6.23/2.54	   POL(pairs) = 0
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.23/2.54	
6.23/2.54	   a__nats -> nats
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(14)
6.23/2.54	Obligation:
6.23/2.54	Q restricted rewrite system:
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(15) DependencyPairsProof (EQUIVALENT)
6.23/2.54	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(16)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   A__ODDS -> A__INCR(a__pairs)
6.23/2.54	   A__ODDS -> A__PAIRS
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(nats) -> A__NATS
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   MARK(pairs) -> A__PAIRS
6.23/2.54	   MARK(odds) -> A__ODDS
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(17) DependencyGraphProof (EQUIVALENT)
6.23/2.54	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(18)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   MARK(odds) -> A__ODDS
6.23/2.54	   A__ODDS -> A__INCR(a__pairs)
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(19) QReductionProof (EQUIVALENT)
6.23/2.54	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
6.23/2.54	
6.23/2.54	   a__head(x0)
6.23/2.54	   a__tail(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(20)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   MARK(odds) -> A__ODDS
6.23/2.54	   A__ODDS -> A__INCR(a__pairs)
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(21) MRRProof (EQUIVALENT)
6.23/2.54	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.
6.23/2.54	
6.23/2.54	Strictly oriented dependency pairs:
6.23/2.54	
6.23/2.54	   MARK(odds) -> A__ODDS
6.23/2.54	
6.23/2.54	
6.23/2.54	Used ordering: Polynomial interpretation [POLO]:
6.23/2.54	
6.23/2.54	   POL(0) = 0
6.23/2.54	   POL(A__INCR(x_1)) = x_1
6.23/2.54	   POL(A__ODDS) = 2
6.23/2.54	   POL(MARK(x_1)) = 2*x_1
6.23/2.54	   POL(a__incr(x_1)) = x_1
6.23/2.54	   POL(a__nats) = 0
6.23/2.54	   POL(a__odds) = 2
6.23/2.54	   POL(a__pairs) = 2
6.23/2.54	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
6.23/2.54	   POL(incr(x_1)) = x_1
6.23/2.54	   POL(mark(x_1)) = x_1
6.23/2.54	   POL(nats) = 0
6.23/2.54	   POL(odds) = 2
6.23/2.54	   POL(pairs) = 2
6.23/2.54	   POL(s(x_1)) = x_1
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(22)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   A__ODDS -> A__INCR(a__pairs)
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(23) DependencyGraphProof (EQUIVALENT)
6.23/2.54	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(24)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(25) QDPOrderProof (EQUIVALENT)
6.23/2.54	We use the reduction pair processor [LPAR04,JAR06].
6.23/2.54	
6.23/2.54	
6.23/2.54	The following pairs can be oriented strictly and are deleted.
6.23/2.54	
6.23/2.54	   MARK(incr(X)) -> A__INCR(mark(X))
6.23/2.54	   A__INCR(cons(X, XS)) -> MARK(X)
6.23/2.54	   MARK(incr(X)) -> MARK(X)
6.23/2.54	   MARK(cons(X1, X2)) -> MARK(X1)
6.23/2.54	The remaining pairs can at least be oriented weakly.
6.23/2.54	Used ordering:  Combined order from the following AFS and order.
6.23/2.54	MARK(x1)  =  MARK(x1)
6.23/2.54	
6.23/2.54	incr(x1)  =  incr(x1)
6.23/2.54	
6.23/2.54	A__INCR(x1)  =  A__INCR(x1)
6.23/2.54	
6.23/2.54	mark(x1)  =  mark(x1)
6.23/2.54	
6.23/2.54	cons(x1, x2)  =  cons(x1)
6.23/2.54	
6.23/2.54	s(x1)  =  x1
6.23/2.54	
6.23/2.54	nats  =  nats
6.23/2.54	
6.23/2.54	a__nats  =  a__nats
6.23/2.54	
6.23/2.54	a__incr(x1)  =  a__incr(x1)
6.23/2.54	
6.23/2.54	pairs  =  pairs
6.23/2.54	
6.23/2.54	a__pairs  =  a__pairs
6.23/2.54	
6.23/2.54	odds  =  odds
6.23/2.54	
6.23/2.54	a__odds  =  a__odds
6.23/2.54	
6.23/2.54	0  =  0
6.23/2.54	
6.23/2.54	
6.23/2.54	Recursive path order with status [RPO].
6.23/2.54	Quasi-Precedence: nats > a__nats > [incr_1, mark_1, a__incr_1, a__pairs] > [MARK_1, cons_1] > A__INCR_1
6.23/2.54	nats > a__nats > [incr_1, mark_1, a__incr_1, a__pairs] > pairs
6.23/2.54	nats > a__nats > [incr_1, mark_1, a__incr_1, a__pairs] > 0
6.23/2.54	[odds, a__odds] > [incr_1, mark_1, a__incr_1, a__pairs] > [MARK_1, cons_1] > A__INCR_1
6.23/2.54	[odds, a__odds] > [incr_1, mark_1, a__incr_1, a__pairs] > pairs
6.23/2.54	[odds, a__odds] > [incr_1, mark_1, a__incr_1, a__pairs] > 0
6.23/2.54	
6.23/2.54	Status: MARK_1: [1]
6.23/2.54	incr_1: [1]
6.23/2.54	A__INCR_1: multiset status
6.23/2.54	mark_1: [1]
6.23/2.54	cons_1: [1]
6.23/2.54	nats: multiset status
6.23/2.54	a__nats: multiset status
6.23/2.54	a__incr_1: [1]
6.23/2.54	pairs: multiset status
6.23/2.54	a__pairs: multiset status
6.23/2.54	odds: multiset status
6.23/2.54	a__odds: multiset status
6.23/2.54	0: multiset status
6.23/2.54	
6.23/2.54	
6.23/2.54	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
6.23/2.54	
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__odds -> odds
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(26)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	The TRS R consists of the following rules:
6.23/2.54	
6.23/2.54	   a__nats -> cons(0, incr(nats))
6.23/2.54	   a__pairs -> cons(0, incr(odds))
6.23/2.54	   a__odds -> a__incr(a__pairs)
6.23/2.54	   a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
6.23/2.54	   mark(nats) -> a__nats
6.23/2.54	   mark(incr(X)) -> a__incr(mark(X))
6.23/2.54	   mark(pairs) -> a__pairs
6.23/2.54	   mark(odds) -> a__odds
6.23/2.54	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.23/2.54	   mark(0) -> 0
6.23/2.54	   mark(s(X)) -> s(mark(X))
6.23/2.54	   a__incr(X) -> incr(X)
6.23/2.54	   a__pairs -> pairs
6.23/2.54	   a__odds -> odds
6.23/2.54	
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(27) UsableRulesProof (EQUIVALENT)
6.23/2.54	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.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(28)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	R is empty.
6.23/2.54	The set Q consists of the following terms:
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(29) QReductionProof (EQUIVALENT)
6.23/2.54	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
6.23/2.54	
6.23/2.54	   a__nats
6.23/2.54	   a__pairs
6.23/2.54	   a__odds
6.23/2.54	   mark(nats)
6.23/2.54	   mark(incr(x0))
6.23/2.54	   mark(pairs)
6.23/2.54	   mark(odds)
6.23/2.54	   mark(head(x0))
6.23/2.54	   mark(tail(x0))
6.23/2.54	   mark(cons(x0, x1))
6.23/2.54	   mark(0)
6.23/2.54	   mark(s(x0))
6.23/2.54	   a__incr(x0)
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(30)
6.23/2.54	Obligation:
6.23/2.54	Q DP problem:
6.23/2.54	The TRS P consists of the following rules:
6.23/2.54	
6.23/2.54	   MARK(s(X)) -> MARK(X)
6.23/2.54	
6.23/2.54	R is empty.
6.23/2.54	Q is empty.
6.23/2.54	We have to consider all minimal (P,Q,R)-chains.
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(31) QDPSizeChangeProof (EQUIVALENT)
6.23/2.54	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.23/2.54	
6.23/2.54	From the DPs we obtained the following set of size-change graphs:
6.23/2.54	*MARK(s(X)) -> MARK(X)
6.23/2.54	The graph contains the following edges 1 > 1
6.23/2.54	
6.23/2.54	
6.23/2.54	----------------------------------------
6.23/2.54	
6.23/2.54	(32)
6.23/2.54	YES
6.23/2.58	EOF