We study type systems for termination in the $pi$-calculus from the point of view of type inference. We analyse four systems by Deng and Sangiorgi. We show that inference can be done in polynomial time for two of these, but that this is not the case for the two most expressive systems. To remedy this, we study two modifications of these type systems that allow us to recover a polynomial type inference.
On the Complexity of Termination Inference for Processes / R. Demangeon; D. l Hirschkoff; N. Kobayashi; D. Sangiorgi. - STAMPA. - 4912:(2008), pp. 140-155. (Intervento presentato al convegno Trustworthy Global Computing (TGC 2007) tenutosi a Sophia-Antipolis, France nel November 5-6, 2007).
On the Complexity of Termination Inference for Processes
SANGIORGI, DAVIDE
2008
Abstract
We study type systems for termination in the $pi$-calculus from the point of view of type inference. We analyse four systems by Deng and Sangiorgi. We show that inference can be done in polynomial time for two of these, but that this is not the case for the two most expressive systems. To remedy this, we study two modifications of these type systems that allow us to recover a polynomial type inference.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
