user avatar
user avatar
user avatar
Klaus Draeger
  • Member for 11 years, 2 months
  • Last seen this week
25 votes
Accepted

Why is non-determinism (Push-down automata) necessary?

14 votes
Accepted

Explicit mu-recursive expression for Ackerman function

13 votes
Accepted

Is the Set of all Primitive Words a Prime Language?

12 votes
Accepted

Isomorphic graph embeddings in the Euclidean Space

11 votes
Accepted

Measurable language which is not $\omega$-regular

9 votes
Accepted

CTL and LTL logic difference

9 votes

Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT

8 votes

Constant in Komlos conjecture

8 votes
Accepted

Directed multigraphs as minimal automata

7 votes
Accepted

The number of states of local automata

7 votes
Accepted

What kind of language is needed to recognize an ordered list? [multihead automata, apparently]

6 votes
Accepted

Alternating automata

6 votes

Which kind of grammar is the following?

5 votes
Accepted

A special case of the boolean multivariate quadratic polynomial problem

5 votes

Complexity of digraph homomorphism to an oriented cycle

4 votes
Accepted

Proof that the theory of rationals is convex

4 votes
Accepted

Independent iterations in Las Vegas algorithms

4 votes
Accepted

Relation between Kleene star, union and difference in relation algebra

4 votes
Accepted

What is a probabilistic function and where can I learn more about them?

4 votes
Accepted

Decidability of membership in the fixed point of a rational relation

4 votes
Accepted

Existence of certain graph gadget related to coloring odd hole free graph

3 votes
Accepted

Expressiveness of Büchi vs CTL(*)

3 votes
Accepted

Kripke model and LTL vs CTL formulae interpretation

3 votes

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

3 votes
Accepted

Minmax vs Maxmin

3 votes

Assignment of values for a set

3 votes
Accepted

How to constrain a finite automaton (NFA and DFA) to a tree?

2 votes
Accepted

How to XOR automata?

1 vote

Polytopes convex hull

1 vote

representing code path as graph walks.. a provable graph walk?