Nov
4
awarded Nice Question
Nov
4
comment Average time to solve maze through backtracking
Try to think how many times you will backtrack in average
Nov
4
comment Average time to solve maze through backtracking
@GabrielRatener "The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution." The algorithm could have found the solution in the first branch it visits without ever having to backtrack. You need to look at average case, not worst case
Nov
4
answered Average time to solve maze through backtracking
Oct
14
awarded Commentator
Oct
10
comment Proving NP-hardness of strange graph partition problem
Try reduction to the subset-sum problem?
Oct
10
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
Thanks for the hint, I figured it out.
Oct
9
comment If both the concatenation of two languages and the second "half" are regular, is the first too?
for your concrete question, try drawing down the DFA and see what you can find.
Oct
9
awarded Supporter
Oct
9
awarded Teacher
Oct
9
revised If both the concatenation of two languages and the second "half" are regular, is the first too?
added missing cdot
Oct
9
answered If both the concatenation of two languages and the second "half" are regular, is the first too?
Oct
7
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
@DavidEisenstat taking $B = a^* b^p$ where p is prime, then $A\subset B \subset C$ is satisfied but B is not regular. Does that work?
Oct
7
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
@DavidEisenstat e.g. A=a* b and C=a* b* then A-C = a* b b*, so not all sets B are regular?
Oct
7
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
@DavidEisenstat I don't really get the above, can you elaborate a bit?
Oct
7
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
@KlausDraeger thanks, so I took another attempt to 2. but still can't find a clue for 1.
Oct
7
revised Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
added 154 characters in body
Oct
6
comment Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
@KlausDraeger does $MinBadPref(P_{safe})=\{ab, aabb\}$ work?
Oct
6
revised Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
added 2 characters in body
Oct
6
awarded Editor
1 2 3 4 5