Michaël Cadilhac's user avatar
Michaël Cadilhac's user avatar
Michaël Cadilhac's user avatar
Michaël Cadilhac
  • Member for 13 years, 3 months
  • Last seen more than a week ago
47 votes
3 answers
5k views

An NP-complete variant of factoring.

19 votes
0 answers
514 views

To what extent MSO = WS1S, when adding relations?

17 votes
3 answers
913 views

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

17 votes
1 answer
910 views

Completeness and Context-Sensitive Languages.

16 votes
1 answer
384 views

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

13 votes
1 answer
968 views

Space-time tradeoff lower bounds

12 votes
3 answers
459 views

Does there exist a hardest DCFL?

11 votes
1 answer
339 views

Regular languages and constant communication complexity

11 votes
0 answers
107 views

Chomsky-Schützenberger for Deterministic CFLs

11 votes
1 answer
646 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
164 views

A language outside the Boolean closure of stochastic languages

10 votes
0 answers
101 views

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

10 votes
0 answers
248 views

Smallest context-free grammar for powers of two summing to $2^k$

6 votes
2 answers
376 views

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

5 votes
3 answers
368 views

Hilbert's Tenth Problem and nonrecursive Diophantine sets

5 votes
0 answers
169 views

The regularity of Markov chains with a threshold

5 votes
0 answers
95 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
104 views

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