We consider the following Problem:
Strict Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, oddNs() -> incr(pairNs())
, incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS)))
, take(0(), XS) -> nil()
, take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS)))
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, zip(cons(X, XS), cons(Y, YS)) ->
cons(pair(X, Y), n__zip(activate(XS), activate(YS)))
, tail(cons(X, XS)) -> activate(XS)
, repItems(nil()) -> nil()
, repItems(cons(X, XS)) ->
cons(X, n__cons(X, n__repItems(activate(XS))))
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(n__incr(X)) -> incr(activate(X))
, activate(n__oddNs()) -> oddNs()
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
Arguments of following rules are not normal-forms:
{ incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS)))
, take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS)))
, zip(cons(X, XS), cons(Y, YS)) ->
cons(pair(X, Y), n__zip(activate(XS), activate(YS)))
, tail(cons(X, XS)) -> activate(XS)
, repItems(cons(X, XS)) ->
cons(X, n__cons(X, n__repItems(activate(XS))))}
All above mentioned rules can be savely removed.
We consider the following Problem:
Strict Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(n__incr(X)) -> incr(activate(X))
, activate(n__oddNs()) -> oddNs()
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
The weightgap principle applies, where following rules are oriented strictly:
TRS Component:
{ oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(X) -> X}
Interpretation of nonconstant growth:
-------------------------------------
The following argument positions are usable:
Uargs(cons) = {1}, Uargs(n__incr) = {}, Uargs(incr) = {1},
Uargs(s) = {}, Uargs(activate) = {}, Uargs(take) = {1, 2},
Uargs(n__take) = {}, Uargs(zip) = {1, 2}, Uargs(pair) = {},
Uargs(n__zip) = {}, Uargs(tail) = {}, Uargs(repItems) = {1},
Uargs(n__cons) = {}, Uargs(n__repItems) = {}
We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation:
Interpretation Functions:
pairNs() = [0]
[0]
cons(x1, x2) = [1 0] x1 + [0 0] x2 + [1]
[0 0] [0 0] [1]
0() = [0]
[0]
n__incr(x1) = [1 0] x1 + [0]
[0 0] [0]
n__oddNs() = [0]
[0]
oddNs() = [2]
[2]
incr(x1) = [1 0] x1 + [1]
[0 0] [1]
s(x1) = [1 0] x1 + [0]
[0 1] [0]
activate(x1) = [1 0] x1 + [1]
[0 1] [1]
take(x1, x2) = [1 1] x1 + [1 0] x2 + [1]
[0 0] [0 0] [1]
nil() = [0]
[0]
n__take(x1, x2) = [1 1] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
zip(x1, x2) = [1 0] x1 + [1 0] x2 + [1]
[0 0] [0 0] [1]
pair(x1, x2) = [0 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__zip(x1, x2) = [1 0] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
tail(x1) = [0 0] x1 + [0]
[0 0] [0]
repItems(x1) = [1 0] x1 + [1]
[0 0] [1]
n__cons(x1, x2) = [1 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__repItems(x1) = [1 0] x1 + [0]
[0 0] [0]
The strictly oriented rules are moved into the weak component.
We consider the following Problem:
Strict Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, activate(n__incr(X)) -> incr(activate(X))
, activate(n__oddNs()) -> oddNs()
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))}
Weak Trs:
{ oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
The weightgap principle applies, where following rules are oriented strictly:
TRS Component: {activate(n__oddNs()) -> oddNs()}
Interpretation of nonconstant growth:
-------------------------------------
The following argument positions are usable:
Uargs(cons) = {1}, Uargs(n__incr) = {}, Uargs(incr) = {1},
Uargs(s) = {}, Uargs(activate) = {}, Uargs(take) = {1, 2},
Uargs(n__take) = {}, Uargs(zip) = {1, 2}, Uargs(pair) = {},
Uargs(n__zip) = {}, Uargs(tail) = {}, Uargs(repItems) = {1},
Uargs(n__cons) = {}, Uargs(n__repItems) = {}
We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation:
Interpretation Functions:
pairNs() = [0]
[0]
cons(x1, x2) = [1 0] x1 + [0 0] x2 + [1]
[0 0] [0 0] [1]
0() = [0]
[0]
n__incr(x1) = [1 0] x1 + [0]
[0 0] [0]
n__oddNs() = [0]
[0]
oddNs() = [0]
[1]
incr(x1) = [1 0] x1 + [0]
[0 0] [1]
s(x1) = [1 0] x1 + [0]
[0 1] [0]
activate(x1) = [1 0] x1 + [1]
[0 1] [1]
take(x1, x2) = [1 1] x1 + [1 0] x2 + [0]
[0 0] [0 0] [1]
nil() = [0]
[0]
n__take(x1, x2) = [1 1] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
zip(x1, x2) = [1 0] x1 + [1 0] x2 + [1]
[0 0] [0 0] [1]
pair(x1, x2) = [0 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__zip(x1, x2) = [1 0] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
tail(x1) = [0 0] x1 + [0]
[0 0] [0]
repItems(x1) = [1 0] x1 + [0]
[0 0] [1]
n__cons(x1, x2) = [1 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__repItems(x1) = [1 0] x1 + [0]
[0 0] [0]
The strictly oriented rules are moved into the weak component.
We consider the following Problem:
Strict Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, activate(n__incr(X)) -> incr(activate(X))
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))}
Weak Trs:
{ activate(n__oddNs()) -> oddNs()
, oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
The weightgap principle applies, where following rules are oriented strictly:
TRS Component: {pairNs() -> cons(0(), n__incr(n__oddNs()))}
Interpretation of nonconstant growth:
-------------------------------------
The following argument positions are usable:
Uargs(cons) = {1}, Uargs(n__incr) = {}, Uargs(incr) = {1},
Uargs(s) = {}, Uargs(activate) = {}, Uargs(take) = {1, 2},
Uargs(n__take) = {}, Uargs(zip) = {1, 2}, Uargs(pair) = {},
Uargs(n__zip) = {}, Uargs(tail) = {}, Uargs(repItems) = {1},
Uargs(n__cons) = {}, Uargs(n__repItems) = {}
We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation:
Interpretation Functions:
pairNs() = [2]
[2]
cons(x1, x2) = [1 0] x1 + [0 0] x2 + [1]
[0 0] [0 0] [1]
0() = [0]
[0]
n__incr(x1) = [1 0] x1 + [0]
[0 0] [0]
n__oddNs() = [2]
[0]
oddNs() = [2]
[1]
incr(x1) = [1 0] x1 + [0]
[0 0] [1]
s(x1) = [1 0] x1 + [0]
[0 1] [0]
activate(x1) = [1 0] x1 + [1]
[0 1] [1]
take(x1, x2) = [1 0] x1 + [1 0] x2 + [1]
[0 0] [0 0] [1]
nil() = [0]
[0]
n__take(x1, x2) = [1 0] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
zip(x1, x2) = [1 0] x1 + [1 0] x2 + [1]
[0 0] [0 0] [1]
pair(x1, x2) = [0 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__zip(x1, x2) = [1 0] x1 + [1 0] x2 + [0]
[0 0] [0 0] [0]
tail(x1) = [0 0] x1 + [0]
[0 0] [0]
repItems(x1) = [1 0] x1 + [0]
[0 0] [1]
n__cons(x1, x2) = [1 0] x1 + [0 0] x2 + [0]
[0 0] [0 0] [0]
n__repItems(x1) = [1 0] x1 + [0]
[0 0] [0]
The strictly oriented rules are moved into the weak component.
We consider the following Problem:
Strict Trs:
{ activate(n__incr(X)) -> incr(activate(X))
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))}
Weak Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, activate(n__oddNs()) -> oddNs()
, oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
We consider the following Problem:
Strict Trs:
{ activate(n__incr(X)) -> incr(activate(X))
, activate(n__take(X1, X2)) -> take(activate(X1), activate(X2))
, activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2))
, activate(n__cons(X1, X2)) -> cons(activate(X1), X2)
, activate(n__repItems(X)) -> repItems(activate(X))}
Weak Trs:
{ pairNs() -> cons(0(), n__incr(n__oddNs()))
, activate(n__oddNs()) -> oddNs()
, oddNs() -> incr(pairNs())
, take(0(), XS) -> nil()
, zip(nil(), XS) -> nil()
, zip(X, nil()) -> nil()
, repItems(nil()) -> nil()
, incr(X) -> n__incr(X)
, oddNs() -> n__oddNs()
, take(X1, X2) -> n__take(X1, X2)
, zip(X1, X2) -> n__zip(X1, X2)
, cons(X1, X2) -> n__cons(X1, X2)
, repItems(X) -> n__repItems(X)
, activate(X) -> X}
StartTerms: basic terms
Strategy: innermost
Certificate: YES(?,O(n^1))
Proof:
The problem is match-bounded by 2.
The enriched problem is compatible with the following automaton:
{ pairNs_0() -> 1
, pairNs_1() -> 3
, pairNs_2() -> 5
, cons_0(2, 2) -> 1
, cons_1(3, 2) -> 1
, cons_1(3, 2) -> 3
, cons_2(6, 7) -> 3
, cons_2(6, 7) -> 5
, 0_0() -> 1
, 0_0() -> 2
, 0_0() -> 3
, 0_1() -> 3
, 0_2() -> 6
, n__incr_0(1) -> 1
, n__incr_0(2) -> 1
, n__incr_0(2) -> 2
, n__incr_0(2) -> 3
, n__incr_1(3) -> 1
, n__incr_1(3) -> 3
, n__incr_1(4) -> 1
, n__incr_1(4) -> 2
, n__incr_1(4) -> 3
, n__incr_2(5) -> 3
, n__incr_2(5) -> 5
, n__incr_2(8) -> 7
, n__oddNs_0() -> 1
, n__oddNs_0() -> 2
, n__oddNs_0() -> 3
, n__oddNs_1() -> 3
, n__oddNs_1() -> 4
, n__oddNs_1() -> 5
, n__oddNs_2() -> 5
, n__oddNs_2() -> 8
, oddNs_0() -> 1
, oddNs_1() -> 3
, oddNs_2() -> 5
, incr_0(1) -> 1
, incr_0(2) -> 1
, incr_1(3) -> 1
, incr_1(3) -> 3
, incr_2(5) -> 3
, incr_2(5) -> 5
, activate_0(2) -> 1
, activate_1(2) -> 3
, activate_1(4) -> 3
, activate_2(4) -> 5
, take_0(2, 2) -> 1
, take_1(3, 3) -> 1
, take_1(3, 3) -> 3
, nil_0() -> 1
, nil_0() -> 2
, nil_0() -> 3
, nil_1() -> 1
, nil_1() -> 3
, n__take_0(2, 2) -> 1
, n__take_0(2, 2) -> 2
, n__take_0(2, 2) -> 3
, n__take_1(3, 3) -> 1
, n__take_1(3, 3) -> 3
, zip_0(2, 2) -> 1
, zip_1(3, 3) -> 1
, zip_1(3, 3) -> 3
, n__zip_0(2, 2) -> 1
, n__zip_0(2, 2) -> 2
, n__zip_0(2, 2) -> 3
, n__zip_1(3, 3) -> 1
, n__zip_1(3, 3) -> 3
, repItems_0(2) -> 1
, repItems_1(3) -> 1
, repItems_1(3) -> 3
, n__cons_0(2, 2) -> 1
, n__cons_0(2, 2) -> 2
, n__cons_0(2, 2) -> 3
, n__cons_1(3, 2) -> 1
, n__cons_1(3, 2) -> 3
, n__cons_2(6, 7) -> 3
, n__cons_2(6, 7) -> 5
, n__repItems_0(2) -> 1
, n__repItems_0(2) -> 2
, n__repItems_0(2) -> 3
, n__repItems_1(3) -> 1
, n__repItems_1(3) -> 3}
Hurray, we answered YES(?,O(n^1))