user avatar
user avatar
user avatar
Michaël Cadilhac
  • Member for 12 years
  • Last seen more than a week ago
48 votes
3 answers
5k views

An NP-complete variant of factoring.

19 votes
0 answers
496 views

To what extent MSO = WS1S, when adding relations?

17 votes
3 answers
864 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
861 views

Completeness and Context-Sensitive Languages.

13 votes
1 answer
896 views

Space-time tradeoff lower bounds

12 votes
3 answers
429 views

Does there exist a hardest DCFL?

11 votes
0 answers
106 views

Chomsky-Schützenberger for Deterministic CFLs

11 votes
1 answer
621 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
99 views

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

9 votes
1 answer
299 views

Regular languages and constant communication complexity

8 votes
0 answers
149 views

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

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
167 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
104 views

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