YES Problem: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Proof: DP Processor: DPs: +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) f#(+(x,y),z) -> f#(y,z) f#(+(x,y),z) -> f#(x,z) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) TDG Processor: DPs: +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) f#(+(x,y),z) -> f#(y,z) f#(+(x,y),z) -> f#(x,z) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) graph: f#(+(x,y),z) -> f#(y,z) -> f#(+(x,y),z) -> +#(f(x,z),f(y,z)) f#(+(x,y),z) -> f#(y,z) -> f#(+(x,y),z) -> f#(x,z) f#(+(x,y),z) -> f#(y,z) -> f#(+(x,y),z) -> f#(y,z) f#(+(x,y),z) -> f#(x,z) -> f#(+(x,y),z) -> +#(f(x,z),f(y,z)) f#(+(x,y),z) -> f#(x,z) -> f#(+(x,y),z) -> f#(x,z) f#(+(x,y),z) -> f#(x,z) -> f#(+(x,y),z) -> f#(y,z) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) -> +#(+(x,y),z) -> +#(y,z) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) -> +#(a(),+(b(),z)) -> +#(a(),z) f#(+(x,y),z) -> +#(f(x,z),f(y,z)) -> +#(a(),b()) -> +#(b(),a()) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(+(x,y),z) -> +#(y,z) -> +#(a(),b()) -> +#(b(),a()) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) -> +#(+(x,y),z) -> +#(y,z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) -> +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(+(x,y),z) -> +#(y,z) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),b()) -> +#(b(),a()) +#(a(),b()) -> +#(b(),a()) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(a(),b()) -> +#(b(),a()) -> +#(+(x,y),z) -> +#(y,z) +#(a(),b()) -> +#(b(),a()) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(a(),b()) -> +#(b(),a()) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),b()) -> +#(b(),a()) -> +#(a(),b()) -> +#(b(),a()) SCC Processor: #sccs: 2 #rules: 7 #arcs: 36/64 DPs: f#(+(x,y),z) -> f#(y,z) f#(+(x,y),z) -> f#(x,z) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Subterm Criterion Processor: simple projection: pi(f#) = 0 problem: DPs: TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Qed DPs: +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) EDG Processor: DPs: +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) graph: +#(+(x,y),z) -> +#(y,z) -> +#(a(),b()) -> +#(b(),a()) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),b()) -> +#(b(),a()) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) CDG Processor: DPs: +#(a(),b()) -> +#(b(),a()) +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) graph: +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(y,z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(+(x,y),z) -> +#(y,z) -> +#(a(),b()) -> +#(b(),a()) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(b(),+(a(),z)) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),+(b(),z)) -> +#(a(),z) +#(a(),+(b(),z)) -> +#(a(),z) -> +#(a(),b()) -> +#(b(),a()) SCC Processor: #sccs: 2 #rules: 3 #arcs: 12/25 DPs: +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Subterm Criterion Processor: simple projection: pi(+#) = 0 problem: DPs: TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Qed DPs: +#(a(),+(b(),z)) -> +#(a(),z) TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Subterm Criterion Processor: simple projection: pi(+#) = 1 problem: DPs: TRS: +(a(),b()) -> +(b(),a()) +(a(),+(b(),z)) -> +(b(),+(a(),z)) +(+(x,y),z) -> +(x,+(y,z)) f(a(),y) -> a() f(b(),y) -> b() f(+(x,y),z) -> +(f(x,z),f(y,z)) Qed