The Program Committee selected 23 out of 41 papers submitted to Petri Nets 2020 by authors from 19 different countries.Each paper was reviewed by three reviewers.After the conference, five papers were distinguished by the Program Committee members.The authors were invited to revise and extend their conference papers for this special issue, and the extended submissions have been reviewed in a separate reviewing process, to meet the standards of Fundamenta Informaticae.Three of these works address the synthesis problem, albeit from rather different points of views (complexity, compositionality and synthesis in a timed context).New results on the complexity and expressiveness of Recursive Petri nets and an in-depth investigation of the intricate connection between sequential and concurrent semantics in Petri nets reversibility, complete this special issue.

Finding good variable orders for decision diagrams is essential for their effective use. We consider Multiway Decision Diagrams (MDDs) encoding a set of fixed-size vectors satisfying a set of linear invariants. Two critical applications of this problem are encoding the state space of a discrete-event discrete state system (DEDS) and encoding all solutions to a set of integer constraints. After studying the relations between the MDD structure and the constraints imposed by the linear invariants, we define i $$_\mathrm {Rank}$$ , a new variable order metric that exploits the knowledge embedded in these invariants. We evaluate i $$_\mathrm {Rank}$$ against other previously proposed metrics on a benchmark of 40 different DEDS and show that it is a better predictor of the MDD size and it is better at driving heuristics for the generation of good variable orders.

Summary: Short reads sequencing technology has been used for more than a decade now. However, the analysis of RNAseq and ChIPseq data is still computational demanding and the simple access to raw data does not guarantee results reproducibility between laboratories. To address these two aspects, we developed SeqBox, a cheap, efficient and reproducible RNAseq/ChIPseq hardware/software solution based on NUC6I7KYK mini-PC (an Intel consumer game computer with a fast processor and a high performance SSD disk), and Docker container platform. In SeqBox the analysis of RNAseq and ChIPseq data is supported by a friendly GUI. This allows access to fast and reproducible analysis also to scientists with/without scripting experience. Availability and implementation: Docker container images, docker4seq package and the GUI are available at http://www.bioinformatica.unito.it/reproducibile.bioinformatics.html. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: RNA-Seq provides remarkable power in the area of biomarkers discovery and disease characterization. Two crucial steps that affect RNA-Seq experiment results are Library Sample Preparation (LSP) and Bioinformatics Analysis (BA). This work describes an evaluation of the combined effect of LSP methods and BA tools in the detection of splice variants. RESULTS: Different LSPs (TruSeq unstranded/stranded, ScriptSeq, NuGEN) allowed the detection of a large common set of splice variants. However, each LSP also detected a small set of unique transcripts that are characterized by a low coverage and/or FPKM. This effect was particularly evident using the low input RNA NuGEN v2 protocol. A benchmark dataset, in which synthetic reads as well as reads generated from standard (Illumina TruSeq 100) and low input (NuGEN) LSPs were spiked-in was used to evaluate the effect of LSP on the statistical detection of alternative splicing events (AltDE). Statistical detection of AltDE was done using as prototypes for splice variant-quantification Cuffdiff2 and RSEM-EBSeq. As prototype for exon-level analysis DEXSeq was used. Exon-level analysis performed slightly better than splice variant-quantification approaches, although at most only 50% of the spiked-in transcripts was detected. The performances of both splice variant-quantification and exon-level analysis improved when raising the number of input reads. CONCLUSION: Data, derived from NuGEN v2, were not the ideal input for AltDE, especially when the exon-level approach was used. We observed that both splice variant-quantification and exon-level analysis performances were strongly dependent on the number of input reads. Moreover, the ribosomal RNA depletion protocol was less sensitive in detecting splicing variants, possibly due to the significant percentage of the reads mapping to non-coding transcripts.

Abstract: This position paper introduces the concept of “artificial co-pilot ” (that is, a driver model), with a focus on driver’s oriented cognitive cars, in order to illustrate a new approach for future intelligent vehicles, which overcomes the limitations of nowadays models. The core consists in adopting the human cognitive frame-work for vehicles, following an artificial intelligent approach to take decisions. This paper illustrates in de-tails these concepts, as they are under development in the EU co-funded project HOLIDES. 1.

Abstract Summary: Chimera is a Bioconductor package that organizes, annotates, analyses and validates fusions reported by different fusion detection tools; current implementation can deal with output from bellerophontes, chimeraScan, deFuse, fusionCatcher, FusionFinder, FusionHunter, FusionMap, mapSplice, Rsubread, tophat-fusion and STAR. The core of Chimera is a fusion data structure that can store fusion events detected with any of the aforementioned tools. Fusions are then easily manipulated with standard R functions or through the set of functionalities specifically developed in Chimera with the aim of supporting the user in managing fusions and discriminating false-positive results. Availability and implementation: Chimera is implemented as a Bioconductor package in R. The package and the vignette can be downloaded at bioconductor.org. Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

The Hybrid Automata Stochastic Logic (HASL) has been recently defined as a flexible way to express classical performance measures as well as more complex, path-based ones (generically called "HASL formulas"). The considered paths are executions of Generalized Stochastic Petri Nets (GSPN), which are an extension of the basic Petri net formalism to define discrete event stochastic processes. The computation of the HASL formulas for a GSPN model is demanded to the COSMOS tool, that applies simulation techniques to the formula computation. Stochastic Symmetric Nets (SSN) are a high level Petri net formalism, of the colored type, in which tokens can have an identity, and it is well known that colored Petri nets allow one to describe systems in a more compact and parametric form than basic (uncolored) Petri nets. In this paper we propose to extend HASL and COSMOS to support colors, so that performance formulas for SSN can be easily defined and evaluated. This requires a new definition of the logic, to ensure that colors are taken into account in a correct and useful manner, and a significant extension of the COSMOS tool.

BACKGROUND: RNA-seq has the potential to discover genes created by chromosomal rearrangements. Fusion genes, also known as "chimeras", are formed by the breakage and re-joining of two different chromosomes. It is known that chimeras have been implicated in the development of cancer. Few publications in the past showed the presence of fusion events also in normal tissue, but with very limited overlaps between their results. More recently, two fusion genes in normal tissues were detected using both RNA-seq and protein data.Due to heterogeneous results in identifying chimeras in normal tissue, we decided to evaluate the efficacy of state of the art fusion finders in detecting chimeras in RNA-seq data from normal tissues. RESULTS: We compared the performance of six fusion-finder tools: FusionHunter, FusionMap, FusionFinder, MapSplice, deFuse and TopHat-fusion. To evaluate the sensitivity we used a synthetic dataset of fusion-products, called positive dataset; in these experiments FusionMap, FusionFinder, MapSplice, and TopHat-fusion are able to detect more than 78% of fusion genes. All tools were error prone with high variability among the tools, identifying some fusion genes not present in the synthetic dataset. To better investigate the false discovery chimera detection rate, synthetic datasets free of fusion-products, called negative datasets, were used. The negative datasets have different read lengths and quality scores, which allow detecting dependency of the tools on both these features. FusionMap, FusionFinder, mapSplice, deFuse and TopHat-fusion were error-prone. Only FusionHunter results were free of false positive. FusionMap gave the best compromise in terms of specificity in the negative dataset and of sensitivity in the positive dataset. CONCLUSIONS: We have observed a dependency of the tools on read length, quality score and on the number of reads supporting each chimera. Thus, it is important to carefully select the software on the basis of the structure of the RNA-seq data under analysis. Furthermore, the sensitivity of chimera detection tools does not seem to be sufficient to provide results consistent with those obtained in normal tissues on the basis of fusion events extracted from published data.

CSLTA is a stochastic temporal logic for continuous-time Markov chains (CTMC), that can verify the probability of following paths specified by a Deterministic Timed Automaton (DTA). A DTA expresses both logic and time constraints over a CTMC path, yielding to a very flexible way of describing performance and dependability properties. This paper explores a model checking algorithm for CSLTAbased on the translation into a Deterministic and Stochastic Petri Net (DSPN). The algorithm has been implemented in a simple Model Checker prototype, that relies on existing DSPN solvers to do the actual numerical computations.

Markov chains are a well-known stochastic process that provide a balance between being able to adequately model the system's behavior and being able to afford the cost of the model solution. The definition of stochastic temporal logics like continuous stochastic logic (CSL) and its variant asCSL, and of their model-checking algorithms, allows a unified approach to the verification of systems, allowing the mix of performance evaluation and probabilistic verification. In this paper we present the stochastic logic CSLTA, which is more expressive than CSL and asCSL, and in which properties can be specified using automata (more precisely, timed automata with a single clock). The extension with respect to expressiveness allows the specification of properties referring to the probability of a finite sequence of timed events. A typical example is the responsiveness property "with probability at least 0.75, a message sent at time 0 by a system A will be received before time 5 by system B and the acknowledgment will be back at A before time 7", a property that cannot be expressed in either CSL or asCSL. We also present a model-checking algorithm for CSLTA.

Equivalence relations can be used to reduce the state space of a system model, thereby permitting more efficient analysis. We study backward stochastic bisimulation in the context of model checking continuous-time Markov chains against continuous stochastic logic (CSL) properties. While there are simple CSL properties that are not preserved when reducing the state space of a continuous-time Markov chain using backward stochastic bisimulation, we show that the equivalence can nevertheless be used in the verification of a practically significant class of CSL properties. We consider an extension of these results to Markov reward models and continuous stochastic reward logic. Furthermore, we identify the logical properties for which the requirement on the equality of state-labeling sets (normally imposed on state equivalences in a model-checking context) can be omitted from the definition of the equivalence, resulting in a better state-space reduction

Reuse is a well-known and widely accepted principle in design and programming, that is instantiated through two main means: modularity and inheritance. Modularity allows a function or a data type and associated functions to be reused, while inheritance is based on the idea that a set of common features of a type can be factorized into a common supertype. While modularity has been widely exploited in performance and dependability modelling, inheritance is instead pretty much a "still-to-investigate" topic for this field. We discuss the role of inheritance in stochastic Petri nets (SPN) modelling, by considering a representation of the fault, error, and failure (FEF) chain based on hierarchies of classes (in the class diagram formalism of UML) and corresponding hierarchies of SPN models.

This paper presents a case study on the combined use of different tools and techniques for the validation and evaluation, from, the early stages of the design, of a fault tolerant software mechanism named distributed synchronization. The mechanism has been specified using UML state charts and sequence diagrams. A number of stochastic well-formed nets (SWN) models have been derived from the specifications: they have been composed using the tool algebra, and the resulting model has been model-checked using the PROD tool for temporal logic properties, thanks to a GreatSPN-to-PROD translator. The quantitative analysis has been performed using the SWN solvers of the Great-SPN tool.

Discusses the lessons learned in the modeling of a software fault tolerance solution built by a consortium of universities and industrial companies for an Esprit project called TIRAN (TaIlorable fault-toleRANce framework for embedded applications). The requirements of high flexibility and modularity for the software have lead to a modeling approach that is strongly based on compositionality. Since the interest was in assessing both the correctness and the performance of the proposed solution, we have cared for these two aspects at the same time, and, by means of an example, we show how this was a central aspect of our analysis.

We present a new approximation algorithm based on an exact representation of the state space S, using decision diagrams, and of the transition rate matrix R, using Kronecker algebra, for a Markov model with K submodels. Our algorithm builds and solves K Markov chains, each corresponding to a different aggregation of the exact process, guided by the structure of the decision diagram, and iterates on their solution until their entries are stable. We prove that exact results are obtained if the overall model has a product-form solution. Advantages of our method include good accuracy, low memory requirements, fast execution times, and a high degree of automation, since the only additional information required to apply it is a partition of the model into the K submodels. As far as we know, this is the first time an approximation algorithm has been proposed where knowledge of the exact state space is explicitly used.

We present new algorithms for the solution of large structured Markov models whose infinitesimal generator can be expressed as a Kronecker expression of sparse matrices. We then compare them with the shuffle-based method commonly used in this context and show how our new algorithms can be advantageous in dealing with very sparse matrices and in supporting both Jacobi-style and Gauss-Seidel-style methods with appropriate multiplication algorithms. Our main contribution is to show how solution algorithms based on Kronecker expression can be modified to consider probability vectors of size equal to the “actual” state space instead of the “potential” state space, thus providing space and time savings. The complexity of our algorithms is compared under different sparsity assumptions. A nontrivial example is studied to illustrate the complexity of the implemented algorithms.

Asynchronously communicating stochastic modules (SAM) are Petri nets that can be seen as a set of modules that communicate through buffers, so they are not (yet another) Petri net subclass, but they complement a net with a structured view. This paper considers the problem of exploiting the compositionality of the view to generate the state space and to find the steady-state probabilities of a stochastic extension of SAM in a net-driven, efficient way. Essentially we give an expression of an auxiliary matrix, G, which is a supermatrix of the infinitesimal generator of a SAM. G is a tensor algebra expression of matrices of the size of the components for which it is possible to numerically solve the characteristic steady-state solution equation /spl pi//spl middot/G=0, without the need to explicitly compute G. Therefore, we obtain a method that computes the steady-state solution of a SAM without ever explicitly computing and storing its infinitesimal generator, and therefore without computing and storing the reachability graph of the system. Some examples of application of the technique are presented and compared to previous approaches.

No abstract available.

Generalized stochastic Petri nets (GSPNs) are used to study the performances of several dynamic polling orders in symmetric multiserver multiqueue systems with one-buffer queues and Markovian interarrival, service, and walk times. Exact numerical results are obtained by means of Great-SPN, a software tool for the analysis of GSPNs, and are presented as curves of the average customer delay and waiting time. The results quantify the performance differences among the various polling orders, and show that the usual cyclic order can be the most effective, if the possibility of shorter walk times in the cyclic cases is adequately taken into account.>

The authors consider symmetric multiserver multiqueue systems in the cases of exhaustive and gated service disciplines, and present exact analytical results for the average server cycle and vacation times, as well as approximate closed-form expressions for the average customer waiting time, thus complementing the results obtained by the same authors (1990) for the one-limited service discipline. Arrival processes at each queue are assumed to be Poisson, with the same rate for all queues; service times and walk times are modeled with independent, identically distributed random variables with arbitrary distributions. The two cases in which at most one server or any number of servers can simultaneously attend a queue are considered.>

A study of multiserver multiqueue systems, i.e., queuing systems comprising a set of waiting lines where customers arrive to be served by a pool of servers, is described. Servers cyclically move from one queue to another, and provide service to at most one waiting customer per visit to a queue. Such (1-limited) multiserver polling models are analyzed. Attention is restricted to the case where the movement of the servers from queue to queue takes place in zero time. Two different server utilization policies are considered, and exact results are presented for the average customer waiting time and delay in the simpler case, while simple upper and lower bounds and a very accurate approximation are proposed for the more complex policy. In both cases systems are assumed to be symmetrical, arrivals are taken to be Poisson, and service times exponential.>

An analysis of polling schemes with multiple servers is presented where the service discipline at each station is assumed to be of the nonexhaustive (limited) type, i.e. no more than one customer can be removed from a station per visit of a server. The times spent by servers to walk from station to station are assumed to be nonzero and are modeled by independent, identically distributed random variables. The arrival processes at each queue are assumed to be Poisson, and serving times are modeled with independent, identically distributed random variables with arbitrary PDF. The case in which at most one server and the case in which any number of servers can simultaneously attend a queue are separately considered. Under the assumption of balanced traffic (equal arrival rates at all stations), several results concerning the cycle analysis and the stability of such schemes are obtained. A simple, explicit expression that gives an approximation for the steady-state average customer waiting time is derived.>