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


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


NO

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

******** FO SN check ********
Check non-SN using NTI (Non-Termination Inference by Payet)

******** Computation rules ********
 (1)  f(X,c(X),c(Y)) => f(Y,Y,f(Y,X,Y))
 (2)  f(s(U),V,W) => f(U,s(c(V)),c(W))
 (3)  f(c(P),P,X1) => c(X1)
 (4)  g(Y1,U1) => Y1
 (5)  g(V1,W1) => W1

backward process killed -- 548 rule(s) generated
forward+backward process killed -- 425 rule(s) generated

NO

let R be the TRS under consideration

f(_1,c(_1),c(_2)) -> f(_2,_2,f(_2,_1,_2)) is in elim_R(R)
let r0 be the right-hand side of this rule
p0 = 0 is a position in r0
we have r0|p0 = _2
g(_3,_4) -> _3 is in R
let l'0 be the left-hand side of this rule
theta0 = {_2/g(_3,_4)} is a mgu of r0|p0 and l'0

==> f(_1,c(_1),c(g(_2,_3))) -> f(_2,g(_2,_3),f(g(_2,_3),_1,g(_2,_3))) is in EU_R^1
let r1 be the right-hand side of this rule
p1 = 1 is a position in r1
we have r1|p1 = g(_2,_3)
g(_4,_5) -> _5 is in R
let l'1 be the left-hand side of this rule
theta1 = {_2/_4, _3/_5} is a mgu of r1|p1 and l'1

==> f(_1,c(_1),c(g(_2,_3))) -> f(_2,_3,f(g(_2,_3),_1,g(_2,_3))) is in EU_R^2
let r2 be the right-hand side of this rule
p2 = 2.0 is a position in r2
we have r2|p2 = g(_2,_3)
g(_4,_5) -> _5 is in R
let l'2 be the left-hand side of this rule
theta2 = {_2/_4, _3/_5} is a mgu of r2|p2 and l'2

==> f(_1,c(_1),c(g(_2,_3))) -> f(_2,_3,f(_3,_1,g(_2,_3))) is in EU_R^3
let r3 be the right-hand side of this rule
p3 = 2 is a position in r3
we have r3|p3 = f(_3,_1,g(_2,_3))
f(c(_4),_4,_5) -> c(_5) is in R
let l'3 be the left-hand side of this rule
theta3 = {_1/_4, _3/c(_4), _5/g(_2,c(_4))} is a mgu of r3|p3 and l'3

==> f(_1,c(_1),c(g(_2,c(_1)))) -> f(_2,c(_1),c(g(_2,c(_1)))) is in EU_R^4
let l be the left-hand side and r be the right-hand side of this rule
let p = epsilon
let theta = {_1/_2}
let theta' = {}
we have r|p = f(_2,c(_1),c(g(_2,c(_1)))) and
theta'(theta(l)) = theta(r|p)
so, theta(l) = f(_2,c(_2),c(g(_2,c(_2)))) is non-terminating w.r.t. R

Termination disproved by the forward process
proof stopped at iteration i=4, depth k=3
241 rule(s) generated
>>NO


******** Signature ********
 c : a -> a
 cons : (d,e) -> e
 f : (a,a,a) -> a
 false : c
 filter : ((d -> c),e) -> e
 filter2 : (c,(d -> c),d,e) -> e
 g : (b,b) -> b
 map : ((d -> d),e) -> e
 nil : e
 s : a -> a
 true : c
******** Computation Rules ********
 (1)  f(X,c(X),c(Y)) => f(Y,Y,f(Y,X,Y))
 (2)  f(s(U),V,W) => f(U,s(c(V)),c(W))
 (3)  f(c(P),P,X1) => c(X1)
 (4)  g(Y1,U1) => Y1
 (5)  g(V1,W1) => W1
 (6)  map(J1,nil) => nil
 (7)  map(F2,cons(Y2,U2)) => cons(F2[Y2],map(F2,U2))
 (8)  filter(H2,nil) => nil
 (9)  filter(I2,cons(P2,X3)) => filter2(I2[P2],I2,P2,X3)
 (10)  filter2(true,Z3,U3,V3) => cons(U3,filter(Z3,V3))
 (11)  filter2(false,I3,P3,X4) => filter(I3,X4)

NO