Timeline for Emptiness and determinization of NFAs
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2010 at 9:56 | history | edited | Niall Murphy | CC BY-SA 2.5 |
added 74 characters in body
|
| May 13, 2010 at 9:39 | history | edited | Niall Murphy | CC BY-SA 2.5 |
added 2 characters in body
|
| May 13, 2010 at 9:33 | history | edited | Niall Murphy | CC BY-SA 2.5 |
added 5 characters in body
|
| May 13, 2010 at 9:33 | comment | added | Niall Murphy | Yes sorry I meant the complement (corrected). And yes, you will need exponential sequential time and as Grigory points out, the problem PSPACE complete. So polynomial parallel time if you have an exponential number of processors. | |
| May 13, 2010 at 9:26 | history | edited | Niall Murphy | CC BY-SA 2.5 |
added 33 characters in body
|
| May 13, 2010 at 3:18 | comment | added | Joel David Hamkins | To compute the complement, don't you first have to build the equivalent DFA? This could take more than poly(n) time. | |
| May 13, 2010 at 0:18 | comment | added | JBL | Niall, what do you mean by the complement (sorry to be a pedant, but note the spelling) of an NFA? An NFA that accepts the complementary language? | |
| May 12, 2010 at 18:47 | history | answered | Niall Murphy | CC BY-SA 2.5 |