1,721,020 research outputs found
New solvers for asymmetric systems in GreatSPN
No full textIn this paper we present the extended symbolic reachability graph/dynamic symbolic reachability graph (ESRG/DSRG) framework to model and solve (asymmetric) SWN models. This framework combines several tools: GreatSPN for the model design, WNESRG to build the ESRG of the designed model, ESRG2MC to refine the ESRG and generate the corresponding MC, WNDSRG to build the DSRG and the corresponding MC. MCSolver is used to solve the MC and compute the steady state marking probability. The following section is dedicated to the detailed presentation of this new framework
MODIMO: Workshop on Multi-Omics Data Integration for Modelling Biological Systems
No full textMulti-omics analysis aims at extracting previously uncovered biological knowledge by integrating information across multiple single-omic sources. Past approaches have focused on the simultaneous analysis of a small number of omic data sets. Current challenges face the problem of integrating multiple omic sources into a unified complex model, or of combining already available tools for two-by-two omics analyses and merging their outcomes. By doing so and leveraging integrated system-level knowledge, multi-omic approaches ought to enable the development of better qualitative and quantitative models for descriptive and predictive analyses. To move this area forward, new statistical and algorithmic frameworks are needed, for example for generalizing classical graph theory results to heterogeneous networks and applying them to diverse problems such as drug repurposing or understanding the immune response to infections. Thus, in short, this workshop aims at investigating novel methodologies for providing crucial insights into multi-omics data management, integration, and analysis in order to enable biological discoveries
MDWNsolver: A Framework to Design and Solve Markov Decision Petri Nets
No full textMDWNsolver is a framework for system modeling and optimization of performability measures based on Markov Decision Petri Net (MDPN) and Markov Decision Well-formed Net (MDWN) formalisms, two Petri Net extensions for high level specification of Markov Decision Processes (MDP). It is integrated in the GreatSPN suite which provides a GUI to design MDPN/MDWN models. From the analysis point of view, MDWNsolver uses efficient algorithms that take advantage of system symmetries, thus reducing the analysis complexity. In this paper the MDWNsolver framework features and architecture are presented, and some application examples are discussed
An entropy heuristic to optimize decision diagrams for index-driven search in biological graph databases
Full text linkGraphs are a widely used structure for knowledge representation. Their uses range from biochemical to biomedical applications and are recently involved in multi-omics analyses. A key computational task regarding graphs is the search of specific topologies contained in them. The task is known to be NP-complete, thus indexing techniques are applied for dealing with its complexity. In particular, techniques exploiting paths extracted from graphs have shown good performances in terms of time requirements, but they still suffer because of the relatively large size of the produced index. We applied decision diagrams (DDs) as index data structure showing a good reduction in the indexing size with respect to other approaches. Nevertheless, the size of a DD is dependent on its variable order. Because the search of an optimal order is an NP-complete task, variable order heuristics on DDs are applied by exploiting domain-specific information. Here, we propose a heuristic based on the information content of the labeled paths. Tests on well-studied biological benchmarks, which are an essential part of multi-omics graphs, show that the resultant size correlates with the information measure related to the paths and that the chosen order allows to effectively reduce the index size
A framework to design and solve Markov Decision Well-formed Net models
No full textThe Markov decision process (MDP) (M.L. Puterman, 2005) formalism is widely used for modeling systems which exhibit both non deterministic and probabilistic behaviors (e.g. distributed systems, resource management systems, ...). Unfortunately, if the system is particularly complex then its modeling at the MDP level may be very hard; so in (M. Beccuti et al., 2007) a higher-level formalism called Markov decision well-formed net (MDWN) was proposed. The MDWN allows to describe the system in terms of its components and their interactions, while the MDP describes directly the state space and the state transitions. The MDWN model is more compact and readable: in particular, it is possible to define a complex non deterministic or probabilistic behavior as a composition of simpler non deterministic or probabilistic steps. In the MDWN formalism, the probabilistic behavior of the system is clearly distinct from the non deterministic one; actually they are designed as two separate Petri nets (PN): the probabilistic PN (N^pr) and the non deterministic PN (N^nd)
Parametric NdRFT for the derivation of optimal repair strategies
No full textNon deterministic Repairable Fault Trees (NdRFT) are a recently proposed modeling formalism for the study of optimal repair strategies: they are based on the widely adopted Fault Tree formalism, but in addition to the failure modes, NdRFTs allow to define possible repair actions. In a previous pa per the formalism has been introduced together with an analysis method and a tool allowing to automatically derive the best repair strategy to be applied in each state. The analysis technique is based on the generation and solution of a Markov Decision Process. In this paper we present an extension, ParNdRFT, that allows to exploit the presence of redundancy to reduce the complexity of the model and of the analysis. It is based on the translation of the ParNdRFT in to a Markov Decision Well-Formed Net, i.e. a model specified by means of an High Level Petri Net formalism. The translated model can be efficiently solved thanks to existing algorithms that generate a reduced state space automatically exploiting the model symmetries
Computing first passage time distributions in Stochastic Well-Formed Nets
No full textThe increasing demand for customer centric evaluation of systems, mostly related with the assessment of the quality of service that they can deliver, requires the development of techniques properly designed to model and to study the movement of specific entities generically referred to as "customers". Stochastic Well-Formed Net(SWN) are naturally suited for the representation of systems in which "customers" of different categories compete for the use of common resources. Color classes of SWN are easily associated with these different categories, leaving to the peculiar features of the formalism the possibility of exploiting all the symmetries existing into the representation for the efficient and effective computation of the measures of interest. Within this application context, the computation of first passage time distribution measures in Stochastic Well-Formed Net (SWN) is becoming of primary interest. Customers however are not primitive entities in the formalism and an approach similar to that previously developed for Generalized Stochastic Petri Nets (GSPN) is suggested to overcome this problem in which P-semiflows are used to identify the circulating "customers". In this paper we propose an original algorithm for computing some P-semiflows of colored PNs (in particular of SWNs) in parametric form by exploiting the peculiarities of the objective of this investigation, and extend the customer centric first passage time computation approach previously developed for GSPNs, to make it suitable for SWN models. Moreover, the paper proposes an enhancement of the SWN notation in order to provide a way to ease the modeler in the specification of customer scheduling policies that may affect the computation of first passage time distributions. This extension, inspired by Queueing Petri Nets, adds to SWN some "syntactic sugar" that allows to include in the model queueing places which are automatically replaced by appropriate submodels, before solving the model
Probe Automata for Passage Time Specification
No full textPassage time distribution has drawn increasing attention over the past years as an important measure to define and verify service level agreements. The definition of passage time requires the specification of a condition to start/stop the computation, and possibly of a restriction on the system behavior to be considered between start and stop. Different characterizations have been defined in the past, either state-based, action-based or a mix of the two, either for Markov chains, or for stochastic Petri nets and process algebras. In this paper we propose probe automata as a way to specify passage time for GSPNs that allows one to select entering, goal, and forbidden states, as well as paths of interest starting from any reachable state. The specification is in terms of conditions over the current marking, the transition (sequence) being fired, as well as over the marking reached through the firing. Probe automata subsume previous definitions of passage time for GSPNs and for Tagged GSPNs, the extension of GSPNs that was defined in the past for computing passage time of a {em tagged token} in a GSPN
Markov Decision Petri Net and Markov Decision Well-Formed Net Formalisms
No full textIn this work, we propose two high-level formalisms, Markov Decision Petri Nets (MDPNs) and Markov Decision Well-formed Nets (MDWNs), useful for the modeling and analysis of distributed systems with probabilistic and non deterministic features: these formalisms allow a high level representation of Markov Decision Processes. The main advantages of both formalisms are: a macroscopic point of view of the alternation between the probabilistic and the non deterministic behaviour of the system and a syntactical way to define the switch between the two behaviours. Furthermore, MDWNs enable the modeller to specify in a concise way similar components. We have also adapted the technique of the symbolic reachability graph, originally designed for Well-formed Nets, producing a reduced Markov decision process w.r.t. the original one, on which the analysis may be performed more efficiently. Our new formalisms and analysis methods are already implemented and partially integrated in the GreatSPN tool, so we also describe some experimental results
First Passage Time Computation in Tagged GSPN with Queue Places
No full textThis paper presents an extension of the generalized stochastic Petri net (GSPN) formalism that enables the computation of first passage time distributions. The tagged customer technique typical of queuing networks is adapted to the GSPN context by providing a formal definition and an automatic computation of the groups of tokens that can be identified as customers, i.e. classes of homogeneous entities behaving in a similar manner. Passage times are identified through the concept of events that correspond to the firing of transitions placed at the boundaries of a subnet. The extended model obtained with this specifications is translated into an ordinary GSPN by isolating a customer from the group and highlighting its path through the net thus obtaining a representation suited for the passage time analysis. Proofs are provided to show the equivalence between these models with respect to their steady-state distributions. An important and original aspect treated in this paper is the possibility of specifying several scheduling policies of tokens at places, an information not present in ordinary GSPN models, but that is vital for the precise computation of first passage time distributions as shown by a few results computed for a simple Flexible Manufacturing application
- …
