Timeline for Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2013 at 13:23 | comment | added | e_noether | @frafl thanks! that's neat and simple. | |
| Mar 20, 2013 at 13:11 | answer | added | e_noether | timeline score: -1 | |
| Mar 20, 2013 at 13:07 | comment | added | frafl | @emmy: Ooops, typo: I meant of course $x_{\lfloor x/2\rfloor}$ i.e. the symbol at the $\lfloor x/2\rfloor$-th position. | |
| Mar 20, 2013 at 12:52 | comment | added | e_noether | see this link | |
| Mar 20, 2013 at 10:50 | history | edited | Raphael |
edited tags; edited tags
|
|
| Mar 20, 2013 at 8:08 | comment | added | Shaull | @emmy: How would a (nondeterministic) 1CM decide $\overline{L}$? | |
| Mar 20, 2013 at 5:38 | comment | added | e_noether | how about this language : $L = \{ a^ib^j \mid i=j \ or\ i=2j \} $ and $\bar{L} = \{a^ib^j \mid i \neq j \ and\ i\neq 2j\}$ | |
| Mar 20, 2013 at 4:20 | comment | added | e_noether | what do you mean by $x_{\lfloor|c|/2\rfloor}=a$ ? | |
| Mar 19, 2013 at 16:44 | history | tweeted | twitter.com/#!/StackCompSci/status/314054705372332033 | ||
| Mar 19, 2013 at 16:27 | comment | added | frafl | A PDA with only one kind of symbols (aside from the bottom symbol) on its stack. | |
| Mar 19, 2013 at 16:24 | comment | added | Ran G. | what is "one-counter"? | |
| Mar 19, 2013 at 16:19 | comment | added | frafl | Something like $L=\{x\in\{a,b\}^*\mid x_{\lfloor|c|/2\rfloor}=a\}$? | |
| S Mar 19, 2013 at 16:04 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
Cleaned up latex, notation and grammar.
|
| S Mar 19, 2013 at 16:04 | history | suggested | Sam Jones | CC BY-SA 3.0 |
Cleaned up latex, notation and grammar.
|
| Mar 19, 2013 at 15:56 | review | Suggested edits | |||
| Mar 19, 2013 at 16:04 | |||||
| Mar 19, 2013 at 15:44 | history | asked | e_noether | CC BY-SA 3.0 |