Maczinga's user avatar
Maczinga's user avatar
Maczinga's user avatar
Maczinga
  • Member for 7 years
  • Last seen more than 1 year ago
4 votes
Accepted

Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$

3 votes
Accepted

Lemma 2 in Knuth's "Notes on Open Addressing"

3 votes
Accepted

How to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and set operations?

3 votes
Accepted

Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable?

2 votes
Accepted

Show that if Automata $A$ recognize language $L$, there also exists an automata $A′$ that recognize $Double(L)$

2 votes
Accepted

In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?

2 votes

Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

2 votes
Accepted

Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

1 vote

Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?

1 vote

Complexity calculation of a recursive function with additional O(n) complexity

1 vote

Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable?

1 vote

What is the simplification of AB + BC + (~B)C?

0 votes

Give a $3$-state DFA for $(01 \cup 1)^∗$

0 votes

Closure under the Star Operation

0 votes

Big theta of $ \lceil{log(n+1)}\rceil $