We present some decidability and undecidability results for subsets of the BlenX Language, a process-calculi-based programming language developed for modelling biological processes. We show that for a core subset of the language (which considers only communication primitives) termination is decidable. Moreover, we prove that by adding either global priorities or events to this core language, we obtain Turing equivalent languages. The proof is through encodings of Random Access Machines (RAMs), a well-known Turing equivalent formalism, into our subsets of BlenX. All the encodings are shown to be correct.
Scheda prodotto non validato
I dati visualizzati non sono stati ancora sottoposti a validazione formale da parte dello Staff di IRIS, ma sono stati ugualmente trasmessi al Sito Docente Cineca (Loginmiur).
Titolo: | On the Computational Power of BlenX |
Autori: | Romanel, Alessandro; Priami, Corrado |
Autori Unitn: | |
Titolo del periodico: | THEORETICAL COMPUTER SCIENCE |
Anno di pubblicazione: | 2010 |
Numero e parte del fascicolo: | 2 |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2009.09.038 |
Handle: | http://hdl.handle.net/11572/89398 |
Appare nelle tipologie: | 03.1 Articolo su rivista (Journal article) |