MAYBE

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We add following dependency tuples:

Strict DPs:
  { a__pairNs^#() -> c_1()
  , a__pairNs^#() -> c_2()
  , a__oddNs^#() -> c_3()
  , a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
  , a__incr^#(X) -> c_5()
  , a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
  , mark^#(0()) -> c_8()
  , mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_10(a__oddNs^#())
  , mark^#(s(X)) -> c_11(mark^#(X))
  , mark^#(nil()) -> c_12()
  , mark^#(take(X1, X2)) ->
    c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_16(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(pairNs()) -> c_17(a__pairNs^#())
  , mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(X1, X2) -> c_19()
  , a__take^#(0(), XS) -> c_20()
  , a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
  , a__zip^#(X1, X2) -> c_22()
  , a__zip^#(X, nil()) -> c_23()
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_24(mark^#(X), mark^#(Y))
  , a__zip^#(nil(), XS) -> c_25()
  , a__repItems^#(X) -> c_28()
  , a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
  , a__repItems^#(nil()) -> c_30()
  , a__tail^#(X) -> c_26()
  , a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }

and mark the set of starting terms.

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { a__pairNs^#() -> c_1()
  , a__pairNs^#() -> c_2()
  , a__oddNs^#() -> c_3()
  , a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
  , a__incr^#(X) -> c_5()
  , a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
  , mark^#(0()) -> c_8()
  , mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_10(a__oddNs^#())
  , mark^#(s(X)) -> c_11(mark^#(X))
  , mark^#(nil()) -> c_12()
  , mark^#(take(X1, X2)) ->
    c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_16(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(pairNs()) -> c_17(a__pairNs^#())
  , mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(X1, X2) -> c_19()
  , a__take^#(0(), XS) -> c_20()
  , a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
  , a__zip^#(X1, X2) -> c_22()
  , a__zip^#(X, nil()) -> c_23()
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_24(mark^#(X), mark^#(Y))
  , a__zip^#(nil(), XS) -> c_25()
  , a__repItems^#(X) -> c_28()
  , a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
  , a__repItems^#(nil()) -> c_30()
  , a__tail^#(X) -> c_26()
  , a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }
Weak Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We estimate the number of application of
{1,2,3,5,8,12,19,20,22,23,25,26,28,29} by applications of
Pre({1,2,3,5,8,12,19,20,22,23,25,26,28,29}) =
{4,6,7,9,10,11,13,14,15,16,17,18,21,24,27,30}. Here rules are
labeled as follows:

  DPs:
    { 1: a__pairNs^#() -> c_1()
    , 2: a__pairNs^#() -> c_2()
    , 3: a__oddNs^#() -> c_3()
    , 4: a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
    , 5: a__incr^#(X) -> c_5()
    , 6: a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
    , 7: mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
    , 8: mark^#(0()) -> c_8()
    , 9: mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
    , 10: mark^#(oddNs()) -> c_10(a__oddNs^#())
    , 11: mark^#(s(X)) -> c_11(mark^#(X))
    , 12: mark^#(nil()) -> c_12()
    , 13: mark^#(take(X1, X2)) ->
          c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
    , 14: mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
    , 15: mark^#(zip(X1, X2)) ->
          c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
    , 16: mark^#(repItems(X)) ->
          c_16(a__repItems^#(mark(X)), mark^#(X))
    , 17: mark^#(pairNs()) -> c_17(a__pairNs^#())
    , 18: mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
    , 19: a__take^#(X1, X2) -> c_19()
    , 20: a__take^#(0(), XS) -> c_20()
    , 21: a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
    , 22: a__zip^#(X1, X2) -> c_22()
    , 23: a__zip^#(X, nil()) -> c_23()
    , 24: a__zip^#(cons(X, XS), cons(Y, YS)) ->
          c_24(mark^#(X), mark^#(Y))
    , 25: a__zip^#(nil(), XS) -> c_25()
    , 26: a__repItems^#(X) -> c_28()
    , 27: a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
    , 28: a__repItems^#(nil()) -> c_30()
    , 29: a__tail^#(X) -> c_26()
    , 30: a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
  , a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
  , mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_10(a__oddNs^#())
  , mark^#(s(X)) -> c_11(mark^#(X))
  , mark^#(take(X1, X2)) ->
    c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_16(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(pairNs()) -> c_17(a__pairNs^#())
  , mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_24(mark^#(X), mark^#(Y))
  , a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
  , a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }
Weak DPs:
  { a__pairNs^#() -> c_1()
  , a__pairNs^#() -> c_2()
  , a__oddNs^#() -> c_3()
  , a__incr^#(X) -> c_5()
  , mark^#(0()) -> c_8()
  , mark^#(nil()) -> c_12()
  , a__take^#(X1, X2) -> c_19()
  , a__take^#(0(), XS) -> c_20()
  , a__zip^#(X1, X2) -> c_22()
  , a__zip^#(X, nil()) -> c_23()
  , a__zip^#(nil(), XS) -> c_25()
  , a__repItems^#(X) -> c_28()
  , a__repItems^#(nil()) -> c_30()
  , a__tail^#(X) -> c_26() }
Weak Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We estimate the number of application of {11} by applications of
Pre({11}) = {2,3,4,6,7,8,9,10,12,13,14,15,16}. Here rules are
labeled as follows:

  DPs:
    { 1: a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
    , 2: a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
    , 3: mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
    , 4: mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
    , 5: mark^#(oddNs()) -> c_10(a__oddNs^#())
    , 6: mark^#(s(X)) -> c_11(mark^#(X))
    , 7: mark^#(take(X1, X2)) ->
         c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
    , 8: mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
    , 9: mark^#(zip(X1, X2)) ->
         c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
    , 10: mark^#(repItems(X)) ->
          c_16(a__repItems^#(mark(X)), mark^#(X))
    , 11: mark^#(pairNs()) -> c_17(a__pairNs^#())
    , 12: mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
    , 13: a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
    , 14: a__zip^#(cons(X, XS), cons(Y, YS)) ->
          c_24(mark^#(X), mark^#(Y))
    , 15: a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
    , 16: a__tail^#(cons(X, XS)) -> c_27(mark^#(XS))
    , 17: a__pairNs^#() -> c_1()
    , 18: a__pairNs^#() -> c_2()
    , 19: a__oddNs^#() -> c_3()
    , 20: a__incr^#(X) -> c_5()
    , 21: mark^#(0()) -> c_8()
    , 22: mark^#(nil()) -> c_12()
    , 23: a__take^#(X1, X2) -> c_19()
    , 24: a__take^#(0(), XS) -> c_20()
    , 25: a__zip^#(X1, X2) -> c_22()
    , 26: a__zip^#(X, nil()) -> c_23()
    , 27: a__zip^#(nil(), XS) -> c_25()
    , 28: a__repItems^#(X) -> c_28()
    , 29: a__repItems^#(nil()) -> c_30()
    , 30: a__tail^#(X) -> c_26() }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
  , a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
  , mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_10(a__oddNs^#())
  , mark^#(s(X)) -> c_11(mark^#(X))
  , mark^#(take(X1, X2)) ->
    c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_16(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_24(mark^#(X), mark^#(Y))
  , a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
  , a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }
Weak DPs:
  { a__pairNs^#() -> c_1()
  , a__pairNs^#() -> c_2()
  , a__oddNs^#() -> c_3()
  , a__incr^#(X) -> c_5()
  , mark^#(0()) -> c_8()
  , mark^#(nil()) -> c_12()
  , mark^#(pairNs()) -> c_17(a__pairNs^#())
  , a__take^#(X1, X2) -> c_19()
  , a__take^#(0(), XS) -> c_20()
  , a__zip^#(X1, X2) -> c_22()
  , a__zip^#(X, nil()) -> c_23()
  , a__zip^#(nil(), XS) -> c_25()
  , a__repItems^#(X) -> c_28()
  , a__repItems^#(nil()) -> c_30()
  , a__tail^#(X) -> c_26() }
Weak Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The following weak DPs constitute a sub-graph of the DG that is
closed under successors. The DPs are removed.

{ a__pairNs^#() -> c_1()
, a__pairNs^#() -> c_2()
, a__oddNs^#() -> c_3()
, a__incr^#(X) -> c_5()
, mark^#(0()) -> c_8()
, mark^#(nil()) -> c_12()
, mark^#(pairNs()) -> c_17(a__pairNs^#())
, a__take^#(X1, X2) -> c_19()
, a__take^#(0(), XS) -> c_20()
, a__zip^#(X1, X2) -> c_22()
, a__zip^#(X, nil()) -> c_23()
, a__zip^#(nil(), XS) -> c_25()
, a__repItems^#(X) -> c_28()
, a__repItems^#(nil()) -> c_30()
, a__tail^#(X) -> c_26() }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#())
  , a__incr^#(cons(X, XS)) -> c_6(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_7(mark^#(X1))
  , mark^#(incr(X)) -> c_9(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_10(a__oddNs^#())
  , mark^#(s(X)) -> c_11(mark^#(X))
  , mark^#(take(X1, X2)) ->
    c_13(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_14(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_15(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_16(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(tail(X)) -> c_18(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(s(N), cons(X, XS)) -> c_21(mark^#(X))
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_24(mark^#(X), mark^#(Y))
  , a__repItems^#(cons(X, XS)) -> c_29(mark^#(X))
  , a__tail^#(cons(X, XS)) -> c_27(mark^#(XS)) }
Weak Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

Due to missing edges in the dependency-graph, the right-hand sides
of following rules could be simplified:

  { a__oddNs^#() -> c_4(a__incr^#(a__pairNs()), a__pairNs^#()) }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { a__oddNs^#() -> c_1(a__incr^#(a__pairNs()))
  , a__incr^#(cons(X, XS)) -> c_2(mark^#(X))
  , mark^#(cons(X1, X2)) -> c_3(mark^#(X1))
  , mark^#(incr(X)) -> c_4(a__incr^#(mark(X)), mark^#(X))
  , mark^#(oddNs()) -> c_5(a__oddNs^#())
  , mark^#(s(X)) -> c_6(mark^#(X))
  , mark^#(take(X1, X2)) ->
    c_7(a__take^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(pair(X1, X2)) -> c_8(mark^#(X1), mark^#(X2))
  , mark^#(zip(X1, X2)) ->
    c_9(a__zip^#(mark(X1), mark(X2)), mark^#(X1), mark^#(X2))
  , mark^#(repItems(X)) -> c_10(a__repItems^#(mark(X)), mark^#(X))
  , mark^#(tail(X)) -> c_11(a__tail^#(mark(X)), mark^#(X))
  , a__take^#(s(N), cons(X, XS)) -> c_12(mark^#(X))
  , a__zip^#(cons(X, XS), cons(Y, YS)) -> c_13(mark^#(X), mark^#(Y))
  , a__repItems^#(cons(X, XS)) -> c_14(mark^#(X))
  , a__tail^#(cons(X, XS)) -> c_15(mark^#(XS)) }
Weak Trs:
  { a__pairNs() -> cons(0(), incr(oddNs()))
  , a__pairNs() -> pairNs()
  , a__oddNs() -> oddNs()
  , a__oddNs() -> a__incr(a__pairNs())
  , a__incr(X) -> incr(X)
  , a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS))
  , mark(cons(X1, X2)) -> cons(mark(X1), X2)
  , mark(0()) -> 0()
  , mark(incr(X)) -> a__incr(mark(X))
  , mark(oddNs()) -> a__oddNs()
  , mark(s(X)) -> s(mark(X))
  , mark(nil()) -> nil()
  , mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
  , mark(pair(X1, X2)) -> pair(mark(X1), mark(X2))
  , mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2))
  , mark(repItems(X)) -> a__repItems(mark(X))
  , mark(pairNs()) -> a__pairNs()
  , mark(tail(X)) -> a__tail(mark(X))
  , a__take(X1, X2) -> take(X1, X2)
  , a__take(0(), XS) -> nil()
  , a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS))
  , a__zip(X1, X2) -> zip(X1, X2)
  , a__zip(X, nil()) -> nil()
  , a__zip(cons(X, XS), cons(Y, YS)) ->
    cons(pair(mark(X), mark(Y)), zip(XS, YS))
  , a__zip(nil(), XS) -> nil()
  , a__tail(X) -> tail(X)
  , a__tail(cons(X, XS)) -> mark(XS)
  , a__repItems(X) -> repItems(X)
  , a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS)))
  , a__repItems(nil()) -> nil() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The input cannot be shown compatible

Arrrr..