/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


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


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


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

(0) CpxTRS
(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) CpxTrsMatchBoundsTAProof [FINISHED, 27 ms]
    (4) BOUNDS(1, n^1)
(5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(6) TRS for Loop Detection
    (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (8) BEST
        (9) proven lower bound
            (10) LowerBoundPropagationProof [FINISHED, 0 ms]
            (11) BOUNDS(n^1, INF)
        (12) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   active(f(x)) -> mark(f(f(x)))
   chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))
   mat(f(x), f(y)) -> f(mat(x, y))
   chk(no(c)) -> active(c)
   mat(f(x), c) -> no(c)
   f(active(x)) -> active(f(x))
   f(no(x)) -> no(f(x))
   f(mark(x)) -> mark(f(x))
   tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))

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

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

(2)
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:

   active(f(x)) -> mark(f(f(x)))
   chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))
   mat(f(x), f(y)) -> f(mat(x, y))
   chk(no(c)) -> active(c)
   mat(f(x), c) -> no(c)
   f(active(x)) -> active(f(x))
   f(no(x)) -> no(f(x))
   f(mark(x)) -> mark(f(x))
   tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))

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

(3) 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 2. 

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]
transitions: 
mark0(0) -> 0
no0(0) -> 0
X0() -> 0
y0() -> 0
c0() -> 0
active0(0) -> 1
chk0(0) -> 2
mat0(0, 0) -> 3
f0(0) -> 4
tp0(0) -> 5
c1() -> 6
active1(6) -> 2
f1(0) -> 7
no1(7) -> 4
f1(0) -> 8
mark1(8) -> 4
X1() -> 14
f1(14) -> 13
f1(13) -> 12
f1(12) -> 12
f1(12) -> 11
mat1(11, 0) -> 10
chk1(10) -> 9
tp1(9) -> 5
c1() -> 15
no1(15) -> 10
no1(7) -> 7
no1(7) -> 8
mark1(8) -> 7
mark1(8) -> 8
c2() -> 16
active2(16) -> 9

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

(4)
BOUNDS(1, n^1)

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

(5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(6)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   active(f(x)) -> mark(f(f(x)))
   chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))
   mat(f(x), f(y)) -> f(mat(x, y))
   chk(no(c)) -> active(c)
   mat(f(x), c) -> no(c)
   f(active(x)) -> active(f(x))
   f(no(x)) -> no(f(x))
   f(mark(x)) -> mark(f(x))
   tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))

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

(7) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

f(no(x)) ->^+ no(f(x))

gives rise to a decreasing loop by considering the right hand sides subterm at position [0].

The pumping substitution is [x / no(x)].

The result substitution is [ ].




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

(8)
Complex Obligation (BEST)

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

(9)
Obligation:
Proved the lower bound n^1 for the following obligation:

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


The TRS R consists of the following rules:

   active(f(x)) -> mark(f(f(x)))
   chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))
   mat(f(x), f(y)) -> f(mat(x, y))
   chk(no(c)) -> active(c)
   mat(f(x), c) -> no(c)
   f(active(x)) -> active(f(x))
   f(no(x)) -> no(f(x))
   f(mark(x)) -> mark(f(x))
   tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))

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

(10) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(11)
BOUNDS(n^1, INF)

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

(12)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   active(f(x)) -> mark(f(f(x)))
   chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))
   mat(f(x), f(y)) -> f(mat(x, y))
   chk(no(c)) -> active(c)
   mat(f(x), c) -> no(c)
   f(active(x)) -> active(f(x))
   f(no(x)) -> no(f(x))
   f(mark(x)) -> mark(f(x))
   tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x)))

S is empty.
Rewrite Strategy: FULL