Timeline for Are context-free languages with context-free complements necessarily deterministic context-free?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 29, 2012 at 16:42 | comment | added | Nick Loughlin | Yes, it seems from discussion I'd put a typo in my original formulation; thanks - it completely passed me by. It was probably an artefact from my rewriting the question first time around. | |
| Feb 22, 2012 at 21:57 | comment | added | Benjamin Steinberg | @Nick, I rewrote the question to match your comment above as djlewis2 makes a good point. Please re-edit if this was not your intent. | |
| Feb 22, 2012 at 21:55 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
Changed the question to agree with the reformulation in the comments; deleted 6 characters in body
|
| Feb 22, 2012 at 16:49 | answer | added | David Lewis | timeline score: 3 | |
| Feb 22, 2012 at 16:03 | vote | accept | Nick Loughlin | ||
| Feb 22, 2012 at 14:35 | answer | added | Benjamin Steinberg | timeline score: 6 | |
| Feb 22, 2012 at 1:55 | comment | added | Kaveh | In other words, you are asking if $CFL \cap coCFL \subseteq DCFL$ or not. Interesting question. Couldn't find the answer in Hopcroft and Ullman. | |
| Feb 21, 2012 at 22:53 | comment | added | Benjamin Steinberg | Ok no longer a duplicate. | |
| Feb 21, 2012 at 22:50 | comment | added | Nick Loughlin | Perhaps you missed my last edit - I removed that part of the question. To clarify, my original question contained the above, as well as a "dual" question concerning the closure of the set of context-free languages w.r.t. finitary Boolean operations. In this question, I'm not looking for the closure of the class of context-free languages with respect to complements, but merely to know if the proper sub-class of CF languages which have CF complements is in fact the class DCF of deterministic CF languages. | |
| Feb 21, 2012 at 22:27 | comment | added | Benjamin Steinberg | This is essentially an exact duplicate of mathoverflow.net/questions/51657/… which has an answer. | |
| Feb 21, 2012 at 22:06 | history | edited | Nick Loughlin | CC BY-SA 3.0 |
Tidied up a bit, and made question's title more explicit; removed second sub-question.
|
| Feb 21, 2012 at 21:46 | history | asked | Nick Loughlin | CC BY-SA 3.0 |