C.P.
  • Member for 8 years, 5 months
  • Last seen more than a month ago
Regular versus TC0
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
Closure of Recognizable Languages under Kleene Star: Algebraic Proof?
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
k-testable languages with non-constant k?
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
Size hierachy for uniform circuits
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
Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$
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
Are there non-constructive proofs of existence of "small" Turing machines / NFAs?
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