On the computational power of BlenX |
| |
Authors: | Alessandro Romanel Corrado Priami |
| |
Affiliation: | CoSBi, I-38123 Povo, TN, Italy DISI, Università di Trento, I-38123 Povo, TN, Italy |
| |
Abstract: | 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. |
| |
Keywords: | Process calculi Random Access Machines Turing equivalence Termination decidability Systems biology |
本文献已被 ScienceDirect 等数据库收录! |
|