sdcvvc's user avatar
sdcvvc's user avatar
sdcvvc's user avatar
sdcvvc
  • Member for 12 years, 1 month
  • Last seen more than a week ago
21 votes

Operations under which the class of undecidable languages isn't closed

15 votes

Examples of context-free languages with a non-context-free complements

13 votes
Accepted

Is it possible for a language and its complement to both be unrecognizable?

10 votes

Finding at least two paths of same length in a directed graph

10 votes
Accepted

Which non-regular languages are in $AC^0$?

10 votes
Accepted

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

8 votes
Accepted

Is this language Context-Free?

8 votes

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

7 votes

If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

7 votes

Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?

7 votes

Infinite languages and undecidable languages

7 votes
Accepted

Are regular and context free languages closed against making them prefix-free?

6 votes

Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

6 votes
Accepted

Prove Language Is Union of Fninitely Many Arithmetic Progressions

6 votes
Accepted

Is a kind of reverse Kleene star of a context-free language context-free?

6 votes
Accepted

Language of the graph of an affine function

6 votes

Does $NP^{NP}=NP$?

6 votes
Accepted

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

6 votes

P vs. NP and Godel's Theorems

5 votes
Accepted

Is this language regular?

5 votes
Accepted

Are Turing-recognizable languages closed under intersection?

5 votes
Accepted

BPP upper bound

5 votes
Accepted

Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

5 votes
Accepted

Is DSPACE properly contained in NSPACE?

4 votes
Accepted

Why is the difference of two NP-complete languages not in NP?

4 votes

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

4 votes
Accepted

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

4 votes

How are all NP Complete problems similar?

4 votes

Why doesn't the recursion theorem prove there is an undecidable finite set?

4 votes
Accepted

Is Half - Palindrome subset of a context-free language context-free?