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


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


YES

We split firstr-order part and higher-order part, and do modular checking by a general modularity.

******** FO SN check ********
Check SN using AProVE (RWTH Aachen University)
proof of tmp8651.trs
# AProVE Commit ID: 240871ee8d33536d563834eff18151406a8bc3fe ffrohn 20170821 unpublished


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

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 0 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 2 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (9) YES
    (10) QDP
        (11) QDPOrderProof [EQUIVALENT, 73 ms]
        (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES


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

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

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

Q is empty.

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

(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:

   XBTIMES(X, xbplus(Y, U)) -> XBPLUS(xbtimes(X, Y), xbtimes(X, U))
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(xbplus(W, P), V) -> XBPLUS(xbtimes(V, W), xbtimes(V, P))
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

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

(4)
Complex Obligation (AND)

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

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

   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

(6) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))

The TRS R consists of the following rules:

   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))

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

(8) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
The graph contains the following edges 1 > 1, 2 >= 2


*XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))
The graph contains the following edges 1 > 1


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

(9)
YES

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

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

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


The following pairs can be oriented strictly and are deleted.

   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(XBTIMES(x_1, x_2)) = x_1 + x_1*x_2
   POL(xbplus(x_1, x_2)) = 1 + x_1 + x_2
   POL(xbtimes(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2

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

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))


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

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

(13) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)

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

(15) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
The graph contains the following edges 1 >= 1, 2 > 2


*XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
The graph contains the following edges 1 >= 1, 2 > 2


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

(16)
YES

...
proof of tmp8651.trs
# AProVE Commit ID: 240871ee8d33536d563834eff18151406a8bc3fe ffrohn 20170821 unpublished


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

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 0 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 2 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (9) YES
    (10) QDP
        (11) QDPOrderProof [EQUIVALENT, 73 ms]
        (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES


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

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

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

Q is empty.

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

(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:

   XBTIMES(X, xbplus(Y, U)) -> XBPLUS(xbtimes(X, Y), xbtimes(X, U))
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(xbplus(W, P), V) -> XBPLUS(xbtimes(V, W), xbtimes(V, P))
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

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

(4)
Complex Obligation (AND)

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

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

   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

(6) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
   XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))

The TRS R consists of the following rules:

   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))

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

(8) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(W1, P1)
The graph contains the following edges 1 > 1, 2 >= 2


*XBPLUS(xbplus(V1, W1), P1) -> XBPLUS(V1, xbplus(W1, P1))
The graph contains the following edges 1 > 1


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

(9)
YES

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

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

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


The following pairs can be oriented strictly and are deleted.

   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, W)
   XBTIMES(xbplus(W, P), V) -> XBTIMES(V, P)
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(X1, xbtimes(Y1, U1))
   XBTIMES(xbtimes(X1, Y1), U1) -> XBTIMES(Y1, U1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(XBTIMES(x_1, x_2)) = x_1 + x_1*x_2
   POL(xbplus(x_1, x_2)) = 1 + x_1 + x_2
   POL(xbtimes(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2

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

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))


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

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)

The TRS R consists of the following rules:

   xbtimes(X, xbplus(Y, U)) -> xbplus(xbtimes(X, Y), xbtimes(X, U))
   xbtimes(xbplus(W, P), V) -> xbplus(xbtimes(V, W), xbtimes(V, P))
   xbtimes(xbtimes(X1, Y1), U1) -> xbtimes(X1, xbtimes(Y1, U1))
   xbplus(xbplus(V1, W1), P1) -> xbplus(V1, xbplus(W1, P1))
   _(X1, X2) -> X1
   _(X1, X2) -> X2

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

(13) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
   XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)

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

(15) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, U)
The graph contains the following edges 1 >= 1, 2 > 2


*XBTIMES(X, xbplus(Y, U)) -> XBTIMES(X, Y)
The graph contains the following edges 1 >= 1, 2 > 2


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

(16)
YES
>>YES

******** Signature ********
 map : ((c -> c),d) -> d
 nil : d
 cons : (c,d) -> d
 filter : ((c -> b),d) -> d
 filter2 : (b,(c -> b),c,d) -> d
 true : b
 false : b
******** Computation rules ********
 (5)  map(F2,nil) => nil
 (6)  map(Z2,cons(U2,V2)) => cons(Z2[U2],map(Z2,V2))
 (7)  filter(I2,nil) => nil
 (8)  filter(J2,cons(X3,Y3)) => filter2(J2[X3],J2,X3,Y3)
 (9)  filter2(true,G3,V3,W3) => cons(V3,filter(G3,W3))
 (10)  filter2(false,J3,X4,Y4) => filter(J3,Y4)


******** General Schema criterion ********
Found constructors: cons, false, nil, true
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>Regared as equal: filter2, filter
Checking  (1) xbtimes(X,xbplus(Y,U)) => xbplus(xbtimes(X,Y),xbtimes(X,U))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. LR LR
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta Y)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in Y] 
 (fun xbtimes=xbtimes) subterm comparison of args w. LR LR
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta U)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in U]  >>True
Checking  (2) xbtimes(xbplus(W,P),V) => xbplus(xbtimes(V,W),xbtimes(V,P))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) xbtimes(X,xbplus(Y,U)) => xbplus(xbtimes(X,Y),xbtimes(X,U))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. RL RL
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta Y)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in Y] 
 (fun xbtimes=xbtimes) subterm comparison of args w. RL RL
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta U)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in U]  >>True
Checking  (2) xbtimes(xbplus(W,P),V) => xbplus(xbtimes(V,W),xbtimes(V,P))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) xbtimes(X,xbplus(Y,U)) => xbplus(xbtimes(X,Y),xbtimes(X,U))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. Mul Mul
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta Y)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in Y] 
 (fun xbtimes=xbtimes) subterm comparison of args w. Mul Mul
 (meta X)[is acc in X,xbplus(Y,U)] [is acc in X] 
 (meta U)[is acc in X,xbplus(Y,U)] [is positive in xbplus(Y,U)] [is acc in U]  >>True
Checking  (2) xbtimes(xbplus(W,P),V) => xbplus(xbtimes(V,W),xbtimes(V,P))
 (fun xbtimes>xbplus)
 (fun xbtimes=xbtimes) subterm comparison of args w. Mul Mul
 (meta V)[is acc in xbplus(W,P),V] [is positive in xbplus(W,P)] [is acc in V] 
 (meta W)[is acc in xbplus(W,P),V] [is positive in xbplus(W,P)] [is acc in W] 
 (fun xbtimes=xbtimes) subterm comparison of args w. Mul Mul
 (meta V)[is acc in xbplus(W,P),V] [is positive in xbplus(W,P)] [is acc in V] 
 (meta P)[is acc in xbplus(W,P),V] [is positive in xbplus(W,P)] [is acc in P]  >>True
Checking  (3) xbtimes(xbtimes(X1,Y1),U1) => xbtimes(X1,xbtimes(Y1,U1))
 (fun xbtimes=xbtimes) subterm comparison of args w. Mul Mul >>False
Found constructors: nil, cons, true, false
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>Regared as equal: filter2, filter
Checking  (5) map(F2,nil) => nil
 (fun map>nil) >>True
Checking  (6) map(Z2,cons(U2,V2)) => cons(Z2[U2],map(Z2,V2))
 (fun map>cons)
 (meta Z2)[is acc in Z2,cons(U2,V2)] [is acc in Z2] 
 (meta U2)[is acc in Z2,cons(U2,V2)] [is positive in cons(U2,V2)] [is acc in U2] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta Z2)[is acc in Z2,cons(U2,V2)] [is acc in Z2] 
 (meta V2)[is acc in Z2,cons(U2,V2)] [is positive in cons(U2,V2)] [is acc in V2]  >>True
Checking  (7) filter(I2,nil) => nil
 (fun filter>nil) >>True
Checking  (8) filter(J2,cons(X3,Y3)) => filter2(J2[X3],J2,X3,Y3)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (meta J2)[is acc in J2,cons(X3,Y3)] [is acc in J2] 
 (meta X3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in X3] 
 (meta J2)[is acc in J2,cons(X3,Y3)] [is acc in J2] 
 (meta X3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in X3] 
 (meta Y3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in Y3]  >>True
Checking  (9) filter2(true,G3,V3,W3) => cons(V3,filter(G3,W3))
 (fun filter2>cons)
 (meta V3)[is acc in true,G3,V3,W3] [is positive in true] [is acc in V3] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta G3)[is acc in true,G3,V3,W3] [is positive in true] [is acc in G3] 
 (meta W3)[is acc in true,G3,V3,W3] [is positive in true] [is acc in W3]  >>True
Checking  (10) filter2(false,J3,X4,Y4) => filter(J3,Y4)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta J3)[is acc in false,J3,X4,Y4] [is positive in false] [is acc in J3] 
 (meta Y4)[is acc in false,J3,X4,Y4] [is positive in false] [is acc in Y4]  >>True
#SN!
******** Signature ********
 xbplus : (a,a) -> a
 xbtimes : (a,a) -> a
 cons : (c,d) -> d
 false : b
 filter : ((c -> b),d) -> d
 filter2 : (b,(c -> b),c,d) -> d
 map : ((c -> c),d) -> d
 nil : d
 true : b
******** Computation Rules ********
 (1)  xbtimes(X,xbplus(Y,U)) => xbplus(xbtimes(X,Y),xbtimes(X,U))
 (2)  xbtimes(xbplus(W,P),V) => xbplus(xbtimes(V,W),xbtimes(V,P))
 (3)  xbtimes(xbtimes(X1,Y1),U1) => xbtimes(X1,xbtimes(Y1,U1))
 (4)  xbplus(xbplus(V1,W1),P1) => xbplus(V1,xbplus(W1,P1))
 (5)  map(F2,nil) => nil
 (6)  map(Z2,cons(U2,V2)) => cons(Z2[U2],map(Z2,V2))
 (7)  filter(I2,nil) => nil
 (8)  filter(J2,cons(X3,Y3)) => filter2(J2[X3],J2,X3,Y3)
 (9)  filter2(true,G3,V3,W3) => cons(V3,filter(G3,W3))
 (10)  filter2(false,J3,X4,Y4) => filter(J3,Y4)

YES