YES Problem: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) Proof: DP Processor: DPs: active#(f(f(a()))) -> g#(f(a())) active#(f(f(a()))) -> f#(g(f(a()))) active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> active#(f(mark(X))) mark#(a()) -> active#(a()) mark#(g(X)) -> active#(g(X)) f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) TDG Processor: DPs: active#(f(f(a()))) -> g#(f(a())) active#(f(f(a()))) -> f#(g(f(a()))) active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> active#(f(mark(X))) mark#(a()) -> active#(a()) mark#(g(X)) -> active#(g(X)) f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) graph: mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> g#(f(a())) mark#(f(X)) -> mark#(X) -> mark#(g(X)) -> active#(g(X)) mark#(f(X)) -> mark#(X) -> mark#(a()) -> active#(a()) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> active#(f(mark(X))) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) -> f#(active(X)) -> f#(X) mark#(f(X)) -> f#(mark(X)) -> f#(mark(X)) -> f#(X) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> g#(f(a())) mark#(a()) -> active#(a()) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(a()) -> active#(a()) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(a()) -> active#(a()) -> active#(f(f(a()))) -> g#(f(a())) f#(mark(X)) -> f#(X) -> f#(active(X)) -> f#(X) f#(mark(X)) -> f#(X) -> f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) -> f#(active(X)) -> f#(X) f#(active(X)) -> f#(X) -> f#(mark(X)) -> f#(X) g#(mark(X)) -> g#(X) -> g#(active(X)) -> g#(X) g#(mark(X)) -> g#(X) -> g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) -> g#(active(X)) -> g#(X) g#(active(X)) -> g#(X) -> g#(mark(X)) -> g#(X) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(g(X)) -> active#(g(X)) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(a()) -> active#(a()) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> active#(f(mark(X))) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> f#(mark(X)) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> mark#(X) active#(f(f(a()))) -> f#(g(f(a()))) -> f#(active(X)) -> f#(X) active#(f(f(a()))) -> f#(g(f(a()))) -> f#(mark(X)) -> f#(X) active#(f(f(a()))) -> g#(f(a())) -> g#(active(X)) -> g#(X) active#(f(f(a()))) -> g#(f(a())) -> g#(mark(X)) -> g#(X) EDG Processor: DPs: active#(f(f(a()))) -> g#(f(a())) active#(f(f(a()))) -> f#(g(f(a()))) active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> active#(f(mark(X))) mark#(a()) -> active#(a()) mark#(g(X)) -> active#(g(X)) f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) graph: mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> g#(f(a())) mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(g(X)) -> active#(g(X)) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> mark#(X) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> active#(f(mark(X))) mark#(f(X)) -> mark#(X) -> mark#(a()) -> active#(a()) mark#(f(X)) -> mark#(X) -> mark#(g(X)) -> active#(g(X)) mark#(f(X)) -> f#(mark(X)) -> f#(mark(X)) -> f#(X) mark#(f(X)) -> f#(mark(X)) -> f#(active(X)) -> f#(X) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> g#(f(a())) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) f#(mark(X)) -> f#(X) -> f#(mark(X)) -> f#(X) f#(mark(X)) -> f#(X) -> f#(active(X)) -> f#(X) f#(active(X)) -> f#(X) -> f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) -> f#(active(X)) -> f#(X) g#(mark(X)) -> g#(X) -> g#(mark(X)) -> g#(X) g#(mark(X)) -> g#(X) -> g#(active(X)) -> g#(X) g#(active(X)) -> g#(X) -> g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) -> g#(active(X)) -> g#(X) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> mark#(X) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> f#(mark(X)) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> active#(f(mark(X))) CDG Processor: DPs: active#(f(f(a()))) -> g#(f(a())) active#(f(f(a()))) -> f#(g(f(a()))) active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> active#(f(mark(X))) mark#(a()) -> active#(a()) mark#(g(X)) -> active#(g(X)) f#(mark(X)) -> f#(X) f#(active(X)) -> f#(X) g#(mark(X)) -> g#(X) g#(active(X)) -> g#(X) TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) graph: mark#(f(X)) -> mark#(X) -> mark#(g(X)) -> active#(g(X)) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> active#(f(mark(X))) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> f#(mark(X)) mark#(f(X)) -> mark#(X) -> mark#(f(X)) -> mark#(X) mark#(f(X)) -> f#(mark(X)) -> f#(active(X)) -> f#(X) mark#(f(X)) -> f#(mark(X)) -> f#(mark(X)) -> f#(X) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> mark#(f(g(f(a())))) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> f#(g(f(a()))) mark#(f(X)) -> active#(f(mark(X))) -> active#(f(f(a()))) -> g#(f(a())) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> active#(f(mark(X))) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> f#(mark(X)) active#(f(f(a()))) -> mark#(f(g(f(a())))) -> mark#(f(X)) -> mark#(X) SCC Processor: #sccs: 1 #rules: 3 #arcs: 12/144 DPs: mark#(f(X)) -> mark#(X) mark#(f(X)) -> active#(f(mark(X))) active#(f(f(a()))) -> mark#(f(g(f(a())))) TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) KBO Processor: argument filtering: pi(a) = [] pi(f) = [0] pi(active) = 0 pi(g) = [] pi(mark) = 0 pi(active#) = [0] pi(mark#) = [0] weight function: w0 = 1 w(mark#) = w(active#) = w(mark) = w(g) = w(active) = w(f) = w(a) = 1 precedence: mark# ~ g ~ a > active# ~ mark ~ active ~ f problem: DPs: TRS: active(f(f(a()))) -> mark(f(g(f(a())))) mark(f(X)) -> active(f(mark(X))) mark(a()) -> active(a()) mark(g(X)) -> active(g(X)) f(mark(X)) -> f(X) f(active(X)) -> f(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) Qed