/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR l l1 l2 l3 x y z) (RULES *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ) Problem 1: Dependency Pairs Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(0(x),y) -> 0#(*(x,y)) *#(1(x),y) -> *#(x,y) *#(1(x),y) -> +#(0(*(x,y)),y) *#(1(x),y) -> 0#(*(x,y)) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) *#(x,+(y,z)) -> +#(*(x,y),*(x,z)) +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> 0#(+(+(x,y),1(#))) -#(0(x),0(y)) -> -#(x,y) -#(0(x),0(y)) -> 0#(-(x,y)) -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -#(1(x),1(y)) -> 0#(-(x,y)) APP(cons(x,l1),l2) -> APP(l1,l2) EQ(0(x),0(y)) -> EQ(x,y) EQ(0(x),#) -> EQ(x,#) EQ(#,0(y)) -> EQ(#,y) EQ(1(x),1(y)) -> EQ(x,y) GE(0(x),0(y)) -> GE(x,y) GE(0(x),1(y)) -> GE(y,x) GE(0(x),1(y)) -> NOT(ge(y,x)) GE(#,0(x)) -> GE(#,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) IFINTER(false,x,l1,l2) -> INTER(l1,l2) IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> APP(inter(l1,l3),inter(l2,l3)) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(cons(x,l1),l2) -> MEM(x,l2) INTER(l1,app(l2,l3)) -> APP(inter(l1,l2),inter(l1,l3)) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) INTER(l1,cons(x,l2)) -> MEM(x,l1) LOG(x) -> -#(log'(x),1(#)) LOG(x) -> LOG'(x) LOG'(0(x)) -> +#(log'(x),1(#)) LOG'(0(x)) -> GE(x,1(#)) LOG'(0(x)) -> IF(ge(x,1(#)),+(log'(x),1(#)),#) LOG'(0(x)) -> LOG'(x) LOG'(1(x)) -> +#(log'(x),1(#)) LOG'(1(x)) -> LOG'(x) MEM(x,cons(y,l)) -> EQ(x,y) MEM(x,cons(y,l)) -> IF(eq(x,y),true,mem(x,l)) MEM(x,cons(y,l)) -> MEM(x,l) PROD(app(l1,l2)) -> *#(prod(l1),prod(l2)) PROD(app(l1,l2)) -> PROD(l1) PROD(app(l1,l2)) -> PROD(l2) PROD(cons(x,l)) -> *#(x,prod(l)) PROD(cons(x,l)) -> PROD(l) SUM(app(l1,l2)) -> +#(sum(l1),sum(l2)) SUM(app(l1,l2)) -> SUM(l1) SUM(app(l1,l2)) -> SUM(l2) SUM(cons(x,l)) -> +#(x,sum(l)) SUM(cons(x,l)) -> SUM(l) SUM(nil) -> 0#(#) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1: SCC Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(0(x),y) -> 0#(*(x,y)) *#(1(x),y) -> *#(x,y) *#(1(x),y) -> +#(0(*(x,y)),y) *#(1(x),y) -> 0#(*(x,y)) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) *#(x,+(y,z)) -> +#(*(x,y),*(x,z)) +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> 0#(+(+(x,y),1(#))) -#(0(x),0(y)) -> -#(x,y) -#(0(x),0(y)) -> 0#(-(x,y)) -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -#(1(x),1(y)) -> 0#(-(x,y)) APP(cons(x,l1),l2) -> APP(l1,l2) EQ(0(x),0(y)) -> EQ(x,y) EQ(0(x),#) -> EQ(x,#) EQ(#,0(y)) -> EQ(#,y) EQ(1(x),1(y)) -> EQ(x,y) GE(0(x),0(y)) -> GE(x,y) GE(0(x),1(y)) -> GE(y,x) GE(0(x),1(y)) -> NOT(ge(y,x)) GE(#,0(x)) -> GE(#,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) IFINTER(false,x,l1,l2) -> INTER(l1,l2) IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> APP(inter(l1,l3),inter(l2,l3)) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(cons(x,l1),l2) -> MEM(x,l2) INTER(l1,app(l2,l3)) -> APP(inter(l1,l2),inter(l1,l3)) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) INTER(l1,cons(x,l2)) -> MEM(x,l1) LOG(x) -> -#(log'(x),1(#)) LOG(x) -> LOG'(x) LOG'(0(x)) -> +#(log'(x),1(#)) LOG'(0(x)) -> GE(x,1(#)) LOG'(0(x)) -> IF(ge(x,1(#)),+(log'(x),1(#)),#) LOG'(0(x)) -> LOG'(x) LOG'(1(x)) -> +#(log'(x),1(#)) LOG'(1(x)) -> LOG'(x) MEM(x,cons(y,l)) -> EQ(x,y) MEM(x,cons(y,l)) -> IF(eq(x,y),true,mem(x,l)) MEM(x,cons(y,l)) -> MEM(x,l) PROD(app(l1,l2)) -> *#(prod(l1),prod(l2)) PROD(app(l1,l2)) -> PROD(l1) PROD(app(l1,l2)) -> PROD(l2) PROD(cons(x,l)) -> *#(x,prod(l)) PROD(cons(x,l)) -> PROD(l) SUM(app(l1,l2)) -> +#(sum(l1),sum(l2)) SUM(app(l1,l2)) -> SUM(l1) SUM(app(l1,l2)) -> SUM(l2) SUM(cons(x,l)) -> +#(x,sum(l)) SUM(cons(x,l)) -> SUM(l) SUM(nil) -> 0#(#) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GE(#,0(x)) -> GE(#,x) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: GE(0(x),0(y)) -> GE(x,y) GE(0(x),1(y)) -> GE(y,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: EQ(#,0(y)) -> EQ(#,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: EQ(0(x),#) -> EQ(x,#) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: EQ(0(x),0(y)) -> EQ(x,y) EQ(1(x),1(y)) -> EQ(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: MEM(x,cons(y,l)) -> MEM(x,l) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: APP(cons(x,l1),l2) -> APP(l1,l2) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: IFINTER(false,x,l1,l2) -> INTER(l1,l2) IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: -#(0(x),0(y)) -> -#(x,y) -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: LOG'(0(x)) -> LOG'(x) LOG'(1(x)) -> LOG'(x) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: SUM(app(l1,l2)) -> SUM(l1) SUM(app(l1,l2)) -> SUM(l2) SUM(cons(x,l)) -> SUM(l) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: PROD(app(l1,l2)) -> PROD(l1) PROD(app(l1,l2)) -> PROD(l2) PROD(cons(x,l)) -> PROD(l) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) The problem is decomposed in 14 subproblems. Problem 1.1: Subterm Processor: -> Pairs: GE(#,0(x)) -> GE(#,x) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(GE) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: GE(0(x),0(y)) -> GE(x,y) GE(0(x),1(y)) -> GE(y,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: Empty ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0](X) = 2.X + 1 [1](X) = 2.X [GE](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: GE(0(x),1(y)) -> GE(y,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GE(0(x),1(y)) -> GE(y,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.2: Reduction Pair Processor: -> Pairs: GE(0(x),1(y)) -> GE(y,x) GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> 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.2: SCC Processor: -> Pairs: GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.2: Subterm Processor: -> Pairs: GE(1(x),0(y)) -> GE(x,y) GE(1(x),1(y)) -> GE(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(GE) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: EQ(#,0(y)) -> EQ(#,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(EQ) = 2 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Subterm Processor: -> Pairs: EQ(0(x),#) -> EQ(x,#) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(EQ) = 1 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.5: Subterm Processor: -> Pairs: EQ(0(x),0(y)) -> EQ(x,y) EQ(1(x),1(y)) -> EQ(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(EQ) = 1 Problem 1.5: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.6: Subterm Processor: -> Pairs: MEM(x,cons(y,l)) -> MEM(x,l) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(MEM) = 2 Problem 1.6: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.7: Subterm Processor: -> Pairs: APP(cons(x,l1),l2) -> APP(l1,l2) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(APP) = 1 Problem 1.7: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.8: Reduction Pair Processor: -> Pairs: IFINTER(false,x,l1,l2) -> INTER(l1,l2) IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0](X) = 2.X [app](X1,X2) = X1 + 2.X2 [eq](X1,X2) = 2.X1 + 2.X2 + 2 [if](X1,X2,X3) = 2.X2 + X3 + 2 [mem](X1,X2) = 2.X1 + 2.X2 + 2 [#] = 0 [1](X) = 2.X [cons](X1,X2) = 2.X2 + 1 [false] = 0 [nil] = 2 [true] = 0 [IFINTER](X1,X2,X3,X4) = 2.X3 + 2.X4 + 2 [INTER](X1,X2) = 2.X1 + 2.X2 + 1 Problem 1.8: SCC Processor: -> Pairs: IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.8: Reduction Pair Processor: -> Pairs: IFINTER(true,x,l1,l2) -> INTER(l1,l2) INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0](X) = 2.X + 2 [app](X1,X2) = 2.X1 + 2.X2 [eq](X1,X2) = X1 + 2.X2 + 2 [if](X1,X2,X3) = 2.X2 + 2.X3 + 2 [mem](X1,X2) = 2.X2 + 2 [#] = 2 [1](X) = 2.X + 1 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [false] = 0 [nil] = 2 [true] = 0 [IFINTER](X1,X2,X3,X4) = 2.X3 + 2.X4 + 2 [INTER](X1,X2) = 2.X1 + 2.X2 + 1 Problem 1.8: SCC Processor: -> Pairs: INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(cons(x,l1),l2) -> IFINTER(mem(x,l2),x,l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) INTER(l1,cons(x,l2)) -> IFINTER(mem(x,l1),x,l2,l1) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.8: Subterm Processor: -> Pairs: INTER(app(l1,l2),l3) -> INTER(l1,l3) INTER(app(l1,l2),l3) -> INTER(l2,l3) INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(INTER) = 1 Problem 1.8: SCC Processor: -> Pairs: INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.8: Subterm Processor: -> Pairs: INTER(l1,app(l2,l3)) -> INTER(l1,l2) INTER(l1,app(l2,l3)) -> INTER(l1,l3) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(INTER) = 2 Problem 1.8: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.9: Reduction Pair Processor: -> Pairs: -#(0(x),0(y)) -> -#(x,y) -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 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.9: SCC Processor: -> Pairs: -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.9: Reduction Pair Processor: -> Pairs: -#(0(x),1(y)) -> -#(-(x,y),1(#)) -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 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.9: SCC Processor: -> Pairs: -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.9: Subterm Processor: -> Pairs: -#(0(x),1(y)) -> -#(x,y) -#(1(x),0(y)) -> -#(x,y) -#(1(x),1(y)) -> -#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(-#) = 1 Problem 1.9: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.10: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 2 [0](X) = X [#] = 0 [1](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.10: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.10: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x 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) = 2.X1 + 2.X2 Problem 1.10: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.10: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x 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) = 2.X1 + 2.X2 Problem 1.10: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.10: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x 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) = 2.X1 + 2.X2 Problem 1.10: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.10: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x 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) = 2.X1 + 2.X2 Problem 1.10: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.10: Subterm Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(1(x),1(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(+#) = 1 Problem 1.10: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.11: Subterm Processor: -> Pairs: LOG'(0(x)) -> LOG'(x) LOG'(1(x)) -> LOG'(x) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(LOG') = 1 Problem 1.11: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.12: Subterm Processor: -> Pairs: SUM(app(l1,l2)) -> SUM(l1) SUM(app(l1,l2)) -> SUM(l2) SUM(cons(x,l)) -> SUM(l) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(SUM) = 1 Problem 1.12: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.13: Subterm Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(*#) = 1 Problem 1.13: SCC Processor: -> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) Problem 1.13: Subterm Processor: -> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(*#) = 2 Problem 1.13: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.14: Subterm Processor: -> Pairs: PROD(app(l1,l2)) -> PROD(l1) PROD(app(l1,l2)) -> PROD(l2) PROD(cons(x,l)) -> PROD(l) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Projection: pi(PROD) = 1 Problem 1.14: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> 0(+(+(x,y),1(#))) +(x,#) -> x -(0(x),0(y)) -> 0(-(x,y)) -(0(x),1(y)) -> 1(-(-(x,y),1(#))) -(#,x) -> # -(1(x),0(y)) -> 1(-(x,y)) -(1(x),1(y)) -> 0(-(x,y)) -(x,#) -> x 0(#) -> # app(cons(x,l1),l2) -> cons(x,app(l1,l2)) app(nil,l) -> l eq(0(x),0(y)) -> eq(x,y) eq(0(x),#) -> eq(x,#) eq(0(x),1(y)) -> false eq(#,0(y)) -> eq(#,y) eq(#,#) -> true eq(#,1(y)) -> false eq(1(x),0(y)) -> false eq(1(x),#) -> false eq(1(x),1(y)) -> eq(x,y) ge(0(x),0(y)) -> ge(x,y) ge(0(x),1(y)) -> not(ge(y,x)) ge(#,0(x)) -> ge(#,x) ge(#,1(x)) -> false ge(1(x),0(y)) -> ge(x,y) ge(1(x),1(y)) -> ge(x,y) ge(x,#) -> true if(false,x,y) -> y if(true,x,y) -> x ifinter(false,x,l1,l2) -> inter(l1,l2) ifinter(true,x,l1,l2) -> cons(x,inter(l1,l2)) inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) inter(nil,x) -> nil inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) inter(x,nil) -> nil log(x) -> -(log'(x),1(#)) log'(0(x)) -> if(ge(x,1(#)),+(log'(x),1(#)),#) log'(#) -> # log'(1(x)) -> +(log'(x),1(#)) mem(x,cons(y,l)) -> if(eq(x,y),true,mem(x,l)) mem(x,nil) -> false not(false) -> true not(true) -> false prod(app(l1,l2)) -> *(prod(l1),prod(l2)) prod(cons(x,l)) -> *(x,prod(l)) prod(nil) -> 1(#) sum(app(l1,l2)) -> +(sum(l1),sum(l2)) sum(cons(x,l)) -> +(x,sum(l)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite.