Locally testable languages form a subset of the first-order definable languages, where the only allowed numerical predicate is the successor (see Straubing, page 46 [1]). By allowing the "local" ...

A well known and studied example: the monoïde $\mathbb{N}^k$. Indeed, for $k\geq 2$, $\text{Rec}(\mathbb{N}^k)$ are more or less periodic rectangles meanwhile $\text{Rat}(\mathbb{N}^k)$ is the class ...

For a pointer on concatenation-like operations (including Kleene star) and their impact on the algebraic structure, you can look to Schützenberger products (see here [1] for instance). [1] Pin, Jean-...

Another solution is to use Higman's lemma: A language closed under subwords is regular. With $u$ a subword of $v$ if we can obtain $u$ by removing some letter in $v$. So take any language ...

Take $S_5$ as alphabet and $$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$ Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}...

Not sure about what kind of results you seek but here what I know for sub-classes of $AC^0$ (constant depth and polynomial size Boolean circuits): The separation between $AC^0$ and its linear ...