YES
  TPA v.1.0

Result: TRS is terminating

Default interpretations for symbols are not printed. For polynomial interpretations
and semantic labelling over N\{0,1} defaults are 2 for constants, identity for unary
symbols and x+y-2 for binary symbols. For semantic labelling over {0,1} (booleans)
defaults are 0 for constants, identity for unary symbols and disjunction for binary symbols.

[1]  TRS loaded from input file:
(1) minus(x,0) -> x
(2) minus(s(x),s(y)) -> minus(x,y)
(3) quot(0,s(y)) -> 0
(4) quot(s(x),s(y)) -> s(quot(minus(x,y),s(y)))
(5) app(nil,y) -> y
(6) app(add(n,x),y) -> add(n,app(x,y))
(7) reverse(nil) -> nil
(8) reverse(add(n,x)) -> app(reverse(x),add(n,nil))
(9) shuffle(nil) -> nil
(10) shuffle(add(n,x)) -> add(n,shuffle(reverse(x)))
(11) concat(leaf,y) -> y
(12) concat(cons(u,v),y) -> cons(u,concat(v,y))
(13) less_leaves(x,leaf) -> false
(14) less_leaves(leaf,cons(w,z)) -> true
(15) less_leaves(cons(u,v),cons(w,z)) -> less_leaves(concat(u,v),concat(w,z))

[2]  Apply the Dependency Pair transformation resulting in the following dependency pairs:
<Minus(s(x),s(y)), Minus(x,y)>
<Quot(s(x),s(y)), Quot(minus(x,y),s(y))>
<Quot(s(x),s(y)), Minus(x,y)>
<App(add(n,x),y), App(x,y)>
<Reverse(add(n,x)), App(reverse(x),add(n,nil))>
<Reverse(add(n,x)), Reverse(x)>
<Shuffle(add(n,x)), Shuffle(reverse(x))>
<Shuffle(add(n,x)), Reverse(x)>
<Concat(cons(u,v),y), Concat(v,y)>
<Less_leaves(cons(u,v),cons(w,z)), Less_leaves(concat(u,v),concat(w,z))>
<Less_leaves(cons(u,v),cons(w,z)), Concat(u,v)>
<Less_leaves(cons(u,v),cons(w,z)), Concat(w,z)>
 and 7 SCCs in the dependency graph. Proofs for those SCCs follow.

[2a-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP7) Shuffle(add(n,x)) -> Shuffle(reverse(x))

[2a-2]  Use following polynomial interpretation:
[quot(x,y)] = y
[add(x,y)] = x + y + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(DP7)

[2a-3]  Since there are no remaining strict rules, relative termination is proved!

[2b-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP6) Reverse(add(n,x)) -> Reverse(x)

[2b-2]  Use following polynomial interpretation:
[quot(x,y)] = y
[add(x,y)] = x + y + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(DP6)

[2b-3]  Since there are no remaining strict rules, relative termination is proved!

[2c-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP4) App(add(n,x),y) -> App(x,y)

[2c-2]  Use following polynomial interpretation:
[quot(x,y)] = y
[add(x,y)] = x + y + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(DP4)

[2c-3]  Since there are no remaining strict rules, relative termination is proved!

[2d-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP2) Quot(s(x),s(y)) -> Quot(minus(x,y),s(y))

[2d-2]  Use following polynomial interpretation:
[minus(x,y)] = x
[s(x)] = x + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(2)-(3), (DP2)

[2d-3]  Since there are no remaining strict rules, relative termination is proved!

[2e-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP10) Less_leaves(cons(u,v),cons(w,z)) -> Less_leaves(concat(u,v),concat(w,z))

[2e-2]  Use following polynomial interpretation:
[quot(x,y)] = y
[cons(x,y)] = x + y + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(14)-(15), (DP10)

[2e-3]  Since there are no remaining strict rules, relative termination is proved!

[2f-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP9) Concat(cons(u,v),y) -> Concat(v,y)

[2f-2]  Use following polynomial interpretation:
[quot(x,y)] = y
[cons(x,y)] = x + y + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(14)-(15), (DP9)

[2f-3]  Since there are no remaining strict rules, relative termination is proved!

[2g-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) minus(x,0) ->= x
(2) minus(s(x),s(y)) ->= minus(x,y)
(3) quot(0,s(y)) ->= 0
(4) quot(s(x),s(y)) ->= s(quot(minus(x,y),s(y)))
(5) app(nil,y) ->= y
(6) app(add(n,x),y) ->= add(n,app(x,y))
(7) reverse(nil) ->= nil
(8) reverse(add(n,x)) ->= app(reverse(x),add(n,nil))
(9) shuffle(nil) ->= nil
(10) shuffle(add(n,x)) ->= add(n,shuffle(reverse(x)))
(11) concat(leaf,y) ->= y
(12) concat(cons(u,v),y) ->= cons(u,concat(v,y))
(13) less_leaves(x,leaf) ->= false
(14) less_leaves(leaf,cons(w,z)) ->= true
(15) less_leaves(cons(u,v),cons(w,z)) ->= less_leaves(concat(u,v),concat(w,z))
(DP1) Minus(s(x),s(y)) -> Minus(x,y)

[2g-2]  Use following polynomial interpretation:
[minus(x,y)] = x
[s(x)] = x + 1
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(2)-(3), (DP1)

[2g-3]  Since there are no remaining strict rules, relative termination is proved!



../tpdb/TRS/AG01/#3.53.trs, 0., Y
Couldn't open file <60>: 60: No such file or directory