# 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
Filter by
Sorted by
Tagged with
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
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
64 views

• 13
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 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
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
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
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
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
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