YES 3: or(T(),x1) -> T() 4: or(F(),x1) -> x1 5: or(or(x1,x2),x3) -> or(x1,or(x2,x3)) 6: or(x1,x2) -> or(x2,x1) @Jouannaud and Kirchner's criterion --- R 3: or(T(),x1) -> T() 4: or(F(),x1) -> x1 5: or(or(x1,x2),x3) -> or(x1,or(x2,x3)) 6: or(x1,x2) -> or(x2,x1) --- S 3: or(T(),x1) -> T() 4: or(F(),x1) -> x1 5: or(or(x1,x2),x3) -> or(x1,or(x2,x3)) 6: or(x1,x2) -> or(x2,x1) NOTE: input TRS is reduced original is 1: or(x1,T()) -> T() 2: or(x1,F()) -> x1 3: or(T(),x1) -> T() 4: or(F(),x1) -> x1 5: or(or(x1,x2),x3) -> or(x1,or(x2,x3)) 6: or(x1,x2) -> or(x2,x1) reduced to 3: or(T(),x1) -> T() 4: or(F(),x1) -> x1 5: or(or(x1,x2),x3) -> or(x1,or(x2,x3)) 6: or(x1,x2) -> or(x2,x1)