Computer Science
Klaus Draeger
Meta user
Network profile
Summary Answers Questions Tags Badges Favorites Bounties Reputation All actions

47 Answers

Newest Activity Votes
10
DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$
Jan 22 '16 at 17:24
10
Why is the set of all regular expressions classified as context-free, instead of regular?
Nov 16 '15 at 14:41
9
Unprovable Post correspondence problem instance
Mar 27 '15 at 18:20
7
Loop variant for a while loop that occasionally doesn't decrease?
Nov 9 '15 at 0:12
7
What are the simplest examples of programs that we do not know whether they terminate?
Jul 30 '15 at 14:08
6
What does least fix point and greatest fix point mean in Safety games
May 12 '15 at 12:31
6
Can we check in polynomial time if the language of a DFA is closed against Kleene star?
Apr 28 '15 at 13:47
5
What can be said in general about a homomorphism between two regular languages?
Feb 19 '16 at 13:16
5
Term rewriting; Compute critical pairs
Sep 16 '15 at 20:06
5
Efficiently finding $k$ smallest elements of Cartesian product
Sep 7 '15 at 18:50
5
Regularity of unary languages with word lengths the sum of two resp. three squares
May 22 '15 at 14:30
5
Why is GFp -> GFq false in LTL, even though GFp and GFq are false?
Jun 29 '12 at 23:08
4
Proving the loop invariant for a simple program in Hoare logic
Mar 17 '17 at 13:34
4
CTL* query evaluation order
Mar 7 '17 at 14:25
4
What happens to uninterpreted predicates in Ackermann's reduction?
Jan 26 '16 at 13:02
4
Show that some context free languages must contain more that one non-terminal
Dec 29 '15 at 15:19
4
Construct Turing Machine which accepts the language $ww$
Jun 16 '15 at 13:47
4
Converting reality to Petri net
May 22 '15 at 12:26
4
Christofides algorithm: why must an MST have even number of odd-degree vertices?
Mar 17 '15 at 13:47
4
Getting minimum DFA for regular expression (11)*+(111)*
Jan 20 '15 at 18:42
3
DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }
Sep 29 '15 at 12:25
3
An algorithm to compute a set of states that satisfy a specific CTL formula
Apr 24 '15 at 13:57
3
Finding a Hoare logic correctness proof for a Repeat-Until loop
Mar 10 '15 at 16:38
3
Witness for the $EU(\phi_1,\phi_2)$ using BDDs
Jul 11 '12 at 15:35
2
Closure under reversal of regular languages: Proof using Automata
Mar 25 '16 at 20:38
2
How do I get and/or verify a formal Grammar for a given formal Language?
Mar 10 '16 at 18:37
2
How can there be 10 steps in the binary search algorithm for the phone book search problem?
Sep 17 '15 at 17:10
2
Is there a name for an inverted state machine?
Jul 3 '15 at 13:34
2
Show that regular languages are closed under Mix operations
May 19 '15 at 13:17
2
Why do all non-empty ω-regular languages have periodic members?
Mar 13 '15 at 12:25
1 2