Search

In this paper we investigate a potential use of fluid approximation techniques in the context of stochastic model checking of CSL formulae. We focus on properties describing the behaviour of a single agent in a (large) population of agents, exploiting a limit result known also as fast simulation. In particular, we will approximate the behaviour of a single agent with a time-inhomogeneous CTMC which depends on the environment and on the other agents only through the solution of the fluid differential equation. We will prove the asymptotic correctness of our approach in terms of satisfiability of CSL formulae and of reachability probabilities. We will also present a procedure to model check time-inhomogeneous CTMC against CSL formulae.

We consider an asynchronous all optical packet switch (OPS) where each link consists of N wavelength channels and a pool of C ≤ N full range tunable wavelength converters. Under the assumption of Poisson arrivals with rate λ (per wavelength channel) and exponential packet lengths, we determine a simple closed-form expression for the limit of the loss probabilities P loss (N) as N tends to infinity (while the load and conversion ratio σ=C/N remains fixed). More specifically, for σ ≤ λ 2 the loss probability tends to (λ 2 -σ)/λ(1+λ), while for σ > λ 2 the loss tends to zero. We also prove an insensitivity result when the exponential packet lengths are replaced by certain classes of phase-type distributions. A key feature of the dynamical system (i.e., set of ODEs) that describes the limit behavior of this OPS switch, is that its right-hand side is discontinuous. To prove the convergence, we therefore had to generalize some existing result to the setting of piece-wise smooth dynamical systems.

This paper presents an analytical model for the performance prediction of queueing networks with batch services and batch arrivals, related to the fluid limit of a suitable single-parameter sequence of continuous-time Markov chains and interpreted as the deterministic approximation of the average behaviour of the stochastic process. Notably, the underlying system of ordinary differential equations exhibits discontinuities in the right-hand sides, which however are proven to yield a meaningful solution. A substantial numerical assessment is used to study the quality of the approximation and shows very good accuracy in networks with large job populations.

Tumors constitute a wide family of diseases kinetically characterized by the co-presence of multiple spatio-temporal scales. So, tumor cells ecologically interplay with other kind of cells, e.g. endothelial cells or immune system effectors, producing and exchanging various chemical signals. As such, tumor growth is an ideal object of hybrid modeling where discrete stochastic processes model agents at low concentrations, and mean-field equations model chemical signals. In previous works we proposed a hybrid version of the well-known Panetta-Kirschner mean-field model of tumor cells, effector cells and Interleukin-2. Our hybrid model suggested -at variance of the inferences from its original formulation- that immune surveillance, i.e. tumor elimination by the immune system, may occur through a sort of side-effect of large stochastic oscillations. However, that model did not account that, due to both chemical transportation and cellular differentiation/division, the tumor-induced recruitment of immune effectors is not instantaneous but, instead, it exhibits a lag period. To capture this, we here integrate a mean-field equation for Interleukins-2 with a bi-dimensional delayed stochastic process describing such delayed interplay. An algorithm to realize trajectories of the underlying stochastic process is obtained by coupling the Piecewise Deterministic Markov process (for the hybrid part) with a Generalized Semi-Markovian clock structure (to account for delays). We (i) relate tumor mass growth with delays via simulations and via parametric sensitivity analysis techniques, (ii) we quantitatively determine probabilistic eradication times, and (iii) we prove, in the oscillatory regime, the existence of a heuristic stochastic bifurcation resulting in delay-induced tumor eradication, which is neither predicted by the mean-field nor by the hybrid non-delayed models.

We demonstrate the modelling of opportunistic networks using the process algebra stochastic HYPE. Network traffic is modelled as continuous flows, contact between nodes in the network is modelled stochastically, and instantaneous decisions are modelled as discrete events. Our model describes a network of stationary video sensors with a mobile ferry which collects data from the sensors and delivers it to the base station. We consider different mobility models and different buffer sizes for the ferries. This case study illustrates the flexibility and expressive power of stochastic HYPE. We also discuss the software that enables us to describe stochastic HYPE models and simulate them., In Proceedings QAPL 2012, arXiv:1207.0559

Spearman distance is a permutation distance which might be used for codes in permutations beside Kendall distance. However, Spearman distance gives rise to a geometry of strings, which is rather unruly from the point of view of error correction and error detection. Special care has to be taken to discriminate between the two notions of codeword distance and codeword distinguishability. This stresses the importance of rejuvenating the latter notion, extending it from Shannon's zero-error information theory to the more general setting of metric string distances.

We compare population models in terms of Continuous Time Markov Chains with embedded deterministic delays (delayed CTMC), in which an exponential timed transition can only update the state of the system after a deterministicdelay, and delay differential equations (DDE). We prove a fluid approximation theorem, showing that, when the size of the population goes to infinity, the delayed CTMC converges to a solution of the DDE.

Fluid flow approximation allows efficient analysis of large scale PEPA models. Given a model, this method outputs how the mean, variance, and any other moment of the model’s stochastic behaviour evolves as a function of time. We investigate whether the method’s results, i.e. moments of the behaviour, are sufficient to capture system’s actual dynamics.We ran a series of experiments on a client-server model. For some parametrizations of the model, the model’s behaviour can accurately be characterized by the fluid flow approximations of its moments. However, the experiments show that for some other parametrizations, these moments are not sufficient to capture the model’s behaviour, highlighting a pitfall of relying only on the results of fluid flow analysis. The results suggest that the sufficiency of the fluid flow method for the analysis of a model depends on the model’s concrete parametrization. They also make it clear that the existing criteria for deciding on the sufficiency of the fluid flow method are not robust.

We consider the behaviour of sequences of Continuous Time Markov Chains (CTMC) based models of systems of interacting entities, for increasing population levels, in situations when some transitions of the system have rates that are discontinuous functions. This can happen, for instance, in presence of guarded actions. In this setting, standard deterministic approximation results do not apply. However, one can still derive a differential equation by syntactic means, de facto defining an hybrid (piecewise-smooth) dynamical system. We prove that the sequence of CTMC converges to the trajectories of this hybrid dynamical system, under (mild) regularity conditions on these limit trajectories.

The process algebra HYPE was recently proposed as a fine-grained modelling approach for capturing the behaviour of hybrid systems. In the original proposal, each flow or influence affecting a variable is modelled separately and the overall behaviour of the system then emerges as the composition of these flows. The discrete behaviour of the system is captured by instantaneous actions which might be urgent, taking effect as soon as some activation condition is satisfied, or non-urgent meaning that they can tolerate some (unknown) delay before happening. In this paper we refine the notion of non-urgent actions, to make such actions governed by a probability distribution. As a consequence of this we now give HYPE a semantics in terms of Transition-Driven Stochastic Hybrid Automata, which are a subset of a general class of stochastic processes termed Piecewise Deterministic Markov Processes., Comment: In Proceedings QAPL 2011, arXiv:1107.0746

We adopt a description of natural languages in terms of strings of crosslinguistically variable syntactic features (parameters), complying with a specified hypothesis of “universal grammar”, and we deal with two problems: first, assessing the statistical significance of language distances calculated on the basis of such features and recently used to reconstruct phylogenetic trees; second, counting the minimal overall number of possible human languages, i.e. of strings satisfying the implicational rules which describe dependencies between parameters of the specified universal grammar. In order to accomplish these tasks, we had to develop a sampling algorithm capable of dealing correctly with such rules. The potential significance of these results for historical and theoretical linguistics is then briefly highlighted.

Hybrid Systems are dynamical systems presenting both discrete and continuous evolution. Hybrid Automata are a formal model for hybrid systems, originally proposed to study embedded systems, where a discrete control acts on a continuously changing environment.

In order to circumvent the problem of state-space explosion of large-scale Markovian models, the stochastic process algebra PEPA has been given a fluid semantics based on ordinary differential equations, treating all entities as continuous. However, low numbers of instances and/or relatively slow dynamics may make such approximation too coarse for some parts of the system. To deal with such situations, we propose an hybrid semantics lying between these two extremes, treating parts of the system as discrete and stochastic and others as continuous and deterministic. The underlying mathematical object for the quantitative evaluation is a stochastic hybrid automaton. A case study of a client/server system with breakdowns and repairs is used to discuss the accuracy and the cost of this hybrid analysis.

We provide Stochastic Concurrent Constraint Programming (sCCP), a stochastic process algebra based on CCP, with a semantics in terms of hybrid automata. We associate with each sCCP program both a stochastic and a non-deterministic hybrid automaton. Then, we compare such automata with the standard stochastic semantics (given by a Continuous Time Markov Chain) and the one based on ordinary differential equations, obtained by a fluid-flow approximation technique. We discuss in detail two case studies: Repressilator and the Circadian Clock, with particular regard to the robustness exhibited by the different semantic models and to the effect of discreteness in dynamical evolution of such systems.

We investigate the limit behavior of a class of stochastic hybrid systems obtained by hybrid approximation of Stochastic Concurrent Constraint Programming (sCCP). We prove that a sequence of Continuous Time Markov Chain (CTMC), constructed from sCCP programs parametrically with respect to a notion of system size, converges a.s., in the limit of divergent size, to the hybrid approximation.

We present a technique to associate to stochastic programs written in stochastic Concurrent Constraint Programming a semantics in terms of a lattice of hybrid automata. The aim of this construction is to provide a framework to approximate the stochastic behavior by a mixed discrete/continuous dynamics with a variable degree of discreteness.

Several process algebras for modelling hybrid systems have appeared in the literature in recent years. These all assume that continuous variables in the system are modelled monolithically, often with the differential equations embedded explicitly in the syntax of the process algebra expression. In HYPE an alternative approach is taken which offers finer-grained modelling with each flow or influence affecting a variable modelled separately. The overall behaviour then emerges as the composition of these flows. This approach is supported by an operational semantics which distinguishes states as collections of flows and which is supported by an equivalence which satisfies the property that bisimilar HYPE models give rise to the same sets of continuous behaviours.

We present an application of stochastic Concurrent Constraint Programming (sCCP) for modeling biological systems. We provide a library of sCCP processes that can be used to describe straightforwardly biological networks. In the meanwhile, we show that sCCP proves to be a general and extensible framework, allowing to describe a wide class of dynamical behaviours and kinetic laws.

We put forward a method to map stochastic π-calculus processes in chemical ground form into hybrid automata, a class of dynamical systems with both discrete and continuous evolution. The key ingredient is the separation of control and molecular terms, which turns out to be related to the conservation properties of the system.

HYPE is a process algebra developed to model hybrid systems – systems that show both continuous and discrete behaviour. It is novel because it allows for the modelling of individual flows which means that subcomponents can be modelled in terms of these flows and do not need to be described monolithically. Biological systems display discrete behaviour inherently, but modellers may choose to model systems in a hybrid fashion, often to deal with differences in scale. We demonstrate how HYPE can be used to model the Repressilator.

We present a technique to approximate models of biological systems written in a “distilled” version of stochastic Concurrent Constraint Programming (sCCP), a stochastic programming methodology based on logic programming. Our technique automatically associates to a stochastic model an hybrid automaton, i.e. a dynamical system where continuous and discrete dynamics coexist. The hybrid automata generated in this way are, in certain cases, capable of capturing aspects of the dynamics of stochastic processes that are lost in approximations based solely on ordinary differential equations. In particular, they work better for those systems whose sCCP model contains explicit logical mechanisms of control. In the paper we outline the general technique to perform this association and we discuss some issues related to its applicability.

Ill-defined strings often occur in soft sciences, e.g. in linguistics or in biology. In this paper we consider \ell-length strings which have in each position one of the three symbols 0 or false, 1 or true, \flat or irrelevant. We tackle some generalisations of the usual Hamming distance between binary crisp strings which were recently used in computational linguistics. We comment on their metric properties, since these should guide the selection of the clustering algorithm to be used for language classification. The concluding section is devoted to future work, and the string approach, as currently pursued, is compared to alternative approaches.

Background Reduced representations of proteins have been playing a keyrole in the study of protein folding. Many such models are available, with different representation detail. Although the usefulness of many such models for structural bioinformatics applications has been demonstrated in recent years, there are few intermediate resolution models endowed with an energy model capable, for instance, of detecting native or native-like structures among decoy sets. The aim of the present work is to provide a discrete empirical potential for a reduced protein model termed here PC2CA, because it employs a PseudoCovalent structure with only 2 Centers of interactions per Amino acid, suitable for protein model quality assessment. Results All protein structures in the set top500H have been converted in reduced form. The distribution of pseudobonds, pseudoangle, pseudodihedrals and distances between centers of interactions have been converted into potentials of mean force. A suitable reference distribution has been defined for non-bonded interactions which takes into account excluded volume effects and protein finite size. The correlation between adjacent main chain pseudodihedrals has been converted in an additional energetic term which is able to account for cooperative effects in secondary structure elements. Local energy surface exploration is performed in order to increase the robustness of the energy function. Conclusion The model and the energy definition proposed have been tested on all the multiple decoys' sets in the Decoys'R'us database. The energetic model is able to recognize, for almost all sets, native-like structures (RMSD less than 2.0 Å). These results and those obtained in the blind CASP7 quality assessment experiment suggest that the model compares well with scoring potentials with finer granularity and could be useful for fast exploration of conformational space. Parameters are available at the url: http://www.dstb.uniud.it/~ffogolari/download/.

We introduce a data structure, the Bundled Suffix Tree (BUST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet Σ together with a non-transitive relation ≈ among its letters. Following the path of a substring β within a BUST, constructed over a text α of length n, not only the positions of the exact occurrences of β in α are found (as in a ST), but also the positions of all the substrings α1, α2, α3 ⋯ that are related with β via the relation ≈ among the characters of ∑, for example strings at a certain “distance” from β. A BuST contains O(n 1+δ) additional nodes (δ < 1) in probability, and is constructed in O(n 1+δ) steps. In the worst case it contains O(n 2) nodes. Please use the following format when citing this chapter: Bortolussi, L., Fabris, F., Policriti, A., 2006, in International Federation for Information Processing, Volume 209, Fourth IFIP International Conference on Theoretical Computer Science-TCS 2006, eds. Navarro, G., Bertossi, L., Kohayakwa, Y., (Boston: Springer). pp. 91–102.

We deal with DNA combinatorial code constructions, as found in the literature, taking the point of view of possibilistic information theory and possibilistic coding theory. The possibilistic framework allows one to tackle an intriguing information-theoretic question: what is channel noise in molecular computation? We examine in detail two representative DNA string distances used for DNA code constructions and point out the merits of the first and the demerits of the second. The two string distances are based on the reverse Hamming distance as required to account for hybridisation of DNA strings.

We present a stochastic version of Concurrent Constraint Programming (CCP), where we associate a rate to each basic instruction that interacts with the constraint store. We give an operational semantic that can be provided either with a discrete or a continuous model of time. The notion of observables is discussed, both for the discrete and the continuous version, and a connection between the two is given. Finally, a possible application for modeling biological networks is presented.

We re-take a coding theoretic notion which goes back to Cl. Shannon: codeword distinguishability. This notion is standard in zero-error information theory, but its bearing is definitely wider and it may help to better understand new forms of coding, e.g. DNA word design. In our approach, the underlying decoding principle is very simple and very general: one decodes by trying to minimise the diversity (in the simplest case the Hamming distance) between a codeword and the output sequence observed at the end of the noisy transmission channel. Symmetrically and equivalently, one may use maximum-similarity decoders and and codeword confusabilities. The operational meaning of codewoord distinguishability is made clear by a reliability criterion, which generalises the well-known criterion on minimum Hamming distance for error-correcting codes. We investigate the formal properties of distinguishabilities versus diversities; these two notions are deeply related, and yet essentially different. An encoding theorem is put forward; as a case study we examine a channel of cryptographic interest.

We present a version of the CCP paradigm, which is both distributed and probabilistic. We consider networks with a fixed number of nodes, each of them possessing a local and independent constraint store. While locally the computations evolve asynchronously, following the usual rules of (probabilistic) CCP, the communications among different nodes are synchronous. There are channels, and through them different objects can be exchanged: constraints, agents and channel themselves. In addition, all this activities are embedded in a probabilistic scheme based on a discrete model of time, both locally and globally. Finally we enhance the language with the capability of performing an automatic remote synchronization of variables belonging to different constraint stores.

My research interests are mainly focused on concurrent approaches to global optimization problems. Optimization tasks have two main conflicting features: they are both very difficult and central to a lot of the applications computer science faces daily. The problems I'm most interested in stem out from biology, protein folding being the principal one.

In this paper we analyze, mainly in a finitary setting, the consistency properties of fuzzy possibilities, interpreting them as instances of upper previsions and applying the basic notions of avoiding sure loss and coherence from the theory of imprecise probabilities. It ensues that fuzzy possibilities always avoid sure loss, but satisfy the stronger coherence condition only in a special case. Their natural extension, i.e. their least-committal correction to a coherent upper prevision, is determined. The same analysis is then performed when min is replaced in the definition of fuzzy possibility by a T–norm or, more generally, a seminorm, showing that the consistency properties and also the natural extension remain the same. Some "closure" properties are also discussed, which are guaranteed to hold if the T–seminorm is continuous, and are satisfied by (ordinary) possibilities too.

We explore the relation between the stochastic semantic associated to stochastic Concurrent Constrain Programming (sCCP) and its fluid-flow approximation. Writing the master equation for a sCCP model, we can show that the fluid flow equation is a first-order approximation of the true equation for the average. Moreover, we introduce a second-order correction and first-order equations for the variance and the covariance.

pp. 55-64 We tackle the following problem: can one replace a real matrix by a stochastic matrix without altering the order relations between entries? We state a general criterion and a convenient necessary condition. The motivation for this work resides in applications to DNA word design.

We introduce a novel approach to automatically detect ineffective breathing efforts in patients in intensive care subject to assisted ventilation. The method is based on synthesising from data temporal logic formulae which are able to discriminate between normal and ineffective breaths. The learning procedure consists in first constructing statistical models of normal and abnormal breath signals, and then in looking for an optimally discriminating formula. The space of formula structures, and the space of parameters of each formula, are searched with an evolutionary algorithm and with a Bayesian optimisation scheme, respectively. We present here our preliminary results and we discuss our future research directions.\&nbsp

In this paper we present a sampling algorithm for constrained strings representing the state of parameters of a universal grammar. This sampling algorithm has been used to assess statistical significance of the parametric comparison method, a new syntax-based approach to reconstruct linguistic phylogeny.