Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

3 votes

How exactly does a compatible reduction relation change the $\pi$-calculus?

Interesting question. As Damiano says, while syntactically trivial to change, a π-calculus with non-blocking inputs is a different model of computing. (A very different one, and an extremely ...
user avatar
3 votes

How exactly does a compatible reduction relation change the $\pi$-calculus?

I don't know "exactly" how it changes the calculus, in the sense that I don't have a formal statement measuring the difference (and I am not aware that there exists one), but allowing ...
user avatar
10 votes
Accepted

Are there survey papers in theoretical computer science?

Yes! These survey series come to mind: Foundations and Trends in TCS (many authors put a free version on their web page) Theory of Computing Graduate Surveys SIGACT News Complexity Column (and also ...
user avatar
2 votes

Establishing competing memory limits for pushdown automata

This answer is inspired by this question. The conjecture is false, for the following reason. Consider the alphabet $\Sigma=\{0,1\}$, and the language $A=\{0^n1(0|1)^n|n>0\}$. This language is ...
user avatar
  • 7,350
2 votes

Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

(Earlier as comment). This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (https://www-igm.univ-mlv.fr/~berstel/Lothaire). For k=1 the problem is in polynomial-...
user avatar
  • 116
2 votes

Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

This is part of coding theory if you view $\ell$ as a message and $s_i$ as its components. As such, it is studied in bioinformatics as well, where the underlying alphabet could be $\{A,C,G,T\}$.
user avatar

Top 50 recent answers are included