Questions tagged [pi-calculus]

The pi-calculus is a formal model of concurrent computation that works by creating and exchanging names (connection points).

Filter by
Sorted by
Tagged with
4 votes
2 answers
159 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 ...
0 votes
0 answers
60 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
178 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
96 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
96 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 ...
11 votes
2 answers
417 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
661 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
175 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
837 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
80 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 ...
0 votes
1 answer
115 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 ...
1 vote
1 answer
96 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
177 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
735 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 ...