/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 Z) (RULES a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ) Problem 1: Dependency Pairs Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> A__ADD(mark(X1),X2) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(from(X)) -> A__FROM(X) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true Problem 1: SCC Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> A__ADD(mark(X1),X2) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(from(X)) -> A__FROM(X) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__ADD(0,X) -> MARK(X) A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> A__ADD(mark(X1),X2) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) ->->-> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true Problem 1: Reduction Pair Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> A__ADD(mark(X1),X2) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true -> Usable rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = 2.X1 + 2.X2 + 2 [a__and](X1,X2) = 2.X1 + 2.X2 + 2 [a__first](X1,X2) = X1 + X2 + 2 [a__from](X) = 2.X + 2 [a__if](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [mark](X) = 2.X + 2 [0] = 0 [add](X1,X2) = 2.X1 + X2 + 2 [and](X1,X2) = 2.X1 + 2.X2 + 2 [cons](X1,X2) = 2.X1 + 2 [false] = 2 [first](X1,X2) = X1 + X2 + 2 [from](X) = 2.X + 2 [if](X1,X2,X3) = 2.X1 + X2 + 2.X3 + 2 [nil] = 2 [s](X) = 2.X + 2 [true] = 1 [A__ADD](X1,X2) = 2.X2 + 2 [A__AND](X1,X2) = X1 + 2.X2 + 1 [A__IF](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1 [MARK](X) = 2.X + 1 Problem 1: SCC Processor: -> Pairs: A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> A__ADD(mark(X1),X2) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) ->->-> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true Problem 1: Reduction Pair Processor: -> Pairs: A__AND(true,X) -> MARK(X) A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true -> Usable rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = 2.X1 + 2.X2 + 2 [a__and](X1,X2) = 2.X1 + 2.X2 + 2 [a__first](X1,X2) = X1 + X2 + 2 [a__from](X) = 2 [a__if](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [mark](X) = 2.X + 2 [0] = 0 [add](X1,X2) = 2.X1 + X2 + 2 [and](X1,X2) = 2.X1 + 2.X2 + 2 [cons](X1,X2) = 2 [false] = 2 [first](X1,X2) = X1 + X2 + 2 [from](X) = 2 [if](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2 [nil] = 1 [s](X) = 2 [true] = 2 [A__AND](X1,X2) = 2.X1 + 2.X2 + 2 [A__IF](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 [MARK](X) = 2.X + 2 Problem 1: SCC Processor: -> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> A__AND(mark(X1),X2) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) ->->-> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true Problem 1: Reduction Pair Processor: -> Pairs: A__IF(false,X,Y) -> MARK(Y) A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true -> Usable rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = 2.X1 + 2.X2 [a__and](X1,X2) = 2.X1 + 2.X2 [a__first](X1,X2) = 2.X1 + 2.X2 + 2 [a__from](X) = 2.X [a__if](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [mark](X) = 2.X [0] = 0 [add](X1,X2) = 2.X1 + X2 [and](X1,X2) = 2.X1 + 2.X2 [cons](X1,X2) = X2 [false] = 0 [first](X1,X2) = 2.X1 + 2.X2 + 2 [from](X) = X [if](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [nil] = 1 [s](X) = 2.X [true] = 2 [A__IF](X1,X2,X3) = 2.X2 + 2.X3 + 2 [MARK](X) = 2.X Problem 1: SCC Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) ->->-> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true Problem 1: Subterm Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) MARK(add(X1,X2)) -> MARK(X1) MARK(and(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(if(X1,X2,X3)) -> A__IF(mark(X1),X2,X3) MARK(if(X1,X2,X3)) -> MARK(X1) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Projection: pi(A__IF) = 2 pi(MARK) = 1 Problem 1: SCC Processor: -> Pairs: A__IF(true,X,Y) -> MARK(X) -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__and(false,Y) -> false a__and(true,X) -> mark(X) a__and(X1,X2) -> and(X1,X2) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(Y,first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__from(X) -> cons(X,from(s(X))) a__from(X) -> from(X) a__if(false,X,Y) -> mark(Y) a__if(true,X,Y) -> mark(X) a__if(X1,X2,X3) -> if(X1,X2,X3) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),X2) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(cons(X1,X2)) -> cons(X1,X2) mark(false) -> false mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(X) mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3) mark(nil) -> nil mark(s(X)) -> s(X) mark(true) -> true ->Strongly Connected Components: There is no strongly connected component The problem is finite.