user avatar
user avatar
user avatar
user6530
  • Member for 2 years, 2 months
  • Last seen this week
9 votes

Proof that no O(n) multiplication algorithm exists

7 votes
Accepted

Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

5 votes
Accepted

Proof that L^2 is regular => L is regular

4 votes

CFG that generates $1^*$ is decidable

4 votes

Turing machine for $0^{3^k} 1^{p}$

3 votes
Accepted

Proof of $f(n) + ο(f(n)) = \Theta(f(n))$

3 votes
Accepted

Is X+Y sorting problem still an open problem?

2 votes

Time complexity of $L=\{a^nb^n | n \ge 1\}$

2 votes

Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

2 votes
Accepted

Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

1 vote
Accepted

Recurrence relations and induction: guessing the right bound

1 vote
Accepted

The intersection of 2 CFL

1 vote
Accepted

How can I prove that LTL formula is valid?

1 vote

Comparisons of functions, their big-oh and their implications

1 vote

How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?

1 vote

Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

1 vote

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

0 votes
Accepted

Grammar for $\{ (n_a(w) - n_b(w)) mod\ 3 = 2 \} $

0 votes

Difference between a regular and a non-regular language

0 votes

Description logics with decision problems within NP