Timeline for Parameterized complexity of inclusion of regular languages
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10, 2018 at 19:53 | history | edited | Florent Foucaud | CC BY-SA 3.0 |
typo
|
| Feb 24, 2018 at 15:48 | vote | accept | Florent Foucaud | ||
| Feb 24, 2018 at 8:54 | vote | accept | Florent Foucaud | ||
| Feb 24, 2018 at 15:48 | |||||
| Feb 24, 2018 at 1:24 | comment | added | Michael Wehar | @FlorentFoucaud Thank you very much for sharing!! I think this is quite neat and Denis's answer contains some more info on the fixed case. :) | |
| Feb 23, 2018 at 12:37 | answer | added | Denis | timeline score: 17 | |
| Feb 23, 2018 at 12:05 | comment | added | Florent Foucaud | @MichaelWehar: Some coNP-complete cases are proved here, (doi.org/10.1137/080743457) but they are not for fixed languages (but for very restricted classes of languages) | |
| Feb 23, 2018 at 10:04 | comment | added | Florent Foucaud | OK, thanks! @Denis, please turn it into an answer (with a reference), and I'll accept it! | |
| Feb 22, 2018 at 23:05 | comment | added | Michael Wehar | For $E_1 = \emptyset$, it is solvable in constant time. For $E_1 = w$ for a fixed string $w$, it is solvable in polynomial time. For $E_1 = \Sigma^{*}$ it is PSPACE-complete. Does there exist an $E_1$ such that the problem is $NP$-complete? | |
| Feb 22, 2018 at 15:59 | comment | added | Denis | Btw allowing squaring makes the problem EXPSPACE-complete, the results you mentioned are without squaring. | |
| Feb 22, 2018 at 15:57 | comment | added | Denis | It remains PSPACE-complete, as language universality (i.e. E1=Sigma*) is PSPACE-complete. | |
| Feb 22, 2018 at 15:56 | history | tweeted | twitter.com/StackCSTheory/status/966703176295567360 | ||
| Feb 22, 2018 at 13:43 | history | edited | Florent Foucaud | CC BY-SA 3.0 |
typo
|
| Feb 22, 2018 at 11:54 | history | edited | Florent Foucaud | CC BY-SA 3.0 |
def reg exp
|
| Feb 22, 2018 at 10:43 | history | asked | Florent Foucaud | CC BY-SA 3.0 |