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) a__f(g(X),Y) -> a__f(mark(X),f(g(X),Y))
(2) mark(f(X1,X2)) -> a__f(mark(X1),X2)
(3) mark(g(X)) -> g(mark(X))
(4) a__f(X1,X2) -> f(X1,X2)

[2]  Apply the Dependency Pair transformation resulting in the following dependency pairs:
<A__f(g(X),Y), A__f(mark(X),f(g(X),Y))>
<A__f(g(X),Y), Mark(X)>
<Mark(f(X1,X2)), A__f(mark(X1),X2)>
<Mark(f(X1,X2)), Mark(X1)>
<Mark(g(X)), Mark(X)>
 and 1 SCCs in the dependency graph. Proofs for those SCCs follow.

[2a-1]  Consider the following SCC obtained from analysis of dependency graph:
(1) a__f(g(X),Y) ->= a__f(mark(X),f(g(X),Y))
(2) mark(f(X1,X2)) ->= a__f(mark(X1),X2)
(3) mark(g(X)) ->= g(mark(X))
(4) a__f(X1,X2) ->= f(X1,X2)
(DP5) Mark(g(X)) -> Mark(X)
(DP4) Mark(f(X1,X2)) -> Mark(X1)
(DP3) Mark(f(X1,X2)) -> A__f(mark(X1),X2)
(DP2) A__f(g(X),Y) -> Mark(X)
(DP1) A__f(g(X),Y) -> A__f(mark(X),f(g(X),Y))

[2a-2]  Use following polynomial interpretation:
[a__f(x,y)] = x + 1
[g(x)] = x + 1
[f(x,y)] = x + 1
[A__f(x,y)] = x
rest default

  Remove rules with left hand side strictly bigger than right hand side:
(1), (DP5), (DP4), (DP3), (DP2), (DP1)

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



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