Jeffrey Shallit's user avatar
Jeffrey Shallit's user avatar
Jeffrey Shallit's user avatar
Jeffrey Shallit
  • Member for 13 years, 3 months
  • Last seen more than a week ago
54 votes

Was the reduction in Shor's algorithm originally discovered by Shor?

48 votes

Are there any open problems left about DFAs?

34 votes
Accepted

Probabilistic (randomized) algorithms before "modern" computer science appeared

24 votes
Accepted

Factoring as a decision problem

21 votes
Accepted

Efficient concatenation of DFAs?

21 votes

Importance of irrational numbers in computer science

20 votes
Accepted

Source of Turing-machine illustration

20 votes
Accepted

complexity of the half language

19 votes
Accepted

Quadratic relationship between nondeterministic and deterministic space?

19 votes
Accepted

Any computable transcendental number that is computable in P time but not $O(n)$

18 votes
Accepted

Is Hartmanis-Stearns conjecture settled by this article?

18 votes
Accepted

Post Correspondence Problem variant

18 votes
Accepted

The significance of state complexity in automata and regular languages?

17 votes

A special class of languages: “circular” languages. Is it known?

17 votes

Easy problems with hard counting versions

16 votes

How to check if a number is a perfect power in polynomial time

16 votes
Accepted

Decide the existence of a string homomorphism

15 votes

Languages that we cannot (dis)prove to be Context-Free

14 votes

Irreducible languages

12 votes
Accepted

Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

11 votes
Accepted

computing maximal bit density over a FSM

10 votes

Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

10 votes
Accepted

Chomsky Schützenberger enumeration theorem

10 votes

Is the complement of { www | … } context-free?

10 votes

Base-k representations of the co-domain of a polynomial - is it context-free?

9 votes

Maximum shortest word accepted by pushdown automata

9 votes
Accepted

Mistake in Wikipedia CSG example?

9 votes

Boundary between decidability and undecidability for small theories

9 votes
Accepted

Kleene closure of DFA

9 votes
Accepted

Factoring assuming smoothness of some numbers