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
0 answers
311 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 ...
paulotorrens's user avatar
4 votes
2 answers
216 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 ...
paulotorrens's user avatar
0 votes
0 answers
68 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}~~ \...
Coder's user avatar
  • 109
1 vote
1 answer
189 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?
Timothy's user avatar
  • 31
0 votes
1 answer
119 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 ...
PePe's user avatar
  • 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 ...
Ulrik Rasmussen's user avatar
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 ...
0x90's user avatar
  • 463
7 votes
1 answer
754 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$-...
Turion's user avatar
  • 616
1 vote
1 answer
205 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; (...
gym's user avatar
  • 11
7 votes
2 answers
893 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 ...
kyagrd's user avatar
  • 71
0 votes
1 answer
88 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 ...
anil keshav's user avatar
0 votes
1 answer
124 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 ...
anil keshav's user avatar
1 vote
1 answer
102 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 $\{...
foobar's user avatar
  • 111
7 votes
1 answer
189 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 ...
DaveBall aka user750378's user avatar
16 votes
1 answer
776 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 ...
DaveBall aka user750378's user avatar
4 votes
2 answers
358 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 ...
Ta Thanh Dinh's user avatar