Questions tagged [pi-calculus]
The pi-calculus is a formal model of concurrent computation that works by creating and exchanging names (connection points).
16
questions
4
votes
0
answers
309
views
How to prove that a language that allows infinite loops is still not Turing-complete?
CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
- 377
4
votes
2
answers
214
views
How exactly does a compatible reduction relation change the $\pi$-calculus?
The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial:
It is ...
- 377
0
votes
0
answers
64
views
A fundamental question about the proof by induction in session types
I have a question about proof by induction in the domain of session types. Let's assume we have the following lemma:
$$
\text{Let}~ \Gamma \vdash P : T. ~~\text{If } P = \mu X.
Q ~~\text{then}~~ \...
- 109
1
vote
1
answer
186
views
Can you embed a Turing Machine into the Pi calculus with just one replication operator?
See title. If it is not universal, then how is the power of the pi calculus with this restriction characterized?
- 31
0
votes
1
answer
107
views
Pi-calculus (or session types) - proof for weakening lemma
I'm writing a thesis about session types and am currently writing a section concerning type soundness for the system. I started to proof weakening lemma, which states, that
$$
\text{If } \Gamma \vdash ...
- 13
3
votes
1
answer
98
views
Reference request: pi-calculus with simultaneous events
I am interested in using the $\pi$-calculus as a basis for modeling workflows, and came up with an extension that proved useful in my modeling, namely the ability to specify that two or more channel ...
- 420
11
votes
2
answers
420
views
Are there protein-based computational models?
Is there a framework/formalism that defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian?
Edit 2020 (related models/ideas based on DNA):
DNA ...
- 463
7
votes
1
answer
740
views
Determinism and pi-calculus
Milner embedded $\lambda$-calculus into $\pi$-calculus, showing that the $\pi$-calculus is capable of Turing-complete, deterministic calculation. Since parallel compositions of processes in the $\pi$-...
- 584
1
vote
1
answer
197
views
Encoding an infinitely looping process with state in the pi-calculus
Suppose I have a process that informally does this
int count = 0
forever do
receive x on some channel c;
count += x;
output count on some channel d;
(...
- 11
7
votes
2
answers
884
views
Is scope extrusion necessary in the Pi-calculus?
What is the real benefit of scope extrusion in the Pi-calculus? I read that it adds more flexiblity to the overly restrictive prior process algebra where the scope of a newly created channel was ...
- 71
0
votes
1
answer
86
views
Sequential execution in π-Calculus
I am just starting into process algebra (π-Calculus) for formally defining the operational semantics of a system. One common statement that I come across that π-Calculus is used for Concurrent and ...
- 111
0
votes
1
answer
123
views
Semantic equivalence using a model of computation of two languages
I am relatively new to the field of language semantics. However i had a question pertaining to language equivalence (i did read about the question, however my approach is slightly different and hence ...
- 111
1
vote
1
answer
101
views
Scope of active substitutions in the applied $\pi$-calculus
As I have seen a few questions on calculi floating around, I figure this is the right place to ask. Suppose we have an extended process $P \equiv \nu \tilde{n}.\left( \{M/x\} \mid N \right)$ where $\{...
- 111
7
votes
1
answer
188
views
Can choice or sequential execution be expressed with other basic operators of the pi calculus?
There are several definitions of what basic operators constitute the pi calculus (see papers from R. Milner, B.Pierce, J.Wing).
The common basic operators ($C$) are:
the parallel composition
...
16
votes
1
answer
765
views
(How) can you model broadcasts in the pi-calculus?
Can you model reliable broadcasts in the pi-calculus?
If so: How?
If not: Are there any similar process algebras where you can?
What I have tried:
If sender $S$ wants to send a message $y$ to ...
4
votes
2
answers
357
views
Parametric equation in pi-calculus
This is the first time I ask a question on cstheory, so I am very sorry for my english.
I have a (maybe very trivial) problem when trying to find a well-form representation for a root of a recursive ...
- 144