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

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

rec(rec(x)) → sent(rec(x))
rec(sent(x)) → sent(rec(x))
rec(no(x)) → sent(rec(x))
rec(bot) → up(sent(bot))
rec(up(x)) → up(rec(x))
sent(up(x)) → up(sent(x))
no(up(x)) → up(no(x))
top(rec(up(x))) → top(check(rec(x)))
top(sent(up(x))) → top(check(rec(x)))
top(no(up(x))) → top(check(rec(x)))
check(up(x)) → up(check(x))
check(sent(x)) → sent(check(x))
check(rec(x)) → rec(check(x))
check(no(x)) → no(check(x))
check(no(x)) → no(x)

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

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

Start state: 1
Accept states: [2]
Transitions:
1→2[rec_1|0, sent_1|0, no_1|0, top_1|0, check_1|0]
1→3[up_1|1]
1→5[up_1|1]
1→6[up_1|1]
1→7[up_1|1]
1→8[up_1|1]
2→2[bot|0, up_1|0]
3→4[sent_1|1]
4→2[bot|1]
5→2[rec_1|1]
5→3[up_1|1]
5→5[up_1|1]
6→2[sent_1|1]
6→6[up_1|1]
7→2[no_1|1]
7→7[up_1|1]
8→2[check_1|1]
8→8[up_1|1]

(2) BOUNDS(1, n^1)