Shaull's user avatar
Shaull's user avatar
Shaull's user avatar
Shaull
  • Member for 12 years, 3 months
  • Last seen this week
27 votes

Hardest known natural problem in P?

18 votes

A simple decision problem whose decidability is not known

17 votes

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

13 votes

Determinising unambiguous automata without exponential blowup

12 votes

Is it possible to test if a computable number is rational or integer?

12 votes
Accepted

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

11 votes
Accepted

What is the motivation behind defining Deterministic Looping Automata?

10 votes
Accepted

Finite-State Automata over a real-valued alphabet

9 votes
Accepted

Is SAT with two "opposite" solutions NP-hard?

8 votes

Do past time LTL and future time LTL have the same expressiveness?

8 votes

Applications of Game theory in computer science?

8 votes
Accepted

Efficient algorithm for finding directed cycle with smallest average weight

8 votes

Is there a well-defined division operation on finite automata?

8 votes

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

8 votes

Relationship between the transition monoid of an automaton and its adjacency matrix

7 votes

Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

7 votes

Applications of algebraic geometry in type theory/programming language theory

6 votes

Are there any intersections between Theory A and Theory B?

6 votes
Accepted

Is there any equation-based method for transforming Büchi-automata to omega-regular language?

6 votes

List of complexity classes closed under complement

6 votes

Hamiltonian Cycle as an integer linear programming problem

6 votes

Finite state transducer that sorts

6 votes

Why is linearizability a safety property and why are safety properties closed sets?

6 votes
Accepted

Number of accepting path of a non deterministic automaton

5 votes

Some problems about arrow's theorem and social choice

5 votes
Accepted

in SAT resolution proofs, are all DAGs possible?

5 votes
Accepted

Finite Automata with succinct representation of chains of states

5 votes
Accepted

Deterministic Parity Automata require unbounded index

5 votes

What is the space complexity of CTL model checking?

5 votes

Under what models do we know linear time sorting?