Versari, Cristian
(2009)
A core calculus for the analysis and implementation of biologically inspired languages, [Dissertation thesis], Alma Mater Studiorum Università di Bologna.
Dottorato di ricerca in
Informatica, 21 Ciclo. DOI 10.6092/unibo/amsdottorato/1442.
Documenti full-text disponibili:
Abstract
The application of Concurrency Theory to Systems Biology
is in its earliest stage of progress. The metaphor of
cells as computing systems by Regev and Shapiro
opened the employment of concurrent languages for the
modelling of biological systems. Their peculiar
characteristics led to the design of many bio-inspired
formalisms which achieve higher faithfulness and
speciﬁcity.
In this thesis we present pi@, an extremely simple and
conservative extension of the pi-calculus representing
a keystone in this respect, thanks to its expressiveness
capabilities. The pi@ calculus is obtained by the addition
of polyadic synchronisation and priority to the
pi-calculus, in order to achieve compartment semantics and
atomicity of complex operations respectively.
In its direct application to biological modelling, the
stochastic variant of the calculus, Spi@, is shown able to
model consistently several phenomena such as formation
of molecular complexes, hierarchical subdivision of the
system into compartments, inter-compartment reactions,
dynamic reorganisation of compartment structure consistent
with volume variation.
The pivotal role of pi@ is evidenced by its capability
of encoding in a compositional way several bio-inspired
formalisms, so that it represents the optimal core of
a framework for the analysis and implementation of
bio-inspired languages. In this respect, the encodings of
BioAmbients, Brane Calculi and a variant of P
Systems in pi@ are formalised. The conciseness of their
translation in pi@ allows their indirect comparison by
means of their encodings. Furthermore it provides a
ready-to-run implementation of minimal effort whose correctness is granted by the correctness of the respective
encoding functions.
Further important results of general validity are stated
on the expressive power of priority. Several impossibility
results are described, which clearly state the superior
expressiveness of prioritised languages and the problems
arising in the attempt of providing their parallel
implementation. To this aim, a new setting in distributed
computing (the last man standing problem) is singled out
and exploited to prove the impossibility of providing a
purely parallel implementation of priority by means
of point-to-point or broadcast communication.
Abstract
The application of Concurrency Theory to Systems Biology
is in its earliest stage of progress. The metaphor of
cells as computing systems by Regev and Shapiro
opened the employment of concurrent languages for the
modelling of biological systems. Their peculiar
characteristics led to the design of many bio-inspired
formalisms which achieve higher faithfulness and
speciﬁcity.
In this thesis we present pi@, an extremely simple and
conservative extension of the pi-calculus representing
a keystone in this respect, thanks to its expressiveness
capabilities. The pi@ calculus is obtained by the addition
of polyadic synchronisation and priority to the
pi-calculus, in order to achieve compartment semantics and
atomicity of complex operations respectively.
In its direct application to biological modelling, the
stochastic variant of the calculus, Spi@, is shown able to
model consistently several phenomena such as formation
of molecular complexes, hierarchical subdivision of the
system into compartments, inter-compartment reactions,
dynamic reorganisation of compartment structure consistent
with volume variation.
The pivotal role of pi@ is evidenced by its capability
of encoding in a compositional way several bio-inspired
formalisms, so that it represents the optimal core of
a framework for the analysis and implementation of
bio-inspired languages. In this respect, the encodings of
BioAmbients, Brane Calculi and a variant of P
Systems in pi@ are formalised. The conciseness of their
translation in pi@ allows their indirect comparison by
means of their encodings. Furthermore it provides a
ready-to-run implementation of minimal effort whose correctness is granted by the correctness of the respective
encoding functions.
Further important results of general validity are stated
on the expressive power of priority. Several impossibility
results are described, which clearly state the superior
expressiveness of prioritised languages and the problems
arising in the attempt of providing their parallel
implementation. To this aim, a new setting in distributed
computing (the last man standing problem) is singled out
and exploited to prove the impossibility of providing a
purely parallel implementation of priority by means
of point-to-point or broadcast communication.
Tipologia del documento
Tesi di dottorato
Autore
Versari, Cristian
Supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
21
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
concurrency, process calculi, pi-calculus, priority, stochastic, simulation
URN:NBN
DOI
10.6092/unibo/amsdottorato/1442
Data di discussione
20 Aprile 2009
URI
Altri metadati
Tipologia del documento
Tesi di dottorato
Autore
Versari, Cristian
Supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
21
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
concurrency, process calculi, pi-calculus, priority, stochastic, simulation
URN:NBN
DOI
10.6092/unibo/amsdottorato/1442
Data di discussione
20 Aprile 2009
URI
Statistica sui download
Gestione del documento: