/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(?, O(n^1))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^1).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 183 ms]
(4) CpxRelTRS
(5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
(6) CpxTRS
(7) CpxTrsMatchBoundsTAProof [FINISHED, 187 ms]
(8) BOUNDS(1, n^1)


----------------------------------------

(0)
Obligation:
The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   app(nil, YS) -> YS
   app(cons(X), YS) -> cons(X)
   from(X) -> cons(X)
   zWadr(nil, YS) -> nil
   zWadr(XS, nil) -> nil
   zWadr(cons(X), cons(Y)) -> cons(app(Y, cons(X)))
   prefix(L) -> cons(nil)

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(nil) -> nil
   encArg(cons(x_1)) -> cons(encArg(x_1))
   encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2))
   encArg(cons_from(x_1)) -> from(encArg(x_1))
   encArg(cons_zWadr(x_1, x_2)) -> zWadr(encArg(x_1), encArg(x_2))
   encArg(cons_prefix(x_1)) -> prefix(encArg(x_1))
   encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_cons(x_1) -> cons(encArg(x_1))
   encode_from(x_1) -> from(encArg(x_1))
   encode_zWadr(x_1, x_2) -> zWadr(encArg(x_1), encArg(x_2))
   encode_prefix(x_1) -> prefix(encArg(x_1))


----------------------------------------

(2)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   app(nil, YS) -> YS
   app(cons(X), YS) -> cons(X)
   from(X) -> cons(X)
   zWadr(nil, YS) -> nil
   zWadr(XS, nil) -> nil
   zWadr(cons(X), cons(Y)) -> cons(app(Y, cons(X)))
   prefix(L) -> cons(nil)

The (relative) TRS S consists of the following rules:

   encArg(nil) -> nil
   encArg(cons(x_1)) -> cons(encArg(x_1))
   encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2))
   encArg(cons_from(x_1)) -> from(encArg(x_1))
   encArg(cons_zWadr(x_1, x_2)) -> zWadr(encArg(x_1), encArg(x_2))
   encArg(cons_prefix(x_1)) -> prefix(encArg(x_1))
   encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_cons(x_1) -> cons(encArg(x_1))
   encode_from(x_1) -> from(encArg(x_1))
   encode_zWadr(x_1, x_2) -> zWadr(encArg(x_1), encArg(x_2))
   encode_prefix(x_1) -> prefix(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(4)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   app(nil, YS) -> YS
   app(cons(X), YS) -> cons(X)
   from(X) -> cons(X)
   zWadr(nil, YS) -> nil
   zWadr(XS, nil) -> nil
   zWadr(cons(X), cons(Y)) -> cons(app(Y, cons(X)))
   prefix(L) -> cons(nil)

The (relative) TRS S consists of the following rules:

   encArg(nil) -> nil
   encArg(cons(x_1)) -> cons(encArg(x_1))
   encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2))
   encArg(cons_from(x_1)) -> from(encArg(x_1))
   encArg(cons_zWadr(x_1, x_2)) -> zWadr(encArg(x_1), encArg(x_2))
   encArg(cons_prefix(x_1)) -> prefix(encArg(x_1))
   encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_cons(x_1) -> cons(encArg(x_1))
   encode_from(x_1) -> from(encArg(x_1))
   encode_zWadr(x_1, x_2) -> zWadr(encArg(x_1), encArg(x_2))
   encode_prefix(x_1) -> prefix(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

(5) RelTrsToTrsProof (UPPER BOUND(ID))
transformed relative TRS to TRS
----------------------------------------

(6)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   app(nil, YS) -> YS
   app(cons(X), YS) -> cons(X)
   from(X) -> cons(X)
   zWadr(nil, YS) -> nil
   zWadr(XS, nil) -> nil
   zWadr(cons(X), cons(Y)) -> cons(app(Y, cons(X)))
   prefix(L) -> cons(nil)
   encArg(nil) -> nil
   encArg(cons(x_1)) -> cons(encArg(x_1))
   encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2))
   encArg(cons_from(x_1)) -> from(encArg(x_1))
   encArg(cons_zWadr(x_1, x_2)) -> zWadr(encArg(x_1), encArg(x_2))
   encArg(cons_prefix(x_1)) -> prefix(encArg(x_1))
   encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_cons(x_1) -> cons(encArg(x_1))
   encode_from(x_1) -> from(encArg(x_1))
   encode_zWadr(x_1, x_2) -> zWadr(encArg(x_1), encArg(x_2))
   encode_prefix(x_1) -> prefix(encArg(x_1))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(7) CpxTrsMatchBoundsTAProof (FINISHED)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 3. 

The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
transitions: 
nil0() -> 0
cons0(0) -> 0
cons_app0(0, 0) -> 0
cons_from0(0) -> 0
cons_zWadr0(0, 0) -> 0
cons_prefix0(0) -> 0
app0(0, 0) -> 1
from0(0) -> 2
zWadr0(0, 0) -> 3
prefix0(0) -> 4
encArg0(0) -> 5
encode_app0(0, 0) -> 6
encode_nil0() -> 7
encode_cons0(0) -> 8
encode_from0(0) -> 9
encode_zWadr0(0, 0) -> 10
encode_prefix0(0) -> 11
cons1(0) -> 1
cons1(0) -> 2
nil1() -> 3
cons1(0) -> 13
app1(0, 13) -> 12
cons1(12) -> 3
nil1() -> 14
cons1(14) -> 4
nil1() -> 5
encArg1(0) -> 15
cons1(15) -> 5
encArg1(0) -> 16
encArg1(0) -> 17
app1(16, 17) -> 5
encArg1(0) -> 18
from1(18) -> 5
encArg1(0) -> 19
encArg1(0) -> 20
zWadr1(19, 20) -> 5
encArg1(0) -> 21
prefix1(21) -> 5
app1(16, 17) -> 6
nil1() -> 7
cons1(15) -> 8
from1(18) -> 9
zWadr1(19, 20) -> 10
prefix1(21) -> 11
cons2(18) -> 5
cons2(18) -> 9
nil2() -> 22
cons2(22) -> 5
cons2(22) -> 11
nil1() -> 15
nil1() -> 16
nil1() -> 17
nil1() -> 18
nil1() -> 19
nil1() -> 20
nil1() -> 21
cons1(15) -> 15
cons1(15) -> 16
cons1(15) -> 17
cons1(15) -> 18
cons1(15) -> 19
cons1(15) -> 20
cons1(15) -> 21
app1(16, 17) -> 15
app1(16, 17) -> 16
app1(16, 17) -> 17
app1(16, 17) -> 18
app1(16, 17) -> 19
app1(16, 17) -> 20
app1(16, 17) -> 21
from1(18) -> 15
from1(18) -> 16
from1(18) -> 17
from1(18) -> 18
from1(18) -> 19
from1(18) -> 20
from1(18) -> 21
zWadr1(19, 20) -> 15
zWadr1(19, 20) -> 16
zWadr1(19, 20) -> 17
zWadr1(19, 20) -> 18
zWadr1(19, 20) -> 19
zWadr1(19, 20) -> 20
zWadr1(19, 20) -> 21
prefix1(21) -> 15
prefix1(21) -> 16
prefix1(21) -> 17
prefix1(21) -> 18
prefix1(21) -> 19
prefix1(21) -> 20
prefix1(21) -> 21
cons2(15) -> 5
cons2(15) -> 6
cons2(15) -> 15
cons2(15) -> 16
cons2(15) -> 17
cons2(18) -> 15
cons2(18) -> 16
cons2(18) -> 17
nil2() -> 5
nil2() -> 10
nil2() -> 15
nil2() -> 16
nil2() -> 17
cons2(15) -> 24
app2(15, 24) -> 23
cons2(23) -> 5
cons2(23) -> 10
cons2(23) -> 15
cons2(23) -> 16
cons2(23) -> 17
app2(18, 24) -> 23
app2(23, 24) -> 23
cons2(18) -> 24
cons2(23) -> 24
cons3(15) -> 23
cons3(18) -> 23
cons3(23) -> 23
0 -> 1
13 -> 12
17 -> 5
17 -> 6
17 -> 15
17 -> 16
17 -> 18
17 -> 19
17 -> 20
17 -> 21
24 -> 23

----------------------------------------

(8)
BOUNDS(1, n^1)