6.25/2.44	YES
6.25/2.45	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.25/2.45	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.25/2.45	
6.25/2.45	
6.25/2.45	Termination w.r.t. Q of the given QTRS could be proven:
6.25/2.45	
6.25/2.45	(0) QTRS
6.25/2.45	(1) DependencyPairsProof [EQUIVALENT, 54 ms]
6.25/2.45	(2) QDP
6.25/2.45	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
6.25/2.45	(4) QDP
6.25/2.45	(5) QDPOrderProof [EQUIVALENT, 75 ms]
6.25/2.45	(6) QDP
6.25/2.45	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
6.25/2.45	(8) TRUE
6.25/2.45	
6.25/2.45	
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(0)
6.25/2.45	Obligation:
6.25/2.45	Q restricted rewrite system:
6.25/2.45	The TRS R consists of the following rules:
6.25/2.45	
6.25/2.45	   a__app(nil, YS) -> mark(YS)
6.25/2.45	   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
6.25/2.45	   a__from(X) -> cons(mark(X), from(s(X)))
6.25/2.45	   a__zWadr(nil, YS) -> nil
6.25/2.45	   a__zWadr(XS, nil) -> nil
6.25/2.45	   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
6.25/2.45	   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
6.25/2.45	   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
6.25/2.45	   mark(from(X)) -> a__from(mark(X))
6.25/2.45	   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
6.25/2.45	   mark(prefix(X)) -> a__prefix(mark(X))
6.25/2.45	   mark(nil) -> nil
6.25/2.45	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.25/2.45	   mark(s(X)) -> s(mark(X))
6.25/2.45	   a__app(X1, X2) -> app(X1, X2)
6.25/2.45	   a__from(X) -> from(X)
6.25/2.45	   a__zWadr(X1, X2) -> zWadr(X1, X2)
6.25/2.45	   a__prefix(X) -> prefix(X)
6.25/2.45	
6.25/2.45	The set Q consists of the following terms:
6.25/2.45	
6.25/2.45	   a__from(x0)
6.25/2.45	   a__prefix(x0)
6.25/2.45	   mark(app(x0, x1))
6.25/2.45	   mark(from(x0))
6.25/2.45	   mark(zWadr(x0, x1))
6.25/2.45	   mark(prefix(x0))
6.25/2.45	   mark(nil)
6.25/2.45	   mark(cons(x0, x1))
6.25/2.45	   mark(s(x0))
6.25/2.45	   a__app(x0, x1)
6.25/2.45	   a__zWadr(x0, x1)
6.25/2.45	
6.25/2.45	
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(1) DependencyPairsProof (EQUIVALENT)
6.25/2.45	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(2)
6.25/2.45	Obligation:
6.25/2.45	Q DP problem:
6.25/2.45	The TRS P consists of the following rules:
6.25/2.45	
6.25/2.45	   A__APP(nil, YS) -> MARK(YS)
6.25/2.45	   A__APP(cons(X, XS), YS) -> MARK(X)
6.25/2.45	   A__FROM(X) -> MARK(X)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)
6.25/2.45	   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(from(X)) -> A__FROM(mark(X))
6.25/2.45	   MARK(from(X)) -> MARK(X)
6.25/2.45	   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(prefix(X)) -> A__PREFIX(mark(X))
6.25/2.45	   MARK(prefix(X)) -> MARK(X)
6.25/2.45	   MARK(cons(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(s(X)) -> MARK(X)
6.25/2.45	
6.25/2.45	The TRS R consists of the following rules:
6.25/2.45	
6.25/2.45	   a__app(nil, YS) -> mark(YS)
6.25/2.45	   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
6.25/2.45	   a__from(X) -> cons(mark(X), from(s(X)))
6.25/2.45	   a__zWadr(nil, YS) -> nil
6.25/2.45	   a__zWadr(XS, nil) -> nil
6.25/2.45	   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
6.25/2.45	   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
6.25/2.45	   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
6.25/2.45	   mark(from(X)) -> a__from(mark(X))
6.25/2.45	   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
6.25/2.45	   mark(prefix(X)) -> a__prefix(mark(X))
6.25/2.45	   mark(nil) -> nil
6.25/2.45	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.25/2.45	   mark(s(X)) -> s(mark(X))
6.25/2.45	   a__app(X1, X2) -> app(X1, X2)
6.25/2.45	   a__from(X) -> from(X)
6.25/2.45	   a__zWadr(X1, X2) -> zWadr(X1, X2)
6.25/2.45	   a__prefix(X) -> prefix(X)
6.25/2.45	
6.25/2.45	The set Q consists of the following terms:
6.25/2.45	
6.25/2.45	   a__from(x0)
6.25/2.45	   a__prefix(x0)
6.25/2.45	   mark(app(x0, x1))
6.25/2.45	   mark(from(x0))
6.25/2.45	   mark(zWadr(x0, x1))
6.25/2.45	   mark(prefix(x0))
6.25/2.45	   mark(nil)
6.25/2.45	   mark(cons(x0, x1))
6.25/2.45	   mark(s(x0))
6.25/2.45	   a__app(x0, x1)
6.25/2.45	   a__zWadr(x0, x1)
6.25/2.45	
6.25/2.45	We have to consider all minimal (P,Q,R)-chains.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(3) DependencyGraphProof (EQUIVALENT)
6.25/2.45	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(4)
6.25/2.45	Obligation:
6.25/2.45	Q DP problem:
6.25/2.45	The TRS P consists of the following rules:
6.25/2.45	
6.25/2.45	   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
6.25/2.45	   A__APP(nil, YS) -> MARK(YS)
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(from(X)) -> A__FROM(mark(X))
6.25/2.45	   A__FROM(X) -> MARK(X)
6.25/2.45	   MARK(from(X)) -> MARK(X)
6.25/2.45	   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))
6.25/2.45	   A__APP(cons(X, XS), YS) -> MARK(X)
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(prefix(X)) -> MARK(X)
6.25/2.45	   MARK(cons(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(s(X)) -> MARK(X)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)
6.25/2.45	
6.25/2.45	The TRS R consists of the following rules:
6.25/2.45	
6.25/2.45	   a__app(nil, YS) -> mark(YS)
6.25/2.45	   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
6.25/2.45	   a__from(X) -> cons(mark(X), from(s(X)))
6.25/2.45	   a__zWadr(nil, YS) -> nil
6.25/2.45	   a__zWadr(XS, nil) -> nil
6.25/2.45	   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
6.25/2.45	   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
6.25/2.45	   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
6.25/2.45	   mark(from(X)) -> a__from(mark(X))
6.25/2.45	   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
6.25/2.45	   mark(prefix(X)) -> a__prefix(mark(X))
6.25/2.45	   mark(nil) -> nil
6.25/2.45	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.25/2.45	   mark(s(X)) -> s(mark(X))
6.25/2.45	   a__app(X1, X2) -> app(X1, X2)
6.25/2.45	   a__from(X) -> from(X)
6.25/2.45	   a__zWadr(X1, X2) -> zWadr(X1, X2)
6.25/2.45	   a__prefix(X) -> prefix(X)
6.25/2.45	
6.25/2.45	The set Q consists of the following terms:
6.25/2.45	
6.25/2.45	   a__from(x0)
6.25/2.45	   a__prefix(x0)
6.25/2.45	   mark(app(x0, x1))
6.25/2.45	   mark(from(x0))
6.25/2.45	   mark(zWadr(x0, x1))
6.25/2.45	   mark(prefix(x0))
6.25/2.45	   mark(nil)
6.25/2.45	   mark(cons(x0, x1))
6.25/2.45	   mark(s(x0))
6.25/2.45	   a__app(x0, x1)
6.25/2.45	   a__zWadr(x0, x1)
6.25/2.45	
6.25/2.45	We have to consider all minimal (P,Q,R)-chains.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(5) QDPOrderProof (EQUIVALENT)
6.25/2.45	We use the reduction pair processor [LPAR04,JAR06].
6.25/2.45	
6.25/2.45	
6.25/2.45	The following pairs can be oriented strictly and are deleted.
6.25/2.45	
6.25/2.45	   A__APP(nil, YS) -> MARK(YS)
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(app(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(from(X)) -> A__FROM(mark(X))
6.25/2.45	   MARK(from(X)) -> MARK(X)
6.25/2.45	   A__APP(cons(X, XS), YS) -> MARK(X)
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(zWadr(X1, X2)) -> MARK(X2)
6.25/2.45	   MARK(prefix(X)) -> MARK(X)
6.25/2.45	   MARK(cons(X1, X2)) -> MARK(X1)
6.25/2.45	   MARK(s(X)) -> MARK(X)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)
6.25/2.45	The remaining pairs can at least be oriented weakly.
6.25/2.45	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
6.25/2.45	
6.25/2.45	POL( A__APP_2(x_1, x_2) ) = x_1 + x_2 + 2
6.25/2.45	POL( A__FROM_1(x_1) ) = x_1
6.25/2.45	POL( A__ZWADR_2(x_1, x_2) ) = x_1 + x_2 + 1
6.25/2.45	POL( mark_1(x_1) ) = x_1
6.25/2.45	POL( app_2(x_1, x_2) ) = x_1 + x_2 + 2
6.25/2.45	POL( a__app_2(x_1, x_2) ) = x_1 + x_2 + 2
6.25/2.45	POL( nil ) = 0
6.25/2.45	POL( from_1(x_1) ) = 2x_1 + 2
6.25/2.45	POL( a__from_1(x_1) ) = 2x_1 + 2
6.25/2.45	POL( zWadr_2(x_1, x_2) ) = 2x_1 + x_2 + 1
6.25/2.45	POL( a__zWadr_2(x_1, x_2) ) = 2x_1 + x_2 + 1
6.25/2.45	POL( prefix_1(x_1) ) = x_1 + 1
6.25/2.45	POL( a__prefix_1(x_1) ) = x_1 + 1
6.25/2.45	POL( cons_2(x_1, x_2) ) = x_1 + 1
6.25/2.45	POL( s_1(x_1) ) = x_1 + 1
6.25/2.45	POL( MARK_1(x_1) ) = x_1
6.25/2.45	
6.25/2.45	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
6.25/2.45	
6.25/2.45	   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
6.25/2.45	   a__app(nil, YS) -> mark(YS)
6.25/2.45	   mark(from(X)) -> a__from(mark(X))
6.25/2.45	   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
6.25/2.45	   mark(prefix(X)) -> a__prefix(mark(X))
6.25/2.45	   mark(nil) -> nil
6.25/2.45	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.25/2.45	   mark(s(X)) -> s(mark(X))
6.25/2.45	   a__app(X1, X2) -> app(X1, X2)
6.25/2.45	   a__from(X) -> from(X)
6.25/2.45	   a__zWadr(nil, YS) -> nil
6.25/2.45	   a__zWadr(XS, nil) -> nil
6.25/2.45	   a__zWadr(X1, X2) -> zWadr(X1, X2)
6.25/2.45	   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
6.25/2.45	   a__prefix(X) -> prefix(X)
6.25/2.45	   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
6.25/2.45	   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
6.25/2.45	   a__from(X) -> cons(mark(X), from(s(X)))
6.25/2.45	
6.25/2.45	
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(6)
6.25/2.45	Obligation:
6.25/2.45	Q DP problem:
6.25/2.45	The TRS P consists of the following rules:
6.25/2.45	
6.25/2.45	   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
6.25/2.45	   A__FROM(X) -> MARK(X)
6.25/2.45	   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
6.25/2.45	   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))
6.25/2.45	
6.25/2.45	The TRS R consists of the following rules:
6.25/2.45	
6.25/2.45	   a__app(nil, YS) -> mark(YS)
6.25/2.45	   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
6.25/2.45	   a__from(X) -> cons(mark(X), from(s(X)))
6.25/2.45	   a__zWadr(nil, YS) -> nil
6.25/2.45	   a__zWadr(XS, nil) -> nil
6.25/2.45	   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
6.25/2.45	   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
6.25/2.45	   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
6.25/2.45	   mark(from(X)) -> a__from(mark(X))
6.25/2.45	   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
6.25/2.45	   mark(prefix(X)) -> a__prefix(mark(X))
6.25/2.45	   mark(nil) -> nil
6.25/2.45	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
6.25/2.45	   mark(s(X)) -> s(mark(X))
6.25/2.45	   a__app(X1, X2) -> app(X1, X2)
6.25/2.45	   a__from(X) -> from(X)
6.25/2.45	   a__zWadr(X1, X2) -> zWadr(X1, X2)
6.25/2.45	   a__prefix(X) -> prefix(X)
6.25/2.45	
6.25/2.45	The set Q consists of the following terms:
6.25/2.45	
6.25/2.45	   a__from(x0)
6.25/2.45	   a__prefix(x0)
6.25/2.45	   mark(app(x0, x1))
6.25/2.45	   mark(from(x0))
6.25/2.45	   mark(zWadr(x0, x1))
6.25/2.45	   mark(prefix(x0))
6.25/2.45	   mark(nil)
6.25/2.45	   mark(cons(x0, x1))
6.25/2.45	   mark(s(x0))
6.25/2.45	   a__app(x0, x1)
6.25/2.45	   a__zWadr(x0, x1)
6.25/2.45	
6.25/2.45	We have to consider all minimal (P,Q,R)-chains.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(7) DependencyGraphProof (EQUIVALENT)
6.25/2.45	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes.
6.25/2.45	----------------------------------------
6.25/2.45	
6.25/2.45	(8)
6.25/2.45	TRUE
6.25/2.48	EOF