Skip to main content
Denis's user avatar
Denis's user avatar
Denis's user avatar
Denis
  • Member for 12 years, 3 months
  • Last seen this week
45 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

34 votes

What is the smallest Turing machine where it is unknown if it halts or not?

29 votes

Most important new papers in computational complexity

18 votes

Theoretical Computer Science vs other Sciences?

17 votes
Accepted

Parameterized complexity of inclusion of regular languages

14 votes

What notable automaton models have polynomially-decidable containment?

14 votes

Data structure whose name starts with the letter “N”?

13 votes

A simple decision problem whose decidability is not known

13 votes

Counterintuitive results for undergraduates

12 votes
Accepted

On the realisation of monoids as syntactic monoids of languages

12 votes

Are Boolean circuits 'universal'

12 votes

Caterpillar decomposition of trees

12 votes

Combinatorics of a badminton tournament

10 votes
Accepted

How to acknowledge answers of TCS in the paper?

10 votes
Accepted

Deterministic Büchi + its complement covers LTL?

10 votes

Major unsolved problems in theoretical computer science?

9 votes
Accepted

For a specific unbounded Turing machine, is its Halting problem undecidable?

9 votes

Complexity of Unknotting problems

9 votes
Accepted

Proof and computational complexity

8 votes
Accepted

Is coRE closed under concatenation?

8 votes

Are regular expressions inherently more difficult to construct than DFAs for humans?

8 votes

Constraints on sliding windows

8 votes

NP-complete decision problems on deterministic automata

7 votes
Accepted

The theoretical complexity of Go - The state of the art

7 votes
Accepted

Kleene Algebra for star-free regular expressions

7 votes

Stephen Hawking's impact on computer science

7 votes
Accepted

star height of star-free languages

7 votes
Accepted

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

6 votes

minimizing size of regular expression

6 votes
Accepted

Algebraic characterisation of star-free safety languages