/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 (innermost) 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), 50 ms]
(4) CpxRelTRS
(5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
(6) CpxTRS
(7) CpxTrsMatchBoundsProof [FINISHED, 35 ms]
(8) BOUNDS(1, n^1)


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

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


The TRS R consists of the following rules:

   active(c) -> mark(f(g(c)))
   active(f(g(X))) -> mark(g(X))
   mark(c) -> active(c)
   mark(f(X)) -> active(f(X))
   mark(g(X)) -> active(g(X))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   g(mark(X)) -> g(X)
   g(active(X)) -> g(X)

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

(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(c) -> c
   encArg(cons_active(x_1)) -> active(encArg(x_1))
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encode_active(x_1) -> active(encArg(x_1))
   encode_c -> c
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))


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

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


The TRS R consists of the following rules:

   active(c) -> mark(f(g(c)))
   active(f(g(X))) -> mark(g(X))
   mark(c) -> active(c)
   mark(f(X)) -> active(f(X))
   mark(g(X)) -> active(g(X))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   g(mark(X)) -> g(X)
   g(active(X)) -> g(X)

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

   encArg(c) -> c
   encArg(cons_active(x_1)) -> active(encArg(x_1))
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encode_active(x_1) -> active(encArg(x_1))
   encode_c -> c
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))

Rewrite Strategy: INNERMOST
----------------------------------------

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

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


The TRS R consists of the following rules:

   active(c) -> mark(f(g(c)))
   active(f(g(X))) -> mark(g(X))
   mark(c) -> active(c)
   mark(f(X)) -> active(f(X))
   mark(g(X)) -> active(g(X))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   g(mark(X)) -> g(X)
   g(active(X)) -> g(X)

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

   encArg(c) -> c
   encArg(cons_active(x_1)) -> active(encArg(x_1))
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encode_active(x_1) -> active(encArg(x_1))
   encode_c -> c
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))

Rewrite Strategy: INNERMOST
----------------------------------------

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

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


The TRS R consists of the following rules:

   active(c) -> mark(f(g(c)))
   active(f(g(X))) -> mark(g(X))
   mark(c) -> active(c)
   mark(f(X)) -> active(f(X))
   mark(g(X)) -> active(g(X))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   g(mark(X)) -> g(X)
   g(active(X)) -> g(X)
   encArg(c) -> c
   encArg(cons_active(x_1)) -> active(encArg(x_1))
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encode_active(x_1) -> active(encArg(x_1))
   encode_c -> c
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))

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

(7) CpxTrsMatchBoundsProof (FINISHED)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 5. 
The certificate found is represented by the following graph.

"[58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81]
{(58,59,[active_1|0, mark_1|0, f_1|0, g_1|0, encArg_1|0, encode_active_1|0, encode_c|0, encode_mark_1|0, encode_f_1|0, encode_g_1|0, c|1]), (58,60,[mark_1|1]), (58,63,[active_1|1]), (58,64,[active_1|1, mark_1|1, f_1|1, g_1|1, f_1|2, g_1|2]), (58,65,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (58,66,[mark_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (58,69,[mark_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (58,70,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (58,71,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (58,72,[active_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (58,73,[mark_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (58,74,[active_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (58,75,[mark_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (58,78,[active_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (58,79,[active_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (58,80,[mark_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (58,81,[active_1|5, f_1|2, f_1|3, g_1|2, g_1|3]), (59,59,[c|0, cons_active_1|0, cons_mark_1|0, cons_f_1|0, cons_g_1|0]), (60,61,[f_1|1]), (61,62,[g_1|1]), (62,59,[c|1]), (63,59,[c|1]), (64,59,[encArg_1|1, c|1]), (64,64,[active_1|1, mark_1|1, f_1|1, g_1|1, f_1|2, g_1|2]), (64,66,[mark_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (64,69,[mark_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (64,70,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (64,65,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (64,71,[active_1|2, f_1|2, f_1|3, g_1|2, g_1|3]), (64,72,[active_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (64,74,[active_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (64,75,[mark_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (64,73,[mark_1|3, f_1|2, f_1|3, g_1|2, g_1|3]), (64,79,[active_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (64,78,[active_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (64,80,[mark_1|4, f_1|2, f_1|3, g_1|2, g_1|3]), (64,81,[active_1|5, f_1|2, f_1|3, g_1|2, g_1|3]), (65,61,[f_1|2]), (65,64,[f_1|2]), (65,66,[f_1|3, f_1|2]), (65,69,[f_1|3, f_1|2]), (65,70,[f_1|3, f_1|2]), (65,65,[f_1|3, f_1|2]), (65,71,[f_1|3, f_1|2]), (65,72,[f_1|3, f_1|2]), (65,74,[f_1|3, f_1|2]), (65,75,[f_1|3, f_1|2]), (65,73,[f_1|3, f_1|2]), (65,79,[f_1|3, f_1|2]), (65,78,[f_1|3, f_1|2]), (65,80,[f_1|3, f_1|2]), (65,81,[f_1|3, f_1|2]), (66,67,[f_1|2]), (67,68,[g_1|2]), (68,59,[c|2]), (69,64,[g_1|2]), (69,62,[g_1|2]), (69,66,[g_1|3, g_1|2]), (69,69,[g_1|3, g_1|2]), (69,70,[g_1|3, g_1|2]), (69,65,[g_1|3, g_1|2]), (69,71,[g_1|3, g_1|2]), (69,72,[g_1|3, g_1|2]), (69,74,[g_1|3, g_1|2]), (69,75,[g_1|3, g_1|2]), (69,73,[g_1|3, g_1|2]), (69,68,[g_1|2]), (69,79,[g_1|3, g_1|2]), (69,78,[g_1|3, g_1|2]), (69,80,[g_1|3, g_1|2]), (69,77,[g_1|2]), (69,81,[g_1|3, g_1|2]), (70,59,[c|2]), (71,64,[g_1|2]), (71,66,[g_1|3, g_1|2]), (71,69,[g_1|3, g_1|2]), (71,70,[g_1|3, g_1|2]), (71,65,[g_1|3, g_1|2]), (71,71,[g_1|3, g_1|2]), (71,72,[g_1|3, g_1|2]), (71,74,[g_1|3, g_1|2]), (71,75,[g_1|3, g_1|2]), (71,73,[g_1|3, g_1|2]), (71,79,[g_1|3, g_1|2]), (71,78,[g_1|3, g_1|2]), (71,80,[g_1|3, g_1|2]), (71,81,[g_1|3, g_1|2]), (72,67,[f_1|3]), (73,64,[g_1|3, g_1|2]), (73,68,[g_1|3]), (73,66,[g_1|3]), (73,69,[g_1|3]), (73,70,[g_1|3]), (73,65,[g_1|3]), (73,71,[g_1|3]), (73,62,[g_1|3]), (73,72,[g_1|4, g_1|3]), (73,74,[g_1|4, g_1|3]), (73,75,[g_1|4, g_1|3]), (73,73,[g_1|4, g_1|3]), (73,79,[g_1|4, g_1|3]), (73,78,[g_1|4, g_1|3]), (73,80,[g_1|4, g_1|3]), (73,77,[g_1|3]), (73,81,[g_1|4, g_1|3]), (74,64,[g_1|3, g_1|2]), (74,62,[g_1|3]), (74,66,[g_1|3]), (74,69,[g_1|3]), (74,70,[g_1|3]), (74,65,[g_1|3]), (74,71,[g_1|3]), (74,72,[g_1|4, g_1|3]), (74,74,[g_1|4, g_1|3]), (74,75,[g_1|4, g_1|3]), (74,73,[g_1|4, g_1|3]), (74,79,[g_1|4, g_1|3]), (74,78,[g_1|4, g_1|3]), (74,68,[g_1|3]), (74,80,[g_1|4, g_1|3]), (74,81,[g_1|4, g_1|3]), (74,77,[g_1|3]), (75,76,[f_1|3]), (76,77,[g_1|3]), (77,59,[c|3]), (78,64,[g_1|4, g_1|2]), (78,68,[g_1|4]), (78,66,[g_1|4, g_1|3]), (78,69,[g_1|4, g_1|3]), (78,70,[g_1|4, g_1|3]), (78,65,[g_1|4, g_1|3]), (78,71,[g_1|4, g_1|3]), (78,62,[g_1|4]), (78,72,[g_1|4, g_1|3]), (78,74,[g_1|4, g_1|3]), (78,75,[g_1|4, g_1|3]), (78,73,[g_1|4, g_1|3]), (78,79,[g_1|5, g_1|4, g_1|3]), (78,78,[g_1|5, g_1|4, g_1|3]), (78,80,[g_1|5, g_1|3, g_1|4]), (78,81,[g_1|5, g_1|3, g_1|4]), (78,77,[g_1|4]), (79,76,[f_1|4]), (80,77,[g_1|4]), (81,77,[g_1|5])}"
----------------------------------------

(8)
BOUNDS(1, n^1)