/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR N X X1 X2 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ) Problem 1: Dependency Pairs Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> A__SQR(mark(N)) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> A__ADD(mark(X1),mark(X2)) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> A__DBL(mark(X)) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> A__SQR(mark(X)) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) Problem 1: SCC Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> A__SQR(mark(N)) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> A__ADD(mark(X1),mark(X2)) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> A__DBL(mark(X)) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> A__SQR(mark(X)) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__ADD(0,X) -> MARK(X) A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> A__ADD(mark(X1),mark(X2)) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) Problem 1: Reduction Pair Processor: -> Pairs: A__ADD(0,X) -> MARK(X) A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> A__ADD(mark(X1),mark(X2)) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = 2.X1 + X2 + 1 [a__dbl](X) = 2.X + 2 [a__first](X1,X2) = 2.X1 + 2.X2 + 2 [a__sqr](X) = 2.X + 1 [a__terms](X) = 2.X + 2 [mark](X) = X [0] = 2 [add](X1,X2) = 2.X1 + X2 + 1 [cons](X1,X2) = X1 [dbl](X) = 2.X + 2 [first](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 1 [recip](X) = X + 1 [s](X) = 0 [sqr](X) = 2.X + 1 [terms](X) = 2.X + 2 [A__ADD](X1,X2) = 2.X2 + 2 [A__FIRST](X1,X2) = X1 + 2.X2 + 2 [A__TERMS](X) = 2.X + 2 [MARK](X) = 2.X + 1 Problem 1: SCC Processor: -> Pairs: A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> A__ADD(mark(X1),mark(X2)) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) Problem 1: Reduction Pair Processor: -> Pairs: A__FIRST(s(X),cons(Y,Z)) -> MARK(Y) A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = 2.X1 + 2.X2 + 2 [a__dbl](X) = 2.X + 2 [a__first](X1,X2) = 2.X1 + 2.X2 + 2 [a__sqr](X) = X [a__terms](X) = 2.X + 2 [mark](X) = 2.X [0] = 2 [add](X1,X2) = 2.X1 + 2.X2 + 2 [cons](X1,X2) = X1 + 2 [dbl](X) = 2.X + 1 [first](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 2 [recip](X) = X [s](X) = 0 [sqr](X) = X [terms](X) = 2.X + 1 [A__FIRST](X1,X2) = 2.X2 + 1 [A__TERMS](X) = 2.X [MARK](X) = 2.X Problem 1: SCC Processor: -> Pairs: A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> A__FIRST(mark(X1),mark(X2)) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) Problem 1: Reduction Pair Processor: -> Pairs: A__TERMS(N) -> MARK(N) MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__add](X1,X2) = X1 + 2.X2 + 2 [a__dbl](X) = X + 2 [a__first](X1,X2) = X1 + 2.X2 + 2 [a__sqr](X) = X [a__terms](X) = 2.X + 2 [mark](X) = 2.X + 1 [0] = 2 [add](X1,X2) = X1 + 2.X2 + 2 [cons](X1,X2) = X1 [dbl](X) = X + 2 [first](X1,X2) = X1 + 2.X2 + 2 [nil] = 0 [recip](X) = X + 1 [s](X) = 2 [sqr](X) = X [terms](X) = 2.X + 2 [A__TERMS](X) = 2.X + 2 [MARK](X) = 2.X + 1 Problem 1: SCC Processor: -> Pairs: MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) Problem 1: Subterm Processor: -> Pairs: MARK(add(X1,X2)) -> MARK(X1) MARK(add(X1,X2)) -> MARK(X2) MARK(cons(X1,X2)) -> MARK(X1) MARK(dbl(X)) -> MARK(X) MARK(first(X1,X2)) -> MARK(X1) MARK(first(X1,X2)) -> MARK(X2) MARK(recip(X)) -> MARK(X) MARK(sqr(X)) -> MARK(X) MARK(terms(X)) -> 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__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Projection: pi(MARK) = 1 Problem 1: SCC Processor: -> Pairs: Empty -> Rules: a__add(0,X) -> mark(X) a__add(s(X),Y) -> s(add(X,Y)) a__add(X1,X2) -> add(X1,X2) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(dbl(X))) a__dbl(X) -> dbl(X) a__first(0,X) -> nil a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first(X1,X2) -> first(X1,X2) a__sqr(0) -> 0 a__sqr(s(X)) -> s(add(sqr(X),dbl(X))) a__sqr(X) -> sqr(X) a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) a__terms(X) -> terms(X) mark(0) -> 0 mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(nil) -> nil mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(X) mark(sqr(X)) -> a__sqr(mark(X)) mark(terms(X)) -> a__terms(mark(X)) ->Strongly Connected Components: There is no strongly connected component The problem is finite.