/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ) Problem 1: Dependency Pairs Processor: -> Pairs: +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> 0#(+(+(x:S,y:S),1(#))) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -#(0(x:S),0(y:S)) -> -#(x:S,y:S) -#(0(x:S),0(y:S)) -> 0#(-(x:S,y:S)) -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> 0#(-(x:S,y:S)) BS(n(x:S,y:S,z:S)) -> AND(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) BS(n(x:S,y:S,z:S)) -> AND(bs(y:S),bs(z:S)) BS(n(x:S,y:S,z:S)) -> AND(ge(x:S,max(y:S)),ge(min(z:S),x:S)) BS(n(x:S,y:S,z:S)) -> BS(y:S) BS(n(x:S,y:S,z:S)) -> BS(z:S) BS(n(x:S,y:S,z:S)) -> GE(min(z:S),x:S) BS(n(x:S,y:S,z:S)) -> GE(x:S,max(y:S)) BS(n(x:S,y:S,z:S)) -> MAX(y:S) BS(n(x:S,y:S,z:S)) -> MIN(z:S) GE(0(x:S),0(y:S)) -> GE(x:S,y:S) GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(0(x:S),1(y:S)) -> NOT(ge(y:S,x:S)) GE(#,0(x:S)) -> GE(#,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) MAX(n(x:S,y:S,z:S)) -> MAX(z:S) MIN(n(x:S,y:S,z:S)) -> MIN(y:S) SIZE(n(x:S,y:S,z:S)) -> +#(+(size(x:S),size(y:S)),1(#)) SIZE(n(x:S,y:S,z:S)) -> +#(size(x:S),size(y:S)) SIZE(n(x:S,y:S,z:S)) -> SIZE(x:S) SIZE(n(x:S,y:S,z:S)) -> SIZE(y:S) WB(n(x:S,y:S,z:S)) -> -#(size(y:S),size(z:S)) WB(n(x:S,y:S,z:S)) -> -#(size(z:S),size(y:S)) WB(n(x:S,y:S,z:S)) -> AND(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) WB(n(x:S,y:S,z:S)) -> AND(wb(y:S),wb(z:S)) WB(n(x:S,y:S,z:S)) -> GE(size(y:S),size(z:S)) WB(n(x:S,y:S,z:S)) -> GE(1(#),-(size(y:S),size(z:S))) WB(n(x:S,y:S,z:S)) -> GE(1(#),-(size(z:S),size(y:S))) WB(n(x:S,y:S,z:S)) -> IF(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))) WB(n(x:S,y:S,z:S)) -> SIZE(y:S) WB(n(x:S,y:S,z:S)) -> SIZE(z:S) WB(n(x:S,y:S,z:S)) -> WB(y:S) WB(n(x:S,y:S,z:S)) -> WB(z:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1: SCC Processor: -> Pairs: +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> 0#(+(+(x:S,y:S),1(#))) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -#(0(x:S),0(y:S)) -> -#(x:S,y:S) -#(0(x:S),0(y:S)) -> 0#(-(x:S,y:S)) -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> 0#(-(x:S,y:S)) BS(n(x:S,y:S,z:S)) -> AND(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) BS(n(x:S,y:S,z:S)) -> AND(bs(y:S),bs(z:S)) BS(n(x:S,y:S,z:S)) -> AND(ge(x:S,max(y:S)),ge(min(z:S),x:S)) BS(n(x:S,y:S,z:S)) -> BS(y:S) BS(n(x:S,y:S,z:S)) -> BS(z:S) BS(n(x:S,y:S,z:S)) -> GE(min(z:S),x:S) BS(n(x:S,y:S,z:S)) -> GE(x:S,max(y:S)) BS(n(x:S,y:S,z:S)) -> MAX(y:S) BS(n(x:S,y:S,z:S)) -> MIN(z:S) GE(0(x:S),0(y:S)) -> GE(x:S,y:S) GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(0(x:S),1(y:S)) -> NOT(ge(y:S,x:S)) GE(#,0(x:S)) -> GE(#,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) MAX(n(x:S,y:S,z:S)) -> MAX(z:S) MIN(n(x:S,y:S,z:S)) -> MIN(y:S) SIZE(n(x:S,y:S,z:S)) -> +#(+(size(x:S),size(y:S)),1(#)) SIZE(n(x:S,y:S,z:S)) -> +#(size(x:S),size(y:S)) SIZE(n(x:S,y:S,z:S)) -> SIZE(x:S) SIZE(n(x:S,y:S,z:S)) -> SIZE(y:S) WB(n(x:S,y:S,z:S)) -> -#(size(y:S),size(z:S)) WB(n(x:S,y:S,z:S)) -> -#(size(z:S),size(y:S)) WB(n(x:S,y:S,z:S)) -> AND(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) WB(n(x:S,y:S,z:S)) -> AND(wb(y:S),wb(z:S)) WB(n(x:S,y:S,z:S)) -> GE(size(y:S),size(z:S)) WB(n(x:S,y:S,z:S)) -> GE(1(#),-(size(y:S),size(z:S))) WB(n(x:S,y:S,z:S)) -> GE(1(#),-(size(z:S),size(y:S))) WB(n(x:S,y:S,z:S)) -> IF(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))) WB(n(x:S,y:S,z:S)) -> SIZE(y:S) WB(n(x:S,y:S,z:S)) -> SIZE(z:S) WB(n(x:S,y:S,z:S)) -> WB(y:S) WB(n(x:S,y:S,z:S)) -> WB(z:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: MIN(n(x:S,y:S,z:S)) -> MIN(y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: MAX(n(x:S,y:S,z:S)) -> MAX(z:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: GE(#,0(x:S)) -> GE(#,x:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: GE(0(x:S),0(y:S)) -> GE(x:S,y:S) GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: BS(n(x:S,y:S,z:S)) -> BS(y:S) BS(n(x:S,y:S,z:S)) -> BS(z:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: -#(0(x:S),0(y:S)) -> -#(x:S,y:S) -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: SIZE(n(x:S,y:S,z:S)) -> SIZE(x:S) SIZE(n(x:S,y:S,z:S)) -> SIZE(y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->->Cycle: ->->-> Pairs: WB(n(x:S,y:S,z:S)) -> WB(y:S) WB(n(x:S,y:S,z:S)) -> WB(z:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) The problem is decomposed in 9 subproblems. Problem 1.1: Subterm Processor: -> Pairs: MIN(n(x:S,y:S,z:S)) -> MIN(y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(MIN) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: MAX(n(x:S,y:S,z:S)) -> MAX(z:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(MAX) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: GE(#,0(x:S)) -> GE(#,x:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(GE) = 2 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pair Processor: -> Pairs: GE(0(x:S),0(y:S)) -> GE(x:S,y:S) GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: Empty ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0](X) = 2.X + 2 [1](X) = X [GE](X1,X2) = X1 + 2.X2 Problem 1.4: SCC Processor: -> Pairs: GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.4: Reduction Pair Processor: -> Pairs: GE(0(x:S),1(y:S)) -> GE(y:S,x:S) GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: Empty ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0](X) = 2.X + 2 [1](X) = 2.X [GE](X1,X2) = 2.X1 + 2.X2 Problem 1.4: SCC Processor: -> Pairs: GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.4: Subterm Processor: -> Pairs: GE(1(x:S),0(y:S)) -> GE(x:S,y:S) GE(1(x:S),1(y:S)) -> GE(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(GE) = 1 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.5: Subterm Processor: -> Pairs: BS(n(x:S,y:S,z:S)) -> BS(y:S) BS(n(x:S,y:S,z:S)) -> BS(z:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(BS) = 1 Problem 1.5: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.6: Reduction Pair Processor: -> Pairs: -#(0(x:S),0(y:S)) -> -#(x:S,y:S) -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [-](X1,X2) = X1 [0](X) = 2.X + 2 [#] = 1 [1](X) = 2.X + 2 [-#](X1,X2) = 2.X1 + 2.X2 Problem 1.6: SCC Processor: -> Pairs: -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.6: Reduction Pair Processor: -> Pairs: -#(0(x:S),1(y:S)) -> -#(-(x:S,y:S),1(#)) -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [-](X1,X2) = X1 + X2 + 1 [0](X) = X + 2 [#] = 0 [1](X) = X + 1 [-#](X1,X2) = 2.X1 + 2.X2 Problem 1.6: SCC Processor: -> Pairs: -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.6: Subterm Processor: -> Pairs: -#(0(x:S),1(y:S)) -> -#(x:S,y:S) -#(1(x:S),0(y:S)) -> -#(x:S,y:S) -#(1(x:S),1(y:S)) -> -#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(-#) = 1 Problem 1.6: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.7: Reduction Pair Processor: -> Pairs: +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + 2.X2 + 1 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = X1 + 2.X2 Problem 1.7: SCC Processor: -> Pairs: +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.7: Reduction Pair Processor: -> Pairs: +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 1 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.7: SCC Processor: -> Pairs: +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.7: Reduction Pair Processor: -> Pairs: +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + 2.X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = X1 + 2.X2 Problem 1.7: SCC Processor: -> Pairs: +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.7: Reduction Pair Processor: -> Pairs: +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) -> Usable rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + 2.X2 + 1 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = X1 + 2.X2 Problem 1.7: SCC Processor: -> Pairs: +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) ->->-> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) Problem 1.7: Subterm Processor: -> Pairs: +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(x:S,+(y:S,z:S)) -> +#(+(x:S,y:S),z:S) +#(x:S,+(y:S,z:S)) -> +#(x:S,y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(+#) = 2 Problem 1.7: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.8: Subterm Processor: -> Pairs: SIZE(n(x:S,y:S,z:S)) -> SIZE(x:S) SIZE(n(x:S,y:S,z:S)) -> SIZE(y:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(SIZE) = 1 Problem 1.8: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.9: Subterm Processor: -> Pairs: WB(n(x:S,y:S,z:S)) -> WB(y:S) WB(n(x:S,y:S,z:S)) -> WB(z:S) -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Projection: pi(WB) = 1 Problem 1.9: SCC Processor: -> Pairs: Empty -> Rules: +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,+(y:S,z:S)) -> +(+(x:S,y:S),z:S) +(x:S,#) -> x:S -(0(x:S),0(y:S)) -> 0(-(x:S,y:S)) -(0(x:S),1(y:S)) -> 1(-(-(x:S,y:S),1(#))) -(#,x:S) -> # -(1(x:S),0(y:S)) -> 1(-(x:S,y:S)) -(1(x:S),1(y:S)) -> 0(-(x:S,y:S)) -(x:S,#) -> x:S 0(#) -> # and(x:S,ffalse) -> ffalse and(x:S,ttrue) -> x:S bs(l(x:S)) -> ttrue bs(n(x:S,y:S,z:S)) -> and(and(ge(x:S,max(y:S)),ge(min(z:S),x:S)),and(bs(y:S),bs(z:S))) ge(0(x:S),0(y:S)) -> ge(x:S,y:S) ge(0(x:S),1(y:S)) -> not(ge(y:S,x:S)) ge(#,0(x:S)) -> ge(#,x:S) ge(#,1(x:S)) -> ffalse ge(1(x:S),0(y:S)) -> ge(x:S,y:S) ge(1(x:S),1(y:S)) -> ge(x:S,y:S) ge(x:S,#) -> ttrue if(ffalse,x:S,y:S) -> y:S if(ttrue,x:S,y:S) -> x:S max(l(x:S)) -> x:S max(n(x:S,y:S,z:S)) -> max(z:S) min(l(x:S)) -> x:S min(n(x:S,y:S,z:S)) -> min(y:S) not(ffalse) -> ttrue not(ttrue) -> ffalse size(l(x:S)) -> 1(#) size(n(x:S,y:S,z:S)) -> +(+(size(x:S),size(y:S)),1(#)) val(l(x:S)) -> x:S val(n(x:S,y:S,z:S)) -> x:S wb(l(x:S)) -> ttrue wb(n(x:S,y:S,z:S)) -> and(if(ge(size(y:S),size(z:S)),ge(1(#),-(size(y:S),size(z:S))),ge(1(#),-(size(z:S),size(y:S)))),and(wb(y:S),wb(z:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.