user avatar
user avatar
user avatar
Michaël Cadilhac
  • Member for 11 years, 10 months
  • Last seen this week
48 votes
3 answers
5k views

An NP-complete variant of factoring.

19 votes
0 answers
492 views

To what extent MSO = WS1S, when adding relations?

17 votes
3 answers
858 views

Which $AC^0$ problems are not "truly feasible"?

16 votes
1 answer
378 views

Compared growth of the number of syntactic classes and Nerode classes.

16 votes
1 answer
860 views

Completeness and Context-Sensitive Languages.

13 votes
1 answer
892 views

Space-time tradeoff lower bounds

12 votes
3 answers
428 views

Does there exist a hardest DCFL?

11 votes
0 answers
106 views

Chomsky-Schützenberger for Deterministic CFLs

11 votes
1 answer
618 views

Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

10 votes
2 answers
231 views

When does an FO property kill off NL-hardness?

10 votes
0 answers
156 views

A language outside the Boolean closure of stochastic languages

10 votes
0 answers
98 views

Complexity of checking $a > br^m + cr^n$, with $r$ rational

9 votes
1 answer
297 views

Regular languages and constant communication complexity

6 votes
2 answers
361 views

Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

5 votes
3 answers
364 views

Hilbert's Tenth Problem and nonrecursive Diophantine sets

5 votes
0 answers
166 views

The regularity of Markov chains with a threshold

5 votes
0 answers
91 views

How much smaller can universal Turing machines get if they only need to be universal for a subclass?

4 votes
1 answer
133 views

If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

4 votes
0 answers
103 views

$\mathsf{P}$ is the closure of [finite set] under [operation between languages]