C.P.
• Member for 8 years, 5 months
• Last seen more than a month ago

## 6 Answers

3 votes

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" ...

View answer
2 votes

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 ...

View answer
4 votes

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-...

View answer
2 votes

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 ...

View answer
Accepted answer
17 votes

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}... View answer 3 votes 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 ...

View answer