New answers tagged reference-request
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 ...
- 10.3k
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 ...
- 4,823
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 ...
- 35.6k
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 ...
- 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-...
- 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\}$.
- 4,400
Top 50 recent answers are included