YES Problem 1: (VAR v_NonEmpty:S X:S X1:S X2:S XS:S) (RULES a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ) (STRATEGY INNERMOST) Problem 1: Dependency Pairs Processor: -> Pairs: A__HEAD(cons(X:S,XS:S)) -> MARK(X:S) A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__ODDS -> A__PAIRS A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> A__HEAD(mark(X:S)) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(nats) -> A__NATS MARK(odds) -> A__ODDS MARK(pairs) -> A__PAIRS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: SCC Processor: -> Pairs: A__HEAD(cons(X:S,XS:S)) -> MARK(X:S) A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__ODDS -> A__PAIRS A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> A__HEAD(mark(X:S)) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(nats) -> A__NATS MARK(odds) -> A__ODDS MARK(pairs) -> A__PAIRS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__HEAD(cons(X:S,XS:S)) -> MARK(X:S) A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> A__HEAD(mark(X:S)) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__HEAD(cons(X:S,XS:S)) -> MARK(X:S) A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> A__HEAD(mark(X:S)) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = 2.X + 2 [a__incr](X) = 2.X [a__nats] = 2 [a__odds] = 0 [a__pairs] = 0 [a__tail](X) = 2.X [mark](X) = 2.X [0] = 0 [cons](X1,X2) = 2.X1 + X2 [fSNonEmpty] = 0 [head](X) = 2.X + 1 [incr](X) = 2.X [nats] = 1 [odds] = 0 [pairs] = 0 [s](X) = X [tail](X) = 2.X [A__HEAD](X) = 2.X + 1 [A__INCR](X) = X [A__NATS] = 0 [A__ODDS] = 0 [A__PAIRS] = 0 [A__TAIL](X) = 2.X [MARK](X) = 2.X Problem 1: SCC Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> A__HEAD(mark(X:S)) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__ODDS -> A__INCR(a__pairs) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = 2.X + 1 [a__incr](X) = X [a__nats] = 1 [a__odds] = 1 [a__pairs] = 1 [a__tail](X) = 2.X + 1 [mark](X) = X [0] = 0 [cons](X1,X2) = 2.X1 + X2 [fSNonEmpty] = 0 [head](X) = 2.X + 1 [incr](X) = X [nats] = 1 [odds] = 1 [pairs] = 1 [s](X) = X [tail](X) = 2.X + 1 [A__HEAD](X) = 0 [A__INCR](X) = X [A__NATS] = 0 [A__ODDS] = 2 [A__PAIRS] = 0 [A__TAIL](X) = 2.X + 1 [MARK](X) = 2.X Problem 1: SCC Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(odds) -> A__ODDS MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) A__TAIL(cons(X:S,XS:S)) -> MARK(XS:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = 2.X + 2 [a__incr](X) = 2.X [a__nats] = 2 [a__odds] = 0 [a__pairs] = 0 [a__tail](X) = 2.X + 2 [mark](X) = 2.X [0] = 0 [cons](X1,X2) = 2.X1 + X2 [fSNonEmpty] = 0 [head](X) = 2.X + 1 [incr](X) = 2.X [nats] = 1 [odds] = 0 [pairs] = 0 [s](X) = X [tail](X) = 2.X + 2 [A__HEAD](X) = 0 [A__INCR](X) = 2.X + 1 [A__NATS] = 0 [A__ODDS] = 0 [A__PAIRS] = 0 [A__TAIL](X) = 2.X + 2 [MARK](X) = 2.X + 1 Problem 1: SCC Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> A__TAIL(mark(X:S)) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(head(X:S)) -> MARK(X:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = X + 2 [a__incr](X) = 2.X [a__nats] = 0 [a__odds] = 0 [a__pairs] = 0 [a__tail](X) = 2.X + 2 [mark](X) = 2.X [0] = 0 [cons](X1,X2) = 2.X1 + 2.X2 [fSNonEmpty] = 0 [head](X) = X + 2 [incr](X) = 2.X [nats] = 0 [odds] = 0 [pairs] = 0 [s](X) = X [tail](X) = 2.X + 2 [A__HEAD](X) = 0 [A__INCR](X) = 2.X + 2 [A__NATS] = 0 [A__ODDS] = 0 [A__PAIRS] = 0 [A__TAIL](X) = 0 [MARK](X) = 2.X + 2 Problem 1: SCC Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) MARK(tail(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = 2.X + 1 [a__incr](X) = X [a__nats] = 1 [a__odds] = 2 [a__pairs] = 2 [a__tail](X) = 2.X + 2 [mark](X) = X [0] = 0 [cons](X1,X2) = X1 + X2 [fSNonEmpty] = 0 [head](X) = 2.X + 1 [incr](X) = X [nats] = 1 [odds] = 2 [pairs] = 2 [s](X) = X [tail](X) = 2.X + 2 [A__HEAD](X) = 0 [A__INCR](X) = 2.X + 2 [A__NATS] = 0 [A__ODDS] = 0 [A__PAIRS] = 0 [A__TAIL](X) = 0 [MARK](X) = 2.X + 2 Problem 1: SCC Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Reduction Pairs Processor: -> Pairs: A__INCR(cons(X:S,XS:S)) -> MARK(X:S) MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) -> Usable rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [a__head](X) = X + 1 [a__incr](X) = X [a__nats] = 2 [a__odds] = 1 [a__pairs] = 1 [a__tail](X) = 2.X [mark](X) = X [0] = 0 [cons](X1,X2) = 2.X1 + 1/2.X2 + 1/2 [fSNonEmpty] = 0 [head](X) = X + 1 [incr](X) = X [nats] = 2 [odds] = 1 [pairs] = 1 [s](X) = X [tail](X) = 2.X [A__HEAD](X) = 0 [A__INCR](X) = 1/2.X + 1/2 [A__NATS] = 0 [A__ODDS] = 0 [A__PAIRS] = 0 [A__TAIL](X) = 0 [MARK](X) = X + 1/2 Problem 1: SCC Processor: -> Pairs: MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> A__INCR(mark(X:S)) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) ->->-> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) Problem 1: Subterm Processor: -> Pairs: MARK(cons(X1:S,X2:S)) -> MARK(X1:S) MARK(incr(X:S)) -> MARK(X:S) MARK(s(X:S)) -> MARK(X:S) -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Projection: pi(MARK) = 1 Problem 1: SCC Processor: -> Pairs: Empty -> Rules: a__head(cons(X:S,XS:S)) -> mark(X:S) a__head(X:S) -> head(X:S) a__incr(cons(X:S,XS:S)) -> cons(s(mark(X:S)),incr(XS:S)) a__incr(X:S) -> incr(X:S) a__nats -> cons(0,incr(nats)) a__nats -> nats a__odds -> a__incr(a__pairs) a__odds -> odds a__pairs -> cons(0,incr(odds)) a__pairs -> pairs a__tail(cons(X:S,XS:S)) -> mark(XS:S) a__tail(X:S) -> tail(X:S) mark(0) -> 0 mark(cons(X1:S,X2:S)) -> cons(mark(X1:S),X2:S) mark(head(X:S)) -> a__head(mark(X:S)) mark(incr(X:S)) -> a__incr(mark(X:S)) mark(nats) -> a__nats mark(odds) -> a__odds mark(pairs) -> a__pairs mark(s(X:S)) -> s(mark(X:S)) mark(tail(X:S)) -> a__tail(mark(X:S)) ->Strongly Connected Components: There is no strongly connected component The problem is finite.