YES Problem: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Proof: DP Processor: DPs: g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) f#(g(x,y)) -> f#(x) f#(g(x,y)) -> f#(f(x)) f#(g(x,y)) -> g#(f(f(x)),a()) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) TDG Processor: DPs: g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) f#(g(x,y)) -> f#(x) f#(g(x,y)) -> f#(f(x)) f#(g(x,y)) -> g#(f(f(x)),a()) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) graph: f#(g(x,y)) -> f#(f(x)) -> f#(g(x,y)) -> g#(y,g(f(f(x)),a())) f#(g(x,y)) -> f#(f(x)) -> f#(g(x,y)) -> g#(f(f(x)),a()) f#(g(x,y)) -> f#(f(x)) -> f#(g(x,y)) -> f#(f(x)) f#(g(x,y)) -> f#(f(x)) -> f#(g(x,y)) -> f#(x) f#(g(x,y)) -> f#(x) -> f#(g(x,y)) -> g#(y,g(f(f(x)),a())) f#(g(x,y)) -> f#(x) -> f#(g(x,y)) -> g#(f(f(x)),a()) f#(g(x,y)) -> f#(x) -> f#(g(x,y)) -> f#(f(x)) f#(g(x,y)) -> f#(x) -> f#(g(x,y)) -> f#(x) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(e(),g(e(),x)) -> g#(c(),x) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(d(),g(d(),x)) -> g#(e(),x) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(c(),g(c(),x)) -> g#(d(),x) f#(g(x,y)) -> g#(f(f(x)),a()) -> g#(x,x) -> g#(a(),b()) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(e(),g(e(),x)) -> g#(c(),x) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(d(),g(d(),x)) -> g#(e(),x) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(c(),g(c(),x)) -> g#(d(),x) f#(g(x,y)) -> g#(y,g(f(f(x)),a())) -> g#(x,x) -> g#(a(),b()) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(x,x) -> g#(a(),b()) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(x,x) -> g#(a(),b()) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(x,x) -> g#(a(),b()) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(x,x) -> g#(a(),b()) g#(x,x) -> g#(a(),b()) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(x,x) -> g#(a(),b()) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(x,x) -> g#(a(),b()) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(x,x) -> g#(a(),b()) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(x,x) -> g#(a(),b()) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(x,x) -> g#(a(),b()) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(x,x) -> g#(a(),b()) -> g#(x,x) -> g#(a(),b()) SCC Processor: #sccs: 2 #rules: 9 #arcs: 71/121 DPs: f#(g(x,y)) -> f#(f(x)) f#(g(x,y)) -> f#(x) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Bounds Processor: bound: 1 enrichment: match-dp automaton: final states: {1} transitions: a0() -> 6* f{#,1}(16) -> 1* f{#,1}(18) -> 1* f{#,1}(17) -> 1* g0(8,8) -> 7* g0(14,15) -> 7* g0(17,6) -> 13* g0(18,14) -> 3* g0(2,14) -> 3* g0(14,14) -> 7* g0(11,14) -> 7* g0(18,15) -> 3* g0(14,8) -> 7* g0(7,6) -> 8* g0(11,13) -> 7* g0(8,15) -> 7* g0(18,8) -> 3* g0(11,15) -> 7* g0(8,14) -> 7* g0(15,15) -> 7* g0(15,14) -> 7* g0(15,8) -> 7* g0(6,11) -> 14*,13,7,8,3 g0(2,8) -> 3* g0(14,6) -> 15*,8,13 g0(2,15) -> 3* g0(3,6) -> 13* f0(3) -> 7* f0(14) -> 7* f0(17) -> 7* f{#,0}(3) -> 1* f{#,0}(17) -> 1* f{#,0}(14) -> 1* f{#,0}(18) -> 1* f{#,0}(6) -> 1* f{#,0}(2) -> 1* f90() -> 2* f1(2) -> 17*,3,16 f1(18) -> 17* f1(6) -> 18*,2,16 b0() -> 11* problem: DPs: f#(g(x,y)) -> f#(x) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: f{#,0}(2) -> 1* f210() -> 2* problem: DPs: TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Qed DPs: g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) EDG Processor: DPs: g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(d(),g(d(),x)) -> g#(e(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) graph: g#(d(),g(d(),x)) -> g#(e(),x) -> g#(x,x) -> g#(a(),b()) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(d(),g(d(),x)) -> g#(e(),x) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(x,x) -> g#(a(),b()) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(x,x) -> g#(a(),b()) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(x,x) -> g#(a(),b()) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(c(),g(c(),x)) -> g#(d(),x) g#(e(),g(e(),x)) -> g#(c(),x) -> g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(d(),g(d(),x)) -> g#(e(),x) g#(c(),g(c(),x)) -> g#(d(),x) -> g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(x,x) -> g#(a(),b()) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(e(),g(e(),x)) -> g#(c(),x) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) -> g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) SCC Processor: #sccs: 1 #rules: 6 #arcs: 18/49 DPs: g#(d(),g(d(),x)) -> g#(e(),x) g#(e(),g(e(),x)) -> g#(d(),g(c(),x)) g#(d(),g(d(),x)) -> g#(c(),g(e(),x)) g#(c(),g(c(),x)) -> g#(e(),g(d(),x)) g#(e(),g(e(),x)) -> g#(c(),x) g#(c(),g(c(),x)) -> g#(d(),x) TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {25,24,23,22,13,12,10,8,4,1} transitions: e0() -> 3* a0() -> 15* f230() -> 2* g0(5,9) -> 11* g0(3,21) -> 6* g0(7,2) -> 11* g0(7,21) -> 9* g0(5,2) -> 6* g0(7,6) -> 9* g0(15,14) -> 21*,11,9,6 g0(5,21) -> 11* g0(3,2) -> 9* g0(3,11) -> 6* g{#,0}(3,11) -> 22*,12,1,13,10 g{#,0}(7,2) -> 23*,12,1,13 g{#,0}(7,21) -> 25* g{#,0}(5,9) -> 24*,13,12,1,8 g{#,0}(3,2) -> 23*,13,12,1 g{#,0}(5,2) -> 23*,1,13,12 g{#,0}(7,6) -> 25*,1,13,12,4 g{#,0}(3,21) -> 22* g{#,0}(5,21) -> 24* d0() -> 7* c0() -> 5* b0() -> 14* 12 -> 1* 4 -> 1* 13 -> 12* 8 -> 13* 1 -> 13* 10 -> 12* problem: DPs: TRS: g(x,x) -> g(a(),b()) g(c(),g(c(),x)) -> g(e(),g(d(),x)) g(d(),g(d(),x)) -> g(c(),g(e(),x)) g(e(),g(e(),x)) -> g(d(),g(c(),x)) f(g(x,y)) -> g(y,g(f(f(x)),a())) Qed