/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v_NonEmpty:S l:S x:S y:S z:S) (RULES *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ) Problem 1: Dependency Pairs Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(0(x:S),y:S) -> 0#(*(x:S,y:S)) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> +#(0(*(x:S,y:S)),y:S) *#(1(x:S),y:S) -> 0#(*(x:S,y:S)) +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> 0#(+(+(x:S,y:S),1(#))) PROD(cons(x:S,l:S)) -> *#(x:S,prod(l:S)) PROD(cons(x:S,l:S)) -> PROD(l:S) SUM(cons(x:S,l:S)) -> +#(x:S,sum(l:S)) SUM(cons(x:S,l:S)) -> SUM(l:S) SUM(nil) -> 0#(#) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1: SCC Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(0(x:S),y:S) -> 0#(*(x:S,y:S)) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> +#(0(*(x:S,y:S)),y:S) *#(1(x:S),y:S) -> 0#(*(x:S,y:S)) +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> 0#(+(+(x:S,y:S),1(#))) PROD(cons(x:S,l:S)) -> *#(x:S,prod(l:S)) PROD(cons(x:S,l:S)) -> PROD(l:S) SUM(cons(x:S,l:S)) -> +#(x:S,sum(l:S)) SUM(cons(x:S,l:S)) -> SUM(l:S) SUM(nil) -> 0#(#) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: SUM(cons(x:S,l:S)) -> SUM(l:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> *#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->->Cycle: ->->-> Pairs: PROD(cons(x:S,l:S)) -> PROD(l:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) The problem is decomposed in 4 subproblems. Problem 1.1: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 1 [0](X) = X [#] = 0 [1](X) = X + 1 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1.1: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 1 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1.1: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 1 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1.1: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X [#] = 2 [1](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1.1: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 + 1 [0](X) = X [#] = 0 [1](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.1: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) Problem 1.1: Subterm Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Projection: pi(+#) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: SUM(cons(x:S,l:S)) -> SUM(l:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Projection: pi(SUM) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> *#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Projection: pi(*#) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Subterm Processor: -> Pairs: PROD(cons(x:S,l:S)) -> PROD(l:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Projection: pi(PROD) = 1 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> 0(+(+(x:S,y:S),1(#))) +(x:S,#) -> x:S 0(#) -> # prod(cons(x:S,l:S)) -> *(x:S,prod(l:S)) prod(nil) -> 1(#) sum(cons(x:S,l:S)) -> +(x:S,sum(l:S)) sum(nil) -> 0(#) ->Strongly Connected Components: There is no strongly connected component The problem is finite.