/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 58 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) QDP
(5) QDPOrderProof [EQUIVALENT, 78 ms]
(6) QDP
(7) DependencyGraphProof [EQUIVALENT, 0 ms]
(8) TRUE


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   a__app(nil, YS) -> mark(YS)
   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
   a__from(X) -> cons(mark(X), from(s(X)))
   a__zWadr(nil, YS) -> nil
   a__zWadr(XS, nil) -> nil
   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
   mark(from(X)) -> a__from(mark(X))
   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
   mark(prefix(X)) -> a__prefix(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   a__app(X1, X2) -> app(X1, X2)
   a__from(X) -> from(X)
   a__zWadr(X1, X2) -> zWadr(X1, X2)
   a__prefix(X) -> prefix(X)

The set Q consists of the following terms:

   a__from(x0)
   a__prefix(x0)
   mark(app(x0, x1))
   mark(from(x0))
   mark(zWadr(x0, x1))
   mark(prefix(x0))
   mark(nil)
   mark(cons(x0, x1))
   mark(s(x0))
   a__app(x0, x1)
   a__zWadr(x0, x1)


----------------------------------------

(1) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(2)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   A__APP(nil, YS) -> MARK(YS)
   A__APP(cons(X, XS), YS) -> MARK(X)
   A__FROM(X) -> MARK(X)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)
   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
   MARK(app(X1, X2)) -> MARK(X1)
   MARK(app(X1, X2)) -> MARK(X2)
   MARK(from(X)) -> A__FROM(mark(X))
   MARK(from(X)) -> MARK(X)
   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
   MARK(zWadr(X1, X2)) -> MARK(X1)
   MARK(zWadr(X1, X2)) -> MARK(X2)
   MARK(prefix(X)) -> A__PREFIX(mark(X))
   MARK(prefix(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(s(X)) -> MARK(X)

The TRS R consists of the following rules:

   a__app(nil, YS) -> mark(YS)
   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
   a__from(X) -> cons(mark(X), from(s(X)))
   a__zWadr(nil, YS) -> nil
   a__zWadr(XS, nil) -> nil
   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
   mark(from(X)) -> a__from(mark(X))
   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
   mark(prefix(X)) -> a__prefix(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   a__app(X1, X2) -> app(X1, X2)
   a__from(X) -> from(X)
   a__zWadr(X1, X2) -> zWadr(X1, X2)
   a__prefix(X) -> prefix(X)

The set Q consists of the following terms:

   a__from(x0)
   a__prefix(x0)
   mark(app(x0, x1))
   mark(from(x0))
   mark(zWadr(x0, x1))
   mark(prefix(x0))
   mark(nil)
   mark(cons(x0, x1))
   mark(s(x0))
   a__app(x0, x1)
   a__zWadr(x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(3) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(4)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
   A__APP(nil, YS) -> MARK(YS)
   MARK(app(X1, X2)) -> MARK(X1)
   MARK(app(X1, X2)) -> MARK(X2)
   MARK(from(X)) -> A__FROM(mark(X))
   A__FROM(X) -> MARK(X)
   MARK(from(X)) -> MARK(X)
   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))
   A__APP(cons(X, XS), YS) -> MARK(X)
   MARK(zWadr(X1, X2)) -> MARK(X1)
   MARK(zWadr(X1, X2)) -> MARK(X2)
   MARK(prefix(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(s(X)) -> MARK(X)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)

The TRS R consists of the following rules:

   a__app(nil, YS) -> mark(YS)
   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
   a__from(X) -> cons(mark(X), from(s(X)))
   a__zWadr(nil, YS) -> nil
   a__zWadr(XS, nil) -> nil
   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
   mark(from(X)) -> a__from(mark(X))
   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
   mark(prefix(X)) -> a__prefix(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   a__app(X1, X2) -> app(X1, X2)
   a__from(X) -> from(X)
   a__zWadr(X1, X2) -> zWadr(X1, X2)
   a__prefix(X) -> prefix(X)

The set Q consists of the following terms:

   a__from(x0)
   a__prefix(x0)
   mark(app(x0, x1))
   mark(from(x0))
   mark(zWadr(x0, x1))
   mark(prefix(x0))
   mark(nil)
   mark(cons(x0, x1))
   mark(s(x0))
   a__app(x0, x1)
   a__zWadr(x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(5) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   A__APP(nil, YS) -> MARK(YS)
   MARK(app(X1, X2)) -> MARK(X1)
   MARK(app(X1, X2)) -> MARK(X2)
   MARK(from(X)) -> A__FROM(mark(X))
   MARK(from(X)) -> MARK(X)
   A__APP(cons(X, XS), YS) -> MARK(X)
   MARK(zWadr(X1, X2)) -> MARK(X1)
   MARK(zWadr(X1, X2)) -> MARK(X2)
   MARK(prefix(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(s(X)) -> MARK(X)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(Y)
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> MARK(X)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( A__APP_2(x_1, x_2) ) = x_1 + x_2 + 2
POL( A__FROM_1(x_1) ) = x_1
POL( A__ZWADR_2(x_1, x_2) ) = x_1 + x_2 + 1
POL( mark_1(x_1) ) = x_1
POL( app_2(x_1, x_2) ) = x_1 + x_2 + 2
POL( a__app_2(x_1, x_2) ) = x_1 + x_2 + 2
POL( nil ) = 0
POL( from_1(x_1) ) = 2x_1 + 2
POL( a__from_1(x_1) ) = 2x_1 + 2
POL( zWadr_2(x_1, x_2) ) = 2x_1 + x_2 + 1
POL( a__zWadr_2(x_1, x_2) ) = 2x_1 + x_2 + 1
POL( prefix_1(x_1) ) = x_1 + 1
POL( a__prefix_1(x_1) ) = x_1 + 1
POL( cons_2(x_1, x_2) ) = x_1 + 1
POL( s_1(x_1) ) = x_1 + 1
POL( MARK_1(x_1) ) = x_1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
   a__app(nil, YS) -> mark(YS)
   mark(from(X)) -> a__from(mark(X))
   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
   mark(prefix(X)) -> a__prefix(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   a__app(X1, X2) -> app(X1, X2)
   a__from(X) -> from(X)
   a__zWadr(nil, YS) -> nil
   a__zWadr(XS, nil) -> nil
   a__zWadr(X1, X2) -> zWadr(X1, X2)
   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
   a__prefix(X) -> prefix(X)
   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
   a__from(X) -> cons(mark(X), from(s(X)))


----------------------------------------

(6)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(app(X1, X2)) -> A__APP(mark(X1), mark(X2))
   A__FROM(X) -> MARK(X)
   MARK(zWadr(X1, X2)) -> A__ZWADR(mark(X1), mark(X2))
   A__ZWADR(cons(X, XS), cons(Y, YS)) -> A__APP(mark(Y), cons(mark(X), nil))

The TRS R consists of the following rules:

   a__app(nil, YS) -> mark(YS)
   a__app(cons(X, XS), YS) -> cons(mark(X), app(XS, YS))
   a__from(X) -> cons(mark(X), from(s(X)))
   a__zWadr(nil, YS) -> nil
   a__zWadr(XS, nil) -> nil
   a__zWadr(cons(X, XS), cons(Y, YS)) -> cons(a__app(mark(Y), cons(mark(X), nil)), zWadr(XS, YS))
   a__prefix(L) -> cons(nil, zWadr(L, prefix(L)))
   mark(app(X1, X2)) -> a__app(mark(X1), mark(X2))
   mark(from(X)) -> a__from(mark(X))
   mark(zWadr(X1, X2)) -> a__zWadr(mark(X1), mark(X2))
   mark(prefix(X)) -> a__prefix(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   a__app(X1, X2) -> app(X1, X2)
   a__from(X) -> from(X)
   a__zWadr(X1, X2) -> zWadr(X1, X2)
   a__prefix(X) -> prefix(X)

The set Q consists of the following terms:

   a__from(x0)
   a__prefix(x0)
   mark(app(x0, x1))
   mark(from(x0))
   mark(zWadr(x0, x1))
   mark(prefix(x0))
   mark(nil)
   mark(cons(x0, x1))
   mark(s(x0))
   a__app(x0, x1)
   a__zWadr(x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(7) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes.
----------------------------------------

(8)
TRUE