We consider nondeterministic and probabilistic termination problems in a process algebra that is equivalent to basic chemistry. We show that the existence of a terminating computation is decidable, but that termination with any probability strictly greater than zero is undecidable. Moreover, we show that the fairness intrinsic in stochastic computations implies that termination of all computation paths is undecidable, while it is decidable in a nondeterministic framework.
Termination Problems in Chemical Kinetics / G. Zavattaro; L. Cardelli. - STAMPA. - (2008), pp. 477-491. (Intervento presentato al convegno CONCUR 2008 - Concurrency Theory, 19th International Conference tenutosi a Toronto, Canada nel August 19-22, 2008).
Termination Problems in Chemical Kinetics
ZAVATTARO, GIANLUIGI;
2008
Abstract
We consider nondeterministic and probabilistic termination problems in a process algebra that is equivalent to basic chemistry. We show that the existence of a terminating computation is decidable, but that termination with any probability strictly greater than zero is undecidable. Moreover, we show that the fairness intrinsic in stochastic computations implies that termination of all computation paths is undecidable, while it is decidable in a nondeterministic framework.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
