/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR X X1 X2 X3 Y) (RULES a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ) (STRATEGY INNERMOST) Problem 1: Dependency Pairs Processor: -> Pairs: A__DIV(s(X),s(Y)) -> A__GEQ(X,Y) A__DIV(s(X),s(Y)) -> A__IF(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) A__GEQ(s(X),s(Y)) -> A__GEQ(X,Y) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) A__MINUS(s(X),s(Y)) -> A__MINUS(X,Y) MARK(div(X1,X2)) -> A__DIV(mark(X1),X2) MARK(div(X1,X2)) -> MARK(X1) MARK(geq(X1,X2)) -> A__GEQ(X1,X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(minus(X1,X2)) -> A__MINUS(X1,X2) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true Problem 1: SCC Processor: -> Pairs: A__DIV(s(X),s(Y)) -> A__GEQ(X,Y) A__DIV(s(X),s(Y)) -> A__IF(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) A__GEQ(s(X),s(Y)) -> A__GEQ(X,Y) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) A__MINUS(s(X),s(Y)) -> A__MINUS(X,Y) MARK(div(X1,X2)) -> A__DIV(mark(X1),X2) MARK(div(X1,X2)) -> MARK(X1) MARK(geq(X1,X2)) -> A__GEQ(X1,X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(minus(X1,X2)) -> A__MINUS(X1,X2) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__MINUS(s(X),s(Y)) -> A__MINUS(X,Y) ->->-> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->->Cycle: ->->-> Pairs: A__GEQ(s(X),s(Y)) -> A__GEQ(X,Y) ->->-> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->->Cycle: ->->-> Pairs: A__DIV(s(X),s(Y)) -> A__IF(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> A__DIV(mark(X1),X2) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) ->->-> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: A__MINUS(s(X),s(Y)) -> A__MINUS(X,Y) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Projection: pi(A__MINUS) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: A__GEQ(s(X),s(Y)) -> A__GEQ(X,Y) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Projection: pi(A__GEQ) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> Pairs: A__DIV(s(X),s(Y)) -> A__IF(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> A__DIV(mark(X1),X2) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true -> Usable rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__div](X1,X2) = 2.X1 + 2 [a__geq](X1,X2) = 1 [a__if](X1,X2,X3) = X1 + X2 + 2.X3 + 1 [a__minus](X1,X2) = X1 [mark](X) = X [0] = 0 [div](X1,X2) = 2.X1 + 2 [false] = 1 [geq](X1,X2) = 1 [if](X1,X2,X3) = X1 + X2 + 2.X3 + 1 [minus](X1,X2) = X1 [s](X) = X + 2 [true] = 1 [A__DIV](X1,X2) = 2.X1 + 2 [A__IF](X1,X2,X3) = X1 + X2 + 2.X3 [MARK](X) = X + 1 Problem 1.3: SCC Processor: -> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> A__DIV(mark(X1),X2) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) ->->-> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true Problem 1.3: Reduction Pairs Processor: -> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true -> Usable rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__div](X1,X2) = 2.X1 + 2.X2 + 2 [a__geq](X1,X2) = X1 + 1 [a__if](X1,X2,X3) = X1 + X2 + 2.X3 + 1 [a__minus](X1,X2) = 0 [mark](X) = X [0] = 0 [div](X1,X2) = 2.X1 + 2.X2 + 2 [false] = 1 [geq](X1,X2) = X1 + 1 [if](X1,X2,X3) = X1 + X2 + 2.X3 + 1 [minus](X1,X2) = 0 [s](X) = X + 2 [true] = 0 [A__IF](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1 [MARK](X) = 2.X + 1 Problem 1.3: SCC Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) ->->-> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true Problem 1.3: Subterm Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(div(X1,X2)) -> MARK(X1) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Projection: pi(A__IF) = 2 pi(MARK) = 1 Problem 1.3: SCC Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) -> Rules: a__div(0,s(Y)) -> 0 a__div(s(X),s(Y)) -> a__if(a__geq(X,Y),s(div(minus(X,Y),s(Y))),0) a__div(X1,X2) -> div(X1,X2) a__geq(0,s(Y)) -> false a__geq(s(X),s(Y)) -> a__geq(X,Y) a__geq(X,0) -> true a__geq(X1,X2) -> geq(X1,X2) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) a__minus(0,Y) -> 0 a__minus(s(X),s(Y)) -> a__minus(X,Y) a__minus(X1,X2) -> minus(X1,X2) mark(0) -> 0 mark(div(X1,X2)) -> a__div(mark(X1),X2) mark(false) -> false mark(geq(X1,X2)) -> a__geq(X1,X2) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(minus(X1,X2)) -> a__minus(X1,X2) mark(s(X)) -> s(mark(X)) mark(true) -> true ->Strongly Connected Components: There is no strongly connected component The problem is finite.