Nuova ricerca

Matteo CAVALIERE

Professore Associato
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

Home | Curriculum(pdf) | Didattica |


Pubblicazioni

2024 - Cooperation and social organization depend on weighing private and public reputations [Articolo su rivista]
Cavaliere, Matteo; Yang, Guoli; De Dreu, Carsten K. W.; Gross, Jörg
abstract

: To avoid exploitation by defectors, people can use past experiences with others when deciding to cooperate or not ('private information'). Alternatively, people can derive others' reputation from 'public' information provided by individuals within the social network. However, public information may be aligned or misaligned with one's own private experiences and different individuals, such as 'friends' and 'enemies', may have different opinions about the reputation of others. Using evolutionary agent-based simulations, we examine how cooperation and social organization is shaped when agents (1) prioritize private or public information about others' reputation, and (2) integrate others' opinions using a friend-focused or a friend-and-enemy focused heuristic (relying on reputation information from only friends or also enemies, respectively). When agents prioritize public information and rely on friend-and-enemy heuristics, we observe polarization cycles marked by high cooperation, invasion by defectors, and subsequent population fragmentation. Prioritizing private information diminishes polarization and defector invasions, but also results in limited cooperation. Only when using friend-focused heuristics and following past experiences or the recommendation of friends create prosperous and stable populations based on cooperation. These results show how combining one's own experiences and the opinions of friends can lead to stable and large-scale cooperation and highlight the important role of following the advice of friends in the evolution of group cooperation.

2024 - Information-driven cooperation on adaptive cyber-physical systems [Articolo su rivista]
Yang, Guoli; Wu, Yu'E; Cavaliere, Matteo
abstract

2022 - Compositional modelling of immune response and virus transmission dynamics [Articolo su rivista]
Waites, W; Cavaliere, M; Danos, V; Datta, R; Eggo, R M; Hallett, T B; Manheim, D; Panovska-Griffiths, J; Russell, T W; Zarnitsyna, V I
abstract

Transmission models for infectious diseases are typically formulated in terms of dynamics between individuals or groups with processes such as disease progression or recovery for each individual captured phenomenologically, without reference to underlying biological processes. Furthermore, the construction of these models is often monolithic: they do not allow one to readily modify the processes involved or include the new ones, or to combine models at different scales. We show how to construct a simple model of immune response to a respiratory virus and a model of transmission using an easily modifiable set of rules allowing further refining and merging the two models together. The immune response model reproduces the expected response curve of PCR testing for COVID-19 and implies a long-tailed distribution of infectiousness reflective of individual heterogeneity. This immune response model, when combined with a transmission model, reproduces the previously reported shift in the population distribution of viral loads along an epidemic trajectory.This article is part of the theme issue 'Technical challenges of modelling real-life epidemics and examples of overcoming these'.

2022 - Cooperation dynamics in dynamical networks with history-based decisions [Articolo su rivista]
Miles, A. L.; Cavaliere, M.
abstract

In many aspects of life on earth, individuals may engage in cooperation with others to contribute towards a goal they may share, which can also ensure self-preservation. In evolutionary game theory, the act of cooperation can be considered as an altruistic act of an individual producing some form of benefit or commodity that can be utilised by others they are associated with, which comes at some personal cost. Under certain conditions, individuals make use of information that they are able to perceive within a group in order to aid with their choices for who they should associate themselves within these cooperative scenarios. However, cooperative individuals can be taken advantage of by opportunistic defectors, which can cause significant disruption to the population. We study a model where the decision to establish interactions with potential partners is based on the opportune integration of the individual’s private ability to perceive the intentions of others (private information) and the observation of the population, information that is available to every individual (public information). When public information is restricted to a potential partners current connection count, the population becomes highly cooperative but rather unstable with frequent invasions of cheaters and recoveries of cooperation. However, when public information considers the previous decisions of the individuals (accepted / rejected connections) the population is slightly less cooperative but more stable. Generally, we find that allowing the observation of previous decisions, as part of the available public information, can often lead to more stable but fragmented and less prosperous networks. Our results highlight that the ability to observe previous individual decisions, balanced by individuals personal information, represents an important aspect of the interplay between individual decision-making and the resilience of cooperation in structured populations.

2022 - Evolutionary game theory in a cell: A membrane computing approach [Articolo su rivista]
Garcia-Victoria, P; Cavaliere, M; Gutierrez-Naranjo, Ma; Cardenas-Montes, M
abstract

Evolutionary Game Theory studies the spreading of strategies in populations. An important question of the area concerns the possibility that certain population structures can facilitate the spreading of more cooperative behaviours associated to the sustainability and resilience of many different systems ranging from ecological to socio-economic systems. In this paper, we propose a novel approach to study the spreading of behaviours in structured populations by combining Evolutionary Game Theory and membrane computing. We show that there is a general way to encode Evolutionary Game Theory into membrane computing, leading to a novel computational framework which can be used to study, analyze and simulate the spreading of behaviours in structured populations organized in communicating compartments. The proposed approach allows to extend the works on membrane systems, population and ecological dynamics, and, at the same time, suggests a novel bioinspired framework, based on formal languages theory, to investigate the dynamics of evolving structured populations. (C) 2022 Elsevier Inc. All rights reserved.

2021 - Automatic design of spiking neural p systems based on genetic algorithms [Articolo su rivista]
Dong, J.; Stachowicz, M.; Zhang, G.; Cavaliere, M.; Rong, H.; Paul, P.
abstract

At present, all known spiking neural P systems (SN P systems) are established by manual design rather than automatic design. The method of manual design poses two problems: consuming a lot of computing time and making unnecessary mistakes. In this paper, we propose an automatic design approach for SN P systems by genetic algorithms. More specifically, the regular expressions are changed to achieve the automatic design of SN P systems. In this method, the number of neurons in system, the synapse connections between neurons, the number of rules within each neuron and the number of spikes within each neuron are known. A population of SN P systems is created by generating randomly accepted regular expressions. A genetic algorithm is applied to evolve a population of SN P systems toward a successful SN P systems with high accuracy and sensitivity for carrying out specific task. An effective fitness function is designed to evaluate each candidate SN P system. In addition, the elitism, crossover and mutation are also designed. Finally, experimental results show that the approach can successfully accomplish the automatic design of SN P systems for generating natural numbers and even natural numbers by using the.NET framework.

2021 - Computational modelling unveils how epiblast remodelling and positioning rely on trophectoderm morphogenesis during mouse implantation [Articolo su rivista]
Dokmegang, Joel; Yap, Moi Hoon; Han, Liangxiu; Cavaliere, Matteo; Doursat, René
abstract

Understanding the processes by which the mammalian embryo implants in the maternal uterus is a long-standing challenge in embryology. New insights into this morphogenetic event could be of great importance in helping, for example, to reduce human infertility. During implantation the blastocyst, composed of epiblast, trophectoderm and primitive endoderm, undergoes significant remodelling from an oval ball to an egg cylinder. A main feature of this transformation is symmetry breaking and reshaping of the epiblast into a "cup". Based on previous studies, we hypothesise that this event is the result of mechanical constraints originating from the trophectoderm, which is also significantly transformed during this process. In order to investigate this hypothesis we propose MG# (MechanoGenetic Sharp), an original computational model of biomechanics able to reproduce key cell shape changes and tissue level behaviours in silico. With this model, we simulate epiblast and trophectoderm morphogenesis during implantation. First, our results uphold experimental findings that repulsion at the apical surface of the epiblast is essential to drive lumenogenesis. Then, we provide new theoretical evidence that trophectoderm morphogenesis indeed can dictate the cup shape of the epiblast and fosters its movement towards the uterine tissue. Our results offer novel mechanical insights into mouse peri-implantation and highlight the usefulness of agent-based modelling methods in the study of embryogenesis.

2021 - Opinion diversity and the resilience of cooperation in dynamical networks [Articolo su rivista]
Miles, A. L.; Cavaliere, M.
abstract

Across various scenarios, individuals cooperate with others to contribute towards a shared goal and ensure self-preservation. In game theory, the act of cooperation is considered as an individual producing some form of benefit to be utilised by others, under the expectation others will return the favour. In several scenarios, individuals make use of their own information to aid with their decision about who to connect and cooperate with. However, the choice of cooperation can be taken advantage of by opportunistic defectors, which can lead to significant disruption. This paper investigates how the diversity of opinion can contribute to the structure and mechanics of a dynamical network model and to the resilience of cooperation, by utilising a computational model where individuals make use of both public and private information to implement their decision. Our results show that increasing diversity leads to more stable, less connected and less prosperous networks coupled to more frequent, but shallower information cascades. Our work generally shows that the outcome of the conflict between cooperators and cheaters strongly depends on the interplay between population structure, individual decision making and individual opinions.

2021 - Quantification of cell behaviors and computational modeling show that cell directional behaviors drive zebrafish pectoral fin morphogenesis [Articolo su rivista]
Dokmegang, Joel; Nguyen, Hanh; Kardash, Elena; Savy, Thierry; Cavaliere, Matteo; Peyriéras, Nadine; Doursat, René
abstract

Motivation: Understanding the mechanisms by which the zebrafish pectoral fin develops is expected to produce insights on how vertebrate limbs grow from a 2D cell layer to a 3D structure. Two mechanisms have been proposed to drive limb morphogenesis in tetrapods: a growth-based morphogenesis with a higher proliferation rate at the distal tip of the limb bud than at the proximal side, and directed cell behaviors that include elongation, division and migration in a non-random manner. Based on quantitative experimental biological data at the level of individual cells in the whole developing organ, we test the conditions for the dynamics of pectoral fin early morphogenesis.Results: We found that during the development of the zebrafish pectoral fin, cells have a preferential elongation axis that gradually aligns along the proximodistal (PD) axis of the organ. Based on these quantitative observations, we build a center-based cell model enhanced with a polarity term and cell proliferation to simulate fin growth. Our simulations resulted in 3D fins similar in shape to the observed ones, suggesting that the existence of a preferential axis of cell polarization is essential to drive fin morphogenesis in zebrafish, as observed in the development of limbs in the mouse, but distal tip-based expansion is not.

2021 - Rule-based epidemic models [Articolo su rivista]
Waites, W.; Cavaliere, M.; Manheim, D.; Panovska-Griffiths, J.; Danos, V.
abstract

Rule-based models generalise reaction-based models with reagents that have internal state and may be bound together to form complexes, as in chemistry. An important class of system that would be intractable if expressed as reactions or ordinary differential equations can be efficiently simulated when expressed as rules. In this paper we demonstrate the utility of the rule-based approach for epidemiological modelling presenting a suite of seven models illustrating the spread of infectious disease under different scenarios: wearing masks, infection via fomites and prevention by hand-washing, the concept of vector-borne diseases, testing and contact tracing interventions, disease propagation within motif-structured populations with shared environments such as schools, and superspreading events. Rule-based models allow to combine transparent modelling approach with scalability and compositionality and therefore can facilitate the study of aspects of infectious disease propagation in a richer context than would otherwise be feasible.

2021 - Strategically positioning cooperators can facilitate the contagion of cooperation [Articolo su rivista]
Yang, Guoli; Cavaliere, Matteo; Zhu, Cheng; Perc, Matjaž
abstract

The spreading of cooperation in structured population is a challenging problem which can be observed at different scales of social and biological organization. Generally, the problem is studied by evaluating the chances that few initial invading cooperators, randomly appearing in a network, can lead to the spreading of cooperation. In this paper we demonstrate that in many scenarios some cooperators are more influential than others and their initial positions can facilitate the spreading of cooperation. We investigate six different ways to add initial cooperators in a network of cheaters, based on different network-based measurements. Our research reveals that strategically positioning the initial cooperators in a population of cheaters allows to decrease the number of initial cooperators necessary to successfully seed cooperation. The strategic positioning of initial cooperators can also help to shorten the time necessary for the restoration of cooperation. The optimal ways in which the initial cooperators should be placed is, however, non-trivial in that it depends on the degree of competition, the underlying game, and the network structure. Overall, our results show that, in structured populations, few cooperators, well positioned in strategically chosen places, can spread cooperation faster and easier than a large number of cooperators that are placed badly.

2020 - Information Cascades and the Collapse of Cooperation [Articolo su rivista]
Yang, G.; Csikasz-Nagy, A.; Waites, W.; Xiao, G.; Cavaliere, M.
abstract

In various types of structured communities newcomers choose their interaction partners by selecting a role-model and copying their social networks. Participants in these networks may be cooperators who contribute to the prosperity of the community, or cheaters who do not and simply exploit the cooperators. For newcomers it is beneficial to interact with cooperators but detrimental to interact with cheaters. However, cheaters and cooperators usually cannot be identified unambiguously and newcomers’ decisions are often based on a combination of private and public information. We use evolutionary game theory and dynamical networks to demonstrate how the specificity and sensitivity of those decisions can dramatically affect the resilience of cooperation in the community. We show that promiscuous decisions (high sensitivity, low specificity) are advantageous for cooperation when the strength of competition is weak; however, if competition is strong then the best decisions for cooperation are risk-adverse (low sensitivity, high specificity). Opportune decisions based on private and public information can still support cooperation but suffer of the presence of information cascades that damage cooperation, especially in the case of strong competition. Our research sheds light on the way the interplay of specificity and sensitivity in individual decision-making affects the resilience of cooperation in dynamical structured communities.

2020 - Ranking the invasions of cheaters in structured populations [Articolo su rivista]
Yang, G.; Cavaliere, M.; Zhu, C.; Perc, M.
abstract

The identification of the most influential individuals in structured populations is an important research question, with many applications across the social and natural sciences. Here, we study this problem in evolutionary populations on static networks, where invading cheaters can lead to the collapse of cooperation. We propose six strategies to rank the invading cheaters and identify those which mostly facilitate the collapse of cooperation. We demonstrate that the type of successful rankings depend on the selection strength, the underlying game, and the network structure. We show that random ranking has generally little ability to successfully identify invading cheaters, especially for the stag-hunt game in scale-free networks and when the selection strength is strong. The ranking based on degree can successfully identify the most influential invaders when the selection strength is weak, while more structured rankings perform better at strong selection. Scale-free networks and strong selection are generally detrimental to the performance of the random ranking, but they are beneficial for the performance of structured rankings. Our research reveals how to identify the most influential invaders using statistical measures in structured communities, and it demonstrates how their success depends on population structure, selection strength, and on the underlying game dynamics.

2019 - Identification of influential invaders in evolutionary populations [Articolo su rivista]
Yang, Guoli; Benko, Tina P; Cavaliere, Matteo; Huang, Jincai; Perc, Matjaž
abstract

The identification of the most influential nodes has been a vibrant subject of research across the whole of network science. Here we map this problem to structured evolutionary populations, where strategies and the interaction network are both subject to change over time based on social inheritance. We study cooperative communities, which cheaters can invade because they avoid the cost of contributions that are associated with cooperation. The question that we seek to answer is at which nodes cheaters invade most successfully. We propose the weighted degree decomposition to identify and rank the most influential invaders. More specifically, we distinguish two kinds of ranking based on the weighted degree decomposition. We show that a ranking strategy based on negative-weighted degree allows to successfully identify the most influential invaders in the case of weak selection, while a ranking strategy based on positive-weighted degree performs better when the selection is strong. Our research thus reveals how to identify the most influential invaders based on statistical measures in dynamically evolving cooperative communities.

2018 - A Genetic Circuit Compiler: Generating Combinatorial Genetic Circuits with Web Semantics and Inference [Articolo su rivista]
Waites, W.; Misirli, G.; Cavaliere, M.; Danos, V.; Wipat, A.
abstract

A central strategy of synthetic biology is to understand the basic processes of living creatures through engineering organisms using the same building blocks. Biological machines described in terms of parts can be studied by computer simulation in any of several languages or robotically assembled in vitro. In this paper we present a language, the Genetic Circuit Description Language (GCDL) and a compiler, the Genetic Circuit Compiler (GCC). This language describes genetic circuits at a level of granularity appropriate both for automated assembly in the laboratory and deriving simulation code. The GCDL follows Semantic Web practice, and the compiler makes novel use of the logical inference facilities that are therefore available. We present the GCDL and compiler structure as a study of a tool for generating ?-language simulations from semantic descriptions of genetic circuits.

2018 - An Information-Theoretic Measure for Patterning in Epithelial Tissues [Articolo su rivista]
Waites, W.; Cavaliere, M.; Cachat, E.; Danos, V.; Dvies, J. A.
abstract

We present path entropy, an information-theoretic measure that captures the notion of patterning due to phase separation in organic tissues. Recent work has demonstrated, both in silico and in vitro, that phase separation in epithelia can arise simply from the forces at play between cells with differing mechanical properties. These qualitative results give rise to numerous questions about how the degree of patterning relates to model parameters or underlying biophysical properties. Answering these questions requires a consistent and meaningful way of quantifying degree of patterning that we observe. We define a resolution-independent measure that is better suited than image-processing techniques for comparing cellular structures. We show how this measure can be usefully applied in a selection of scenarios from biological experiment and computer simulation, and argue for the establishment of a tissue-graph library to assist with parameter estimation for synthetic morphology.

2018 - Preface [Breve Introduzione]
Cavaliere, M.; Rodriguez-Paton, A.
abstract

2017 - Cooperation in microbial communities and their biotechnological applications [Articolo su rivista]
Cavaliere, Matteo; Feng, Song; Soyer, Orkun S; Jiménez, José I
abstract

Microbial communities are increasingly utilized in biotechnology. Efficiency and productivity in many of these applications depends on the presence of cooperative interactions between members of the community. Two key processes underlying these interactions are the production of public goods and metabolic cross-feeding, which can be understood in the general framework of ecological and evolutionary (eco-evo) dynamics. In this review, we illustrate the relevance of cooperative interactions in microbial biotechnological processes, discuss their mechanistic origins and analyse their evolutionary resilience. Cooperative behaviours can be damaged by the emergence of cheating' cells that benefit from the cooperative interactions but do not contribute to them. Despite this, cooperative interactions can be stabilized by spatial segregation, by the presence of feedbacks between the evolutionary dynamics and the ecology of the community, by the role of regulatory systems coupled to the environmental conditions and by the action of horizontal gene transfer. Cooperative interactions enrich microbial communities with a higher degree of robustness against environmental stress and can facilitate the evolution of more complex traits. Therefore, the evolutionary resilience of microbial communities and their ability to constraint detrimental mutants should be considered to design robust biotechnological applications.

2017 - Eco-evolutionary feedbacks can rescue cooperation in microbial populations [Articolo su rivista]
Moreno-Fenoll, C.; Cavaliere, M.; Martinez-Garcia, E.; Poyatos, J. F.
abstract

Bacterial populations whose growth depends on the cooperative production of public goods are usually threatened by the rise of cheaters that do not contribute but just consume the common resource. Minimizing cheater invasions appears then as a necessary mechanism to maintain these populations. However, that invasions result instead in the persistence of cooperation is a prospect that has yet remained largely unexplored. Here, we show that the demographic collapse induced by cheaters in the population can actually contribute to the rescue of cooperation, in a clear illustration of how ecology and evolution can influence each other. The effect is made possible by the interplay between spatial constraints and the essentiality of the shared resource. We validate this result by carefully combining theory and experiments, with the engineering of a synthetic bacterial community in which the public compound allows survival to a lethal stress. The characterization of the experimental system identifies additional factors that can matter, like the impact of the lag phase on the tolerance to stress, or the appearance of spontaneous mutants. Our work explains the unanticipated dynamics that eco-evolutionary feedbacks can generate in microbial communities, feedbacks that reveal fundamental for the adaptive change of ecosystems at all scales.

2017 - The evolutionary resilience of distributed cellular computing [Relazione in Atti di Convegno]
Cavaliere, M.; Sanchez, A.
abstract

Individual cells process environmental information relevant to their functions using biochemical processes and signalling networks that implement a flow of information from the extracellular environment, across the cell membrane to the cytoplasm in which the actual cellular computation takes place (in the form of gene expression). In many cases, the environmental information to be processed are either molecules produced by other cells or shared extracellular molecules - in this case the processing of the environmental information is a distributed, highly parallel computing process, in which cells must synchronize, coordinate and cooperate. While the ability of cells to cooperate can increase their overall computational power, it also raises an evolutionary stability issue population of cooperating cells are at risk of cheating cells invasions, cells that do not cooperate but exploit the benefits of the population. The bridge between membrane computing (as a mathematical formalization of cellular computing) and evolutionary dynamics (as mathematical formalization of natural selection) could lead to interesting insights on the evolutionary stability of cellular computing.

2016 - Annotation of rule-based models with formal semantics to enable creation, analysis, reuse and visualization [Articolo su rivista]
Misirli, G.; Cavaliere, M.; Waites, W.; Pocock, M.; Madsen, C.; Gilfellon, O.; Honorato-Zimmer, R.; Zuliani, P.; Danos, V.; Wipat, A.
abstract

Motivation: Biological systems are complex and challenging to model and therefore model reuse is highly desirable. To promote model reuse, models should include both information about the specifics of simulations and the underlying biology in the form of metadata. The availability of computationally tractable metadata is especially important for the effective automated interpretation and processing of models. Metadata are typically represented as machine-readable annotations which enhance programmatic access to information about models. Rule-based languages have emerged as a modelling framework to represent the complexity of biological systems. Annotation approaches have been widely used for reaction-based formalisms such as SBML. However, rule-based languages still lack a rich annotation framework to add semantic information, such as machine-readable descriptions, to the components of a model. Results: We present an annotation framework and guidelines for annotating rule-based models, encoded in the commonly used Kappa and BioNetGen languages. We adapt widely adopted annotation approaches to rule-based models. We initially propose a syntax to store machine-readable annotations and describe a mapping between rule-based modelling entities, such as agents and rules, and their annotations. We then describe an ontology to both annotate these models and capture the information contained therein, and demonstrate annotating these models using examples. Finally, we present a proof of concept tool for extracting annotations from a model that can be queried and analyzed in a uniform way. The uniform representation of the annotations can be used to facilitate the creation, analysis, reuse and visualization of rule-based models. Although examples are given, using specific implementations the proposed techniques can be applied to rule-based models in general. Availability and implementation: The annotation ontology for rule-based models can be found at http://purl.org/rbm/rbmo. The krdf tool and associated executable examples are available at http://purl.org/rbm/rbmo/krdf. Contact: or vdanos@inf.ed.ac.uk.

2016 - Detecting the Collapse of Cooperation in Evolving Networks [Articolo su rivista]
Cavaliere, M.; Yang, G.; Danos, V.; Dakos, V.
abstract

The sustainability of biological, social, economic and ecological communities is often determined by the outcome of social conflicts between cooperative and selfish individuals (cheaters). Cheaters avoid the cost of contributing to the community and can occasionally spread in the population leading to the complete collapse of cooperation. Although such collapse often unfolds unexpectedly, it is unclear whether one can detect the risk of cheater's invasions and loss of cooperation in an evolving community. Here, we combine dynamical networks and evolutionary game theory to study the abrupt loss of cooperation with tools for studying critical transitions. We estimate the risk of cooperation collapse following the introduction of a single cheater under gradually changing conditions. We observe an increase in the average time it takes for cheaters to be eliminated from the community as the risk of collapse increases. We argue that such slow system response resembles slowing down in recovery rates prior to a critical transition. In addition, we show how changes in community structure reflect the risk of cooperation collapse. We find that these changes strongly depend on the mechanism that governs how cheaters evolve in the community. Our results highlight novel directions for detecting abrupt transitions in evolving networks.

2014 - The stochastic loss of spikes in spiking neural P systems: Design and implementation of reliable arithmetic circuits [Articolo su rivista]
Xu, Z.; Cavaliere, M.; An, P.; Vrudhula, S.; Cao, Y.
abstract

Spiking neural P systems (in short, SN P systems) have been introduced as computing devices inspired by the structure and functioning of neural cells. The presence of unreliable components in SN P systems can be considered in many different aspects. In this paper we focus on two types of unreliability: the stochastic delays of the spiking rules and the stochastic loss of spikes. We propose the implementation of elementary SN P systems with DRAM-based CMOS circuits that are able to cope with these two forms of unreliability in an efficient way. The constructed bio-inspired circuits can be used to encode basic arithmetic modules.

2013 - Cooperation and competition in the dynamics of tissue architecture during homeostasis and tumorigenesis [Articolo su rivista]
Csikasz-Nagy, A.; Escudero, L. M.; Guillaud, M.; Sedwards, S.; Baum, B.; Cavaliere, M.
abstract

The construction of a network of cell-to-cell contacts makes it possible to characterize the patterns and spatial organization of tissues. Such networks are highly dynamic, depending on the changes of the tissue architecture caused by cell division, death and migration. Local competitive and cooperative cell-to-cell interactions influence the choices cells make. We review the literature on quantitative data of epithelial tissue topology and present a dynamical network model that can be used to explore the evolutionary dynamics of a two dimensional tissue architecture with arbitrary cell-to-cell interactions. In particular, we show that various forms of experimentally observed types of interactions can be modelled using game theory. We discuss a model of cooperative and non-cooperative cell-to-cell communication that can capture the interplay between cellular competition and tissue dynamics. We conclude with an outlook on the possible uses of this approach in modelling tumorigenesis and tissue homeostasis. © 2013 Elsevier Ltd.

2013 - Plasticity facilitates sustainable growth in the commons [Articolo su rivista]
Cavaliere, M.; Poyatos, J. F.
abstract

In the commons, communities whose growth depends on public good, individuals often rely on surprisingly simple strategies, or heuristics, to decide whether to contribute to the shared resource (at risk of exploitation by free-riders). Although this appears a limitation, we show here how four heuristics lead to sustainable growth when coupled to specific ecological constraints. The two simplest ones - contribute permanently or switch stochastically between contributing or not - are first shown to bring sustainability when the public good efficiently promotes growth. If efficiency declines and the commons is structured in small groups, the most effective strategy resides in contributing only when a majority of individuals are also contributors. In contrast, when group size becomes large, the most effective behaviour follows a minimal-effort rule: contribute only when it is strictly necessary. Both plastic strategies are observed in natural scenarios across scales that present them as relevant social motifs for the sustainable management of public goods. © 2013 The Authors.

2012 - Combining game theory and graph theory to model interactions between cells in the tumor microenvironment [Capitolo/Saggio]
Csikasz-Nagy, A.; Cavaliere, M.; Sedwards, S.
abstract

Mathematical concepts of graph theory and game theory both influence models of biological systems. We combine these two approaches to understand how game-like interactions influence the cellular topology of a planar tissue. We review the literature on the role of cell to cell interactions in tumourigenesis and survey the mathematical approaches that have been used to simulate such cell-cell interactions. We present how this game-graph approach can be used to simulate epithelial tissue growth and how it can foster our understanding of the role of cell-cell communication in the early stages of cancer development. We present computational models that we use to test how cooperating and non-cooperating cells build planar tissues and compare the simulated tissue topologies with literature data. We further discuss how such system could be used to model microenviromental communications between cancer cells and the surrounding tissue.

2012 - Prosperity is associated with instability in dynamical networks [Articolo su rivista]
Cavaliere, Matteo; Sedwards, Sean; Tarnita, Corina E; Nowak, Martin A; Csikász-Nagy, Attila
abstract

Social, biological and economic networks grow and decline with occasional fragmentation and reformation, often explained in terms of external perturbations. We show that these phenomena can be a direct consequence of simple imitation and internal conflicts between 'cooperators' and 'defectors'. We employ a game-theoretic model of dynamic network formation where successful individuals are more likely to be imitated by newcomers who adopt their strategies and copy their social network. We find that, despite using the same mechanism, cooperators promote well-connected highly prosperous networks and defectors cause the network to fragment and lose its prosperity; defectors are unable to maintain the highly connected networks they invade. Once the network is fragmented it can be reconstructed by a new invasion of cooperators, leading to the cycle of formation and fragmentation seen, for example, in bacterial communities and socio-economic networks. In this endless struggle between cooperators and defectors we observe that cooperation leads to prosperity, but prosperity is associated with instability. Cooperation is prosperous when the network has frequent formation and fragmentation. (c) 2011 Elsevier Ltd. All rights reserved.

2011 - An observer-based de-quantisation of Deutsch's algorithm [Articolo su rivista]
Calude, C. S.; Cavaliere, M.; Mardare, R.
abstract

Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithmclassical solutions which are as efficient as the quantum onehave been proposed in the literature. These solutions are based on the possibility of classically simulating "superpositions", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their "observational power". © 2011 World Scientific Publishing Company.

2011 - Computing by observing: Simple systems and simple observers [Articolo su rivista]
Cavaliere, M.; Leupold, P.
abstract

We survey and extend the work on the paradigm called "computing by observing". Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this purpose an external observer records this behavior. In this way, several computational trade-offs between the observer and the observed system can be determined. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems, an abstract model of DNA computing. Finally, we introduce and investigate the case where the observers can read only one measure of the observed system (e.g., mass or temperature), modeling in this way the limitations in the observation of real physical systems. Finally, a research perspective on the topic is presented. © 2010 Elsevier B.V. All rights reserved.

2011 - On aggregation in multiset-based self-assembly of graphs [Articolo su rivista]
Bernardini, F.; Brijder, R.; Cavaliere, M.; Franco, G.; Hoogeboom, H. J.; Rozenberg, G.
abstract

We continue the formal study of multiset-based self-assembly. The process of self-assembly of graphs, where iteratively new nodes are attached to a given graph, is guided by rules operating on nodes labelled by multisets. In this way, the multisets and rules model connection points (such as "sticky ends") and complementarity/affinity between connection points, respectively. We identify three natural ways (individual, free, and collective) to attach (aggregate) new nodes to the graph, and study the generative power of the corresponding self-assembly systems. For example, it turns out that individual aggregation can be simulated by free or collective aggregation. However, we demonstrate that, for a fixed set of connection points, collective aggregation is rather restrictive. We also give a number of results that are independent of the way that aggregation is performed. © 2010 Springer Science+Business Media B.V.

2010 - A (Natural) Computing Perspective on Cellular Processes [Capitolo/Saggio]
Cavaliere, M.; Mazza, T.
abstract

2009 - Asynchronous spiking neural P systems [Articolo su rivista]
Cavaliere, M.; Ibarra, O. H.; Paun, G.; Egecioglu, O.; Ionescu, M.; Woodworth, S.
abstract

We consider here spiking neural P systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete. For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable. © 2009 Elsevier B.V. All rights reserved.

2009 - Cell Cycle and Tumor Growth in Membrane Systems with Peripheral Proteins [Relazione in Atti di Convegno]
Mazza, T.; Cavaliere, M.
abstract

Membrane systems with peripheral proteins are essentially standard membrane systems with the possibility of having multisets of objects (proteins) embedded in the membranes and with the presence of rules that control the transport and the change of configurations of these proteins. The model intends to abstract the activities of the receptors embedded in the cellular membranes. In this paper we use an extension of this paradigm to model and simulate some of the mechanisms underlying cell cycle and breast tumor growth. In particular we have defined a membrane system that abstracts the G2/M cell cycle phase transition and extends the corresponding Reactome model. The model has been then simulated by using the software Cyto-Sim and we have monitored the interplay between activators and inhibitors of the cell cycle. © 2008 Elsevier B.V. All rights reserved.

2009 - DNA splicing: Computing by observing [Articolo su rivista]
Cavaliere, M.; Jonoska, N.; Leupold, P.
abstract

Motivated by several techniques for observing molecular processes in real-time we introduce a computing device that stresses the role of the observer in biological computations and that is based on the observed behavior of a splicing system. The basic idea is to introduce a marked DNA strand into a test tube with other DNA strands and restriction enzymes. Under the action of these enzymes the DNA starts to splice. An external observer monitors and registers the evolution of the marked DNA strand. The input marked DNA strand is then accepted if its observed evolution follows a certain expected pattern. We prove that using simple observers (finite automata), applied on finite splicing systems (finite set of rules and finite set of axioms), the class of recursively enumerable languages can be recognized. © Springer Science+Business Media B.V. 2007.

2008 - A logical characterization of robustness, mutants and species in colonies of agents [Articolo su rivista]
Mardare, R.; Cavaliere, M.; Sedwards, S.
abstract

We study a modelling framework and computational paradigm called Colonies of Synchronizing Agents (CSAs), which abstracts intracellular and intercellular mechanisms of biological tissues. The model is based on a multiset of agents (cells) in a common environment (a tissue). Each agent has a local contents, stored in the form of a multiset of atomic objects (e.g., representing molecules), updated by multiset rewriting rules which may act on individual agents (intracellular action) or synchronize the contents of pairs of agents (intercellular action). In this paper we investigate dynamic properties of CSAs, by means of temporal logic, and we give a logical characterization of some notions inspired by biology such as robustness, mutants and species. We reveal the relation that exists between the concept of robustness for CSAs and the bisimulation relation on colonies. We also present some decidability results for particular cases of robustness. © 2008 World Scientific Publishing Company.

2008 - A multiset-based model of synchronizing agents: Computability and robustness [Articolo su rivista]
Cavaliere, M.; Mardare, R.; Sedwards, S.
abstract

We introduce a modelling framework and computational paradigm called Colonies of Synchronizing Agents (CSAs) inspired by the intracellular and intercellular mechanisms in biological tissues. The model is based on a multiset of agents in a common environment. Each agent has a local state stored in the form of a multiset of atomic objects, which is updated by global multiset rewriting rules either independently or synchronously with another agent. We first define the model then study its computational power, considering trade-offs between internal rewriting (intracellular mechanisms) and synchronization between agents (intercellular mechanisms). We also investigate dynamic properties of CSAs, including behavioural robustness (ability to generate a core behaviour despite agent loss or rule failure) and safety of synchronization (ability of an agent to synchronize with some other agent whenever needed). © 2007 Elsevier Ltd. All rights reserved.

2008 - Asynchronous spiking neural P systems: Decidability and undecidability [Relazione in Atti di Convegno]
Cavaliere, M.; Egecioglu, O.; Ibarra, O. H.; Ionescu, M.; Paun, G.; Woodworth, S.
abstract

In search for "realistic" bio-inspired computing models, we consider asynchronous spiking neural P systems, in the hope to get a class of computing devices with decidable properties. However, although the non-synchronization is known in general to decrease the computing power, in the case of using extended rules (several spikes can be produced by a rule) we obtain again the equivalence with Turing machines (interpreted as generators of sets of vectors of numbers). The problem remains open for the case of restricted spiking neural P systems, whose rules can only produce one spike. On the other hand, we prove that asynchronous spiking neural P systems, with a specific way of halting, using extended rules and where each neuron is either bounded or unbounded, are equivalent to partially blind counter machines and, therefore, have many decidable properties. © 2008 Springer-Verlag Berlin Heidelberg.

2008 - Computing by observing: A brief survey [Relazione in Atti di Convegno]
Cavaliere, M.
abstract

This paper is a brief survey of a computational paradigm called computing by observing that stresses the role of an observer in computation. The idea of the paradigm is that a computing device can be obtained by combining a basic system and an observer that transforms the trajectories of the basic system into a readable output. The paradigm has been applied in several areas: natural computing (DNA computing and membrane computing), automata and formal language theory. In general, it has been shown that simple basic systems observed by simple observers can produce that which only much more complex systems can produce. © 2008 Springer-Verlag Berlin Heidelberg.

2008 - Decision problems in membrane systems with peripheral proteins, transport and evolution [Articolo su rivista]
Cavaliere, M.; Sedwards, S.
abstract

Transport of substances and communication between compartments are fundamental biological processes, often mediated by the presence of complementary proteins attached to the surfaces of membranes. Within compartments, substances are acted upon by local biochemical rules. Inspired by this behaviour we present a model based on Membrane Systems, with objects attached to the sides of the membranes and floating objects that can be moved between the regions of the system. Moreover, in each region there are evolution rules that rewrite the transported objects, mimicking chemical reactions. We investigate qualitative properties, like configuration reachability, in relation to the use of cooperative or non-cooperative evolution and transport rules and in the contexts of free- and maximal-parallel evolution. © 2008.

2008 - Experiments on the reliability of stochastic spiking neural P systems [Articolo su rivista]
Cavaliere, M.; Mura, I.
abstract

In the area of membrane computing, time-freeness has been defined as the ability for a timed membrane system to produce always the same result, independently of the execution times associated to the rules. In this paper, we use a similar idea in the framework of spiking neural P systems, a model inspired by the structure and the functioning of neural cells. In particular, we introduce stochastic spiking neural P systems where the time of firing for an enabled spiking rule is probabilistically chosen and we investigate when, and how, these probabilities can influence the ability of the systems to simulate, in a reliable way, universal machines, such as register machines. © Springer Science+Business Media B.V. 2008.

2008 - Membrane systems with proteins embedded in membranes [Articolo su rivista]
Brijder, R.; Cavaliere, M.; Riscos-Núñez, A.; Rozenberg, G.; Sburlan, D.
abstract

Membrane computing is a biologically inspired computational paradigm. Motivated by brane calculi we investigate membrane systems which differ from conventional membrane systems by the following features: (1) biomolecules (proteins) can move through the regions of the systems, and can attach onto (and de-attach from) membranes, and (2) membranes can evolve depending on the attached molecules. The evolution of membranes is performed by using rules that are motivated by the operation of pinocytosis (the pino rule) and the operation of cellular dripping (the drip rule) that take place in living cells.We show that such membrane systems are computationally universal. We also show that if only the second feature is used then one can generate at least the family of Parikh images of the languages generated by programmed grammars without appearance checking (which contains non-semilinear sets of vectors).If, moreover, the use of pino/drip rules is non-cooperative (i.e., not dependent on the proteins attached to membranes), then one generates a family of sets of vectors that is strictly included in the family of semilinear sets of vectors.We also consider a number of decision problems concerning reachability of configurations and boundness. (C) 2008 Elsevier B.V. All rights reserved.

2007 - Membrane Systems with Marked Membranes [Articolo su rivista]
Brijder, R.; Cavaliere, M.; Riscos-Nunez, A.; Rozenberg, G.; Sburlan, D.
abstract

Membrane computing is a biologically inspired computational paradigm. Motivated by brane calculi we investigate membrane systems which differ from conventional membrane systems by the following features: (1) biomolecules (proteins) can move through the regions of the systems, and can attach onto (and de-attach from) membranes, and (2) membranes can evolve depending on the attached molecules. The evolution of membranes is performed by using rules that are motivated by the operation of pinocytosis (the pino rule) and the operation of cellular dripping (the drip rule) that take place in living cells. We show that such membrane systems are computationally universal. We also show that if only the second feature is used then one can generate at least the family of Parikh images of the languages generated by programmed grammars without appearance checking (which contains non-semilinear sets of vectors). If, moreover, the use of pino/drip rules is non-cooperative (i.e., not dependent on the proteins attached to membranes), then one generates a family of sets of vectors that is strictly included in the family of semilinear sets of vectors. We also consider a number of decision problems concerning reachability of configurations and boundness. © 2007 Elsevier B.V. All rights reserved.

2007 - Membrane Systems with Peripheral Proteins: Transport and Evolution [Relazione in Atti di Convegno]
Cavaliere, M.; Sedwards, S.
abstract

Transport of substances and communication between compartments are fundamental biological processes, often mediated by the presence of complementary proteins attached to the surfaces of membranes. Within compartments, substances are acted upon by local biochemical rules. Inspired by this behaviour we present a model based on membrane systems, with objects attached to the sides of the membranes and floating objects that can move between the regions of the system. Moreover, in each region there are evolution rules that rewrite the transported objects, mimicking chemical reactions. We first analyse the system, showing that interesting qualitative properties can be decided (like reachability of configurations) and then present a simulator based on a stochastic version of the introduced model and show how it can be used to simulate relevant quantitative biological processes. © 2007 Elsevier B.V. All rights reserved.

2007 - Multiset random context grammars, checkers, and transducers [Articolo su rivista]
Cavaliere, M.; Freund, R.; Oswald, M.; Sburlan, D.
abstract

We introduce a general model of random context multiset grammars as well as the concept of multiset random context checkers and transducers. Our main results show how recursively enumerable sets of finite multisets can be generated using these models of computing; corresponding results for antiport P systems are established, too. © 2006 Elsevier Ltd. All rights reserved.

2006 - Computing by only observing [Relazione in Atti di Convegno]
Cavaliere, M.; Frisco, P.; Hoogeboom, H. J.
abstract

The paradigm of evolution/observation is based on the idea that a computing device can be obtained by combining a basic system and an observer that transforms the evolution of the basic system into a readable output. In this framework we investigate what can be computed by changing the observer but not the basic observed system. We consider grammars as basic systems combined with finite state automata as observers, watching either the sequence of sentential forms or the productions used by the grammar. It is possible to obtain computational completeness only varying the observer, without modifying the basic system, which is a fixed context-free grammar. © Springer-Verlag Berlin Heidelberg 2006.

2006 - Further results on time-free P systems [Articolo su rivista]
Cavaliere, M.; Deufemia, V.
abstract

Membrane systems (currently called P systems) are parallel computing devices inspired by the structure and the functioning of living cells. A standard feature of P systems is that each rule is executed in exactly one time unit. Actually, in living cells different chemical reactions might take different times to be executed; moreover, it might be hard to know precisely such time of execution. For this reason, in [7] two models of P systems (time-free and clock-free P systems) have been defined and investigated, where the time of execution of the rules is arbitrary and the output produced by the system is always the same, independently of this time. Preliminary results concerning time-free and clock-free P system have been obtained in [6,7,8]. In this paper we continue these investigations by considering different combinations of possible ingredients. In particular, we present the universality of time-free P systems using bi-stable catalysts. Then, we prove that this result implies that is not possible to decide whether an arbitrary bi-stable catalytic P system is time-free. We present several results about time-free evolutioncommunication P systems, where the computation is a mixed application of evolution and symport/antiport rules. In this case we obtain the universality even by using noncooperative evolution rules and antiports of weight one. Finally, we formulate several open problems. © World Scientific Publishing Company.

2006 - Membrane systems with external control [Relazione in Atti di Convegno]
Brijder, R.; Cavaliere, M.; Riscos-Nunez, A.; Rozenberg, G.; Sburlan, D.
abstract

We consider the idea of controlling the evolution of a membrane system. In particular, we investigate a model of membrane systems using promoted rules, where a string of promoters (called the control string) "travels" through the regions, activating the rules of the system. This control string is present in the skin region at the beginning of the computation - one can interpret that it has been inserted in the system before starting the computation - and it is "consumed", symbol by symbol, while traveling through the system. In this way, the inserted string drives the computation of the membrane system by controlling the activation of evolution rules. When the control string is entirely consumed and no rule can be applied anymore, then the system halts - this corresponds to a successful computation. The number of objects present in the output region is the result of such a computation. In this way, using a set of control strings (a control program), one generates a set of numbers. We also consider a more restrictive definition of a successful computation, and then study the corresponding model. In this paper we investigate the influence of the structure of control programs on the generative power. We demonstrate that different structures yield generative powers ranging from finite to recursively enumerable number sets. In determining the way that the control string moves through the regions, we consider two possible "strategies of traveling", and prove that they are similar as far as the generative power is concerned. © Springer-Verlag Berlin Heidelberg 2006.

2006 - Modelling cellular processes using membrane systems with peripheral and integral proteins [Relazione in Atti di Convegno]
Cavaliere, M.; Sedwards, S.
abstract

Membrane systems were introduced as models of computation inspired by the structure and functioning of biological cells. Recently, membrane systems have also been shown to be suitable to model cellular processes. We introduce a new model called Membrane Systems with Peripheral and Integral Proteins. The model has compartments enclosed by membranes, floating objects, objects associated to the internal and external surfaces of the membranes and also objects integral to the membranes. The floating objects can be processed within the compartments and can interact with the objects associated to the membranes. The model can be used to represent cellular processes that involve compartments, surface and integral membrane proteins, transport and processing of chemical substances. As examples we model a circadian clock and the G-protein cycle in yeast saccharomyces cerevisiae and present a quantitative analysis using an implemented simulator. © Springer-Verlag Berlin Heidelberg 2006.

2006 - Observation of string-rewriting systems [Articolo su rivista]
Cavaliere, M.; Leupold, P.
abstract

Models of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power.

2006 - Partial knowledge in membrane systems: A logical approach [Relazione in Atti di Convegno]
Cavaliere, M.; Mardare, R.
abstract

We propose a logic for specifying and proving properties of membrane systems. The main idea is to approach a membrane system by using the "point of view" of an external observer. Observers (as epis-temic agents) accumulate their knowledge from the partial information they collect by observing subparts of the system and by applying logical reasoning to this information. We provide a formal framework to combine and interpret distributed knowledge in order to recover the complete knowledge about a membrane system. The proposed logic can be used to model biological situations where information concerning parts of the biological system is missing or incomplete. © Springer-Verlag Berlin Heidelberg 2006.

2006 - Recognizing DNA splicing [Relazione in Atti di Convegno]
Cavaliere, M.; Jonoska, N.; Leupold, P.
abstract

Motivated by recent techniques developed for observing evolutionary dynamics of a single DNA molecule, we introduce a formal model for accepting an observed behavior of a splicing system. The main idea is to input a marked DNA strand into a test tube together with certain restriction enzymes and, possibly, with other DNA strands. Under the action of the enzymes, the marked DNA strand starts to evolve by splicing with other DNA strands. The evolution of the marked DNA strand is "observed" by an outside observer and the input DNA strand is "accepted" if its (observed) evolution follows a certain expected pattern. We prove that using finite splicing system (finite set of rules and finite set of axioms), universal computation is attainable with simple observing and accepting devices made of finite state automata. © Springer-Verlag Berlin Heidelberg 2006.

2005 - Biomolecular implementation of computing devices with unbounded memory [Relazione in Atti di Convegno]
Cavaliere, M.; Jonoska, N.; Yogev, S.; Piran, R.; Keinan, E.; Seeman, N. C.
abstract

We propose a new way to implement (general) computing devices with unbounded memory. In particular, we show a procedure to implement automata with unbounded stack memory, push-down automata, using circular DNA molecules and a class IIs restriction enzyme. The proposed ideas are inspired by the results from [1]. The same ideas are extended to show a way to implement push-down automata with two stacks (i.e, universal computing devices) using two circular molecules glued with a DX molecule and a class IIs restriction enzyme. In this case each computational molecule also contains a DX portion. These devices can potentially be incorporated in an array of TX molecules. © Springer-Verlag Berlin Heidelberg 2005.

2005 - Computing by observing bio-systems: The case of sticker systems [Relazione in Atti di Convegno]
Alhazov, A.; Cavaliere, M.
abstract

A very common approach in chemistry and biology is to observe the progress of an experiment, and take the result of this observation as the final output. Inspired by this, a new approach to computing, called system/observer, was introduced in [3]. In this paper we apply this strategy to sticker systems, [8, 11]. In particular we use finite automata (playing the role of observer) watching the "evolution" of a sticker system and translating such "evolution" into a readable output. We show that this way of "computing by observing" brings us results quite different from the ones obtained when considering sticker systems in the standard manner. Even regular simple sticker systems (whose generative power is subregular) become universal when considered in this new framework. The significance of these results for DNA computing (by sticker systems) is briefly discussed. © Springer-Verlag Berlin Heidelberg 2005.

2005 - Computing using signals: From cells to P systems [Articolo su rivista]
Ardelean, I. I.; Cavaliere, M.; Sburlan, D.
abstract

In cell biology a fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computation is controlled by signals which move across the regions. In particular, we consider signals-based P systems where the symbol-objects cannot be moved and the evolution rules can be activated/ inactivated using a finite number of signals (signal-promoters) moved across the membranes; differently from standard P systems using promoters, in our case signal-promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst and a bounded number of signal-promoters. Also results concerning signals-based P systems using non cooperative rules together with several open problems are presented. © Springer-Verlag 2005.

2005 - Evolution and observation: A non-standard way to accept formal languages [Relazione in Atti di Convegno]
Cavaliere, M.; Leupold, P.
abstract

It is a very common procedure in biology to observe the progress of an experiment and regard the result of this observation as the final outcome. Inspired by this, a new approach for generating formal languages, called evolution/observation, has been introduced [6]. In the current work we consider evolution/observation as a new strategy also for accepting languages: a word is accepted, if the (observed) evolution of a certain system starting from this input follows a regular pattern. We obtain the following result: checking if the (observed) evolution of a context-free system follows a regular pattern is enough to accept every recursively enumerable languages. On the other hand, if we observe the evolution of systems using very simple rules (of the kind a → b), then it is possible to accept exactly the class of context-sensitive languages. © Springer-Verlag Berlin Heidelberg 2005.

2005 - Inhibiting/de-inhibiting rules in P systems [Relazione in Atti di Convegno]
Cavaliere, M.; Ionescu, M.; Ishdorj, T. -O.
abstract

We introduce in the P systems area a mechanism, inspired from neural-cell behavior, which controls computations by inhibiting and de-inhibiting evolution rules. We investigate the computational power of this mechanism in both generative and accepting P systems. In particular, we prove that universality can be obtained by using one catalyst. If we use only non-cooperative rules and one membrane, then we can obtain at least the family of Parikh images of the languages generated by ET0L systems. Several research proposals are also suggested. © Springer-Verlag Berlin Heidelberg 2005.

2005 - Time and synchronization in membrane systems [Articolo su rivista]
Cavaliere, M.; Sburlan, D.
abstract

Membrane systems are parallel computational devices inspired from the cell functioning. Since the original definition, a standard feature of membrane systems is the fact that each rule of the system is executed in exactly one time-unit. However, this hypothesis seems not to have a counterpart in real world. In fact, in cells, chemical reactions might take different times to be exe-cuted. Therefore, a natural step is to associate to each rule of a membrane system a certain time of execution. We are interested in membrane systems, called time-free, working independently from the assigned execution time of the rules. A basic and interesting problem in time-free membrane systems consists in the synchronization of different rules, running in parallel, and having unknown execution times. Here, we present different ways to approach this problem within the framework of membrane systems. Several research proposals are also suggested.

2005 - Time-independent P systems [Relazione in Atti di Convegno]
Cavaliere, M.; Sburlan, D.
abstract

We introduce a class of P systems called timed P systems where to each rule is associated an integer that represents the time needed by the rule (reaction) to be entirely executed. The idea comes from cell biology where chemical reactions take certain times to be executed. In this work we are interested in a special class of P systems, called time-free, working always in the same way (i.e., always producing the same result) independently from the values associated to the execution time of their rules. Later we introduce a generalization of time-free P systems, namely clock-free P systems, where a time of execution is associated directly to each single application of the rules (in this case, different applications, even of the same rule, may take a different time to be executed). Several results are presented together with open problems and research proposals. © Springer-Verlag Berlin Heidelberg 2005.

2004 - Evolution and observation - A non-standard way to generate formal languages [Articolo su rivista]
Cavaliere, M.; Leupold, P.
abstract

In biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. Inspired by this, we have introduced P/O systems (A. Alhazov, C. Martín-Vide, Gh. Pǎun, Pre-Proc. of the Workshop on Membrane Computing 2003, Tarrragona, Spain; http://pizarro.fll.urv.es/continguts/ linguistica/proyecto/reports/wmc03.html), where languages are generated by multiset automata that observe the evolution of membrane systems. Now we apply this approach also to more classical devices of formal language theory. Namely, we use finite automata observing the derivations of grammars or of Lindenmayer systems. We define several modes of operation for grammar/observer systems. In two of these modes a context-free grammar (or even a locally commutative context-free grammar) with a finite automaton as observer suffices to generate any recursively enumerable language. In a third case, we obtain a class of languages between the context-free and context-sensitive ones. © 2004 Elsevier B.V. All rights reserved.

2004 - Evolution and observation: A new way to look at membrane systems [Relazione in Atti di Convegno]
Cavaliere, M.; Leupold, P.
abstract

An architecture for investigating the dynamical behaviour of biological systems is proposed by using the concepts of "behaviour" and "observer". The behaviour of a biological system is the sequence of states traversed as time passes; the observer is a device translating this behaviour into a readable output. As an instance of this architecture we investigate P/O systems constituted by a membrane system and a multiset finite automaton observer. We first characterize the infinite behaviours of conservative systems, i.e., systems whose number of objects is constant. These systems behave very regularly. For more sophisticated systems we then use also more complicated multiset automata as observers: they map the configurations into an output alphabet and thus we obtain words describing the entire computations. Even for seemingly simple membrane systems using only non-cooperative rules and regular-like observers through this combination a great power emerges, in our case computational universality. © Springer-Verlag Berlin Heidelberg 2004.

2004 - P systems with symport/antiport of rules [Articolo su rivista]
Cavaliere, M.; Genova, D.
abstract

Moving "instructions" instead of "data" using transport mechanisms inspired by biology is the basic idea of the computing device presented in this paper. Specifically, we propose a new class of P systems that use both evolution rules and symport/antiport rules. The idea of this kind of systems is the following: during a computation, symbol-objects (the "data") evolve using evolution rules, but they cannot be moved; on the other hand, the evolution rules (the "instructions") can be moved across the membranes using classical symport/antiport rules. We present a number of results using different combinations of evolution rules (catalytic, non-cooperative) and the weight of the symport/antiport rules. In particular, we show that using non-cooperative rules and antiports of unbounded weight makes it possible to obtain at least the Parikh set of ETOL languages. On the other hand, using catalytic rules (one catalyst) and antiports of weight 2, these system become universal. Several open problems are also presented. © J.UCS.

2004 - Proton pumping P systems [Relazione in Atti di Convegno]
Alhazov, A.; Cavaliere, M.
abstract

We propose here a (biologically inspired) model of P system called proton pumping P system that is a special case of evolution-communication P system. In cell biology there are transport mechanisms, involving protons. We generalize this idea by considering a few different types of protons. A proton pumping P system is, essentially, an evolution-communication P system where a special subset of symbol-objects (called protons) is used. In such a system we have simple evolution rules (classical evolution rules without target indications), symport and antiport rules that exchange some objects (among them, possibly, other protons) for a proton; taking inspiration from biology, this particular type of antiports is often called proton pumping rules. We show that, as expected, the new model is universal, using non-cooperative rules, symport and antiport rules of weight one, and enough types of protons available for the computation. If we decrease the number of types of protons to one or two, then the model is at least as powerful as ETOL system, provided that (total) weak or strong priority of antiport rules over symport and evolution rules are used. Finally, we consider some descriptional complexity measures (again, inspired from biology) for the newly introduced model. © Springer-Verlag Berlin Heidelberg 2004.

2003 - An application of dynamic P systems: Generating context-free languages [Relazione in Atti di Convegno]
Enguix, G. B.; Cavaliere, M.; Ceterchi, R.; Gramatovici, R.; Martin-Vide, C.
abstract

We present a method of generating context-free languages, in a parallel way, using dynamic P systems, which evolve in time in a coherent manner. The evolution is described by a contextual grammar D(G), which can be canonically associated to any context-free grammar G. The dynamic P system generated by D(G) will "compute" the language L(G), i.e., one of the configurations of the system will contain all words of L(G) of length n at depth 2n - 1. Our approach is an attempt to prove the richness and power of the concept of dynamic P system, both in the area of P systems, and in the area of contextual grammars. © Springer-Verlag Berlin Heidelberg 2003.

2003 - Evolution-communication P systems [Relazione in Atti di Convegno]
Cavaliere, M.
abstract

We propose a new class of P systems that use simple evolution rules (classical evolution rules without communication targets) and symport/antiport rules (for communication). This type of P system is realistic for (at least) three different reasons: we do not have target indications in the evolution rules, we use very simple symport/antiport rules to realize communication, and we do not need objects available in the environment at the beginning of a computation. Somewhat expected, this new variant is still universal. We prove the universality in two cases: when using catalytic rules (but only one catalyst), symport/antiport rules of weight one, and two membranes, and when we use three membranes, symport/antiport rules of weight one, and no catalyst. Especially the latter result is of interest, because the catalysts were used in most universality proofs for P systems with symbol-objects. Also new is the proof technique we use: we start from programmed grammars with unconditional transfer. © Springer-Verlag Berlin Heidelberg 2003.

2003 - Forbidding and enforcing in membrane computing [Articolo su rivista]
Cavaliere, M.; Jonoska, N.
abstract

Motivated by biochemistry and the non-deterministic reactions between molecules, the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems (fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second case the membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders. © 2003 Kluwer Academic Publishers.

2003 - Modelling biological processes by using a probabilistic P system software [Articolo su rivista]
Ardelean, I. I.; Cavaliere, M.
abstract

In this paper we present a probabilistic P system simulator that implements the evolution-communication model proposed in (Cavaliere, 2003) enriched with some probabilistic parameters inspired by the cell biology. After describing the software and its working, we compare the mathematical model used with the biological reality of the cell. Then, we present some mathematical and biological applications showing how one can use this software to simulate simple but interesting biological phenomena, related to respiration and photosynthesis processes in some bacteria. © 2003 Kluwer Academic Publishers.