Klaus Draeger's user avatar
Klaus Draeger's user avatar
Klaus Draeger's user avatar
Klaus Draeger
  • Member for 10 years, 5 months
  • Last seen more than a month ago
10 votes
Accepted

Why is the set of all regular expressions classified as context-free, instead of regular?

10 votes

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

9 votes

Unprovable Post correspondence problem instance

9 votes
Accepted

What does least fix point and greatest fix point mean in Safety games

7 votes

Loop variant for a while loop that occasionally doesn't decrease?

7 votes

What are the simplest examples of programs that we do not know whether they terminate?

6 votes
Accepted

Can we check in polynomial time if the language of a DFA is closed against Kleene star?

6 votes
Accepted

Term rewriting; Compute critical pairs

5 votes

Regularity of unary languages with word lengths the sum of two resp. three squares

5 votes
Accepted

Construct Turing Machine which accepts the language $ww$

5 votes
Accepted

Efficiently finding $k$ smallest elements of Cartesian product

5 votes

Why is GFp -> GFq false in LTL, even though GFp and GFq are false?

5 votes

What can be said in general about a homomorphism between two regular languages?

4 votes
Accepted

What happens to uninterpreted predicates in Ackermann's reduction?

4 votes

Show that some context free languages must contain more that one non-terminal

4 votes
Accepted

CTL* query evaluation order

4 votes
Accepted

Proving the loop invariant for a simple program in Hoare logic

4 votes
Accepted

Getting minimum DFA for regular expression (11)*+(111)*

4 votes

Finding a Hoare logic correctness proof for a Repeat-Until loop

4 votes
Accepted

Christofides algorithm: why must an MST have even number of odd-degree vertices?

4 votes

DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }

4 votes

Converting reality to Petri net

3 votes

Show that regular languages are closed under Mix operations

3 votes

An algorithm to compute a set of states that satisfy a specific CTL formula

3 votes
Accepted

Witness for the $EU(\phi_1,\phi_2)$ using BDDs

2 votes

Why is the A* search heuristic optimal even if it underestimates costs?

2 votes

Why do all non-empty ω-regular languages have periodic members?

2 votes

Is there a name for an inverted state machine?

2 votes

Reduction from 3SAT

2 votes

How can there be 10 steps in the binary search algorithm for the phone book search problem?