Blockchain technology has experienced significant advancements, with Proof-of-Stake emerging as a notable alternative to traditional Proof-of-Work blockchains. Among various PoS blockchain systems, Cosmos stands out as a prominent example due to its ecosystem designed to facilitate interoperability between different blockchains built on their platform through the Inter-Blockchain Communication protocol. What is more, Cosmos is operated by the unique consensus mechanism, namely CosmosBFT that supports multiple rounds for an agreement on block of the same height. This study examines the current state of blockchains within the Cosmos ecosystem, highlighting two major issues. First, we observe the multi-round performance in Cosmos blockchain using the process algebra tool to create our model featured non-homogeneous proposers. Second, we propose a method for determining optimal timeouts for the Propose step in any network within the ecosystem. In addition, we identify a skewed distribution of voting power among validators, favouring top-ranked members. This concentration of VP threatens the network’s decentralisation and immutability, as it allows a small group of members to potentially corrupt the consensus process. Our models, although parameterised for a particular Cosmos instance, are applicable to any blockchain that use the CometBFT protocol, offering valuable insights for enhancing efficiency of consensus mechanisms in the decentralised networks.

In application domains such as routing, network analysis, scheduling, and planning, directed graphs are widely used as both formal models and core data structures for the development of efficient algorithmic solutions. In these areas, graphs are often evolving in time: for example, connection links may fail due to temporary technical issues, meaning that edges of the graph cannot be traversed for some time interval and alternative paths have to be followed. In classical computation graphs have been implemented both explicitly through adjacency matrices/lists and symbolically as ordered binary decision diagrams. Moreover, ad-hoc visit procedures have been developed to deal with dynamically evolving graphs. Quantum computation, exploiting interference and entanglement, has provided an exponential speed-up for specific problems, e.g., database search and integer factorization. In the quantum framework everything must be represented and manipulated using reversible operators. This poses a challenge when one has to deal with traversals of dynamically evolving directed graphs. Graph traversals are not intrinsically reversible because of converging paths. In the case of dynamically evolving graphs also the creation/destruction of paths comes into play against reversibility. In this paper we propose a novel high level graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our procedure allows to encode any multigraph into a unitary matrix. We devise algorithms for computing the encoding that are optimal in terms of time and space and we show the effectiveness of the proposal with some examples. We describe how to react to edge/node failures in constant time. Furthermore, we present two methods to perform quantum random walks taking advantage of this encoding: with and without projectors. We implement and test our encoding obtaining that the theoretical bounds for the running time are confirmed by the empirical results and providing more details on the behavior of the algorithms over graphs of different densities.

Abstract The lack of purely Quantum Programming Languages constitutes a hurdle in the general description of quantum computational processes; the implementation is heavily dependent on the considered quantum computational model. To bypass the obstacle, this paper pursues a new direction, investigating the compilation of classical programming paradigms over different quantum computational models: Gate-Based, Measurement-Based and Adiabatic Quantum Computation. Since graphs can be exploited to describe both classical and quantum computations, the problem of graph encoding on quantum hardware is tightly connected to our purposes. As such, it holds a major relevance in our quest for quantum compilation. While studying these topics through the lenses of Graph Theory, declarative programming emerges as the ideal candidate for such endeavour. In this paper we consider some existing quantum computational models and for each of them we identify the main subtleties in the compilation of classical languages. In turn, we break these complexities down into easier problems to stimulate further developments in this area of research. As it turns out, the observations for each model differ widely. Nevertheless, as for the tasks here considered, no model seems to claim supremacy over the others. In contrast, declarative programming maintains the spot as the ideal candidate for quantum compilation, independently of the model.

Advancements in Neural Networks have led to larger models, challenging implementation on embedded devices with memory, battery, and computational constraints. Consequently, network compression has flourished, offering solutions to reduce operations and parameters. However, many methods rely on heuristics, often requiring re-training for accuracy. Model reduction techniques extend beyond Neural Networks, relevant in Verification and Performance Evaluation fields. This paper bridges widely-used reduction strategies with formal concepts like lumpability, designed for analyzing Markov Chains. We propose a pruning approach based on lumpability, preserving exact behavioral outcomes without data dependence or fine-tuning. Relaxing strict quotienting method definitions enables a formal understanding of common reduction techniques.

The field of tumor phylogenetics focuses on studying the differences within cancer cell populations. Many efforts are done within the scientific community to build cancer progression models trying to understand the heterogeneity of such diseases. These models are highly dependent on the kind of data used for their construction, therefore, as the experimental technologies evolve, it is of major importance to exploit their peculiarities. In this work we describe a cancer progression model based on Single Cell DNA Sequencing data. When constructing the model, we focus on tailoring the formalism on the specificity of the data. We operate by defining a minimal set of assumptions needed to reconstruct a flexible DAG structured model, capable of identifying progression beyond the limitation of the infinite site assumption. Our proposal is conservative in the sense that we aim to neither discard nor infer knowledge which is not represented in the data. We provide simulations and analytical results to show the features of our model, test it on real data, show how it can be integrated with other approaches to cope with input noise. Moreover, our framework can be exploited to produce simulated data that follows our theoretical assumptions. Finally, we provide an open source R implementation of our approach, called CIMICE, that is publicly available on BioConductor.

Abstract In this paper, we deal with the lumpability approach to cope with the state space explosion problem inherent to the computation of the stationary performance indices of large stochastic models. The lumpability method is based on a state aggregation technique and applies to Markov chains exhibiting some structural regularity. Moreover, it allows one to efficiently compute the exact values of the stationary performance indices when the model is actually lumpable. The notion of quasi-lumpability is based on the idea that a Markov chain can be altered by relatively small perturbations of the transition rates in such a way that the new resulting Markov chain is lumpable. In this case, only upper and lower bounds on the performance indices can be derived. Here, we introduce a novel notion of quasi-lumpability, named proportional lumpability, which extends the original definition of lumpability but, differently from the general definition of quasi-lumpability, it allows one to derive exact stationary performance indices for the original process. We then introduce the notion of proportional bisimilarity for the terms of the performance process algebra PEPA. Proportional bisimilarity induces a proportional lumpability on the underlying continuous-time Markov chains. Finally, we prove some compositionality results and show the applicability of our theory through examples.

SUMMARY: Whole genome assembly (WGA) of bacterial genomes with short reads is a quite common task as DNA sequencing has become cheaper with the advances of its technology. The process of assembling a genome has no absolute golden standard and it requires to perform a sequence of steps each of which can involve combinations of many different tools. However, the quality of the final assembly is always strongly related to the quality of the input data. With this in mind we built WGA-LP, a package that connects state-of-the-art programs for microbial analysis and novel scripts to check and improve the quality of both samples and resulting assemblies. WGA-LP, with its conservative decontamination approach, has shown to be capable of creating high quality assemblies even in the case of contaminated reads. AVAILABILITY AND IMPLEMENTATION: WGA-LP is available on GitHub (https://github.com/redsnic/WGA-LP) and Docker Hub (https://hub.docker.com/r/redsnic/wgalp). The web app for node visualization is hosted by shinyapps.io (https://redsnic.shinyapps.io/ContigCoverageVisualizer/). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this paper, we study an information flow security property for systems specified as terms of a quantitative Markovian process algebra, namely the Performance Evaluation Process Algebra (PEPA). We propose a quantitative extension of the Non-Interference property used to secure systems from the functional point view by assuming that the observers are able to measure also the timing properties of the system, e.g., the response time of certain actions or its throughput. We introduce the notion of Persistent Stochastic Non-Interference (PSNI) based on the idea that every state reachable by a process satisfies a basic Stochastic Non-Interference (SNI) property. The structural operational semantics of PEPA allows us to give two characterizations of PSNI: one based on a bisimulation-like equivalence relation inducing a lumping on the underlying Markov chain, and another one based on unwinding conditions which demand properties of individual actions. These two different characterizations naturally lead to efficient methods for the verification and construction of secure systems. A decision algorithm for PSNI is presented and an application of PSNI to a queueing system is discussed.

In this work we present parallelotope bundles, i.e., sets of parallelotopes for a symbolic representation of polytopes. We define a compact representation of these objects and show that any polytope can be canonically expressed by a bundle. We propose efficient algorithms for the manipulation of bundles. Among these, we define techniques for computing tight over-approximations of polynomial transformations. We apply our framework, in combination with the Bernstein technique, to the reachability problem for polynomial dynamical systems. The accuracy and scalability of our approach are validated on a number of case studies.

We consider the algorithmic problem of computing the maximal simulation preorder (and quotient) on acyclic labelled graphs. The acyclicity allows to exploit an inner structure on the set of nodes, that can be processed in stages according to a set-theoretic notion of rank. This idea, previously used for bisimulation computation, on the one hand improves on the performances of the ensuing procedure and, on the other hand, gives to the solution an orderly iterative flavour making the algorithmic idea more explicit. The computational complexity achieved is good as we obtain the best performing algorithm for simulation computation on acyclic graphs, in both time and space. © The Author, 2013. Published by Oxford University Press. All rights reserved.

We propose a mapping from a database conceptual design to a schema for XML that produces highly connected and nested XML structures. We first introduce two alternative definitions of the mapping, one modeling entities as global XML elements and expressing relationships among them in terms of keys and key references (flat design), the other one encoding relationships by properly including the elements for some entities into the elements for other entities (nest design). Then we provide a benchmark evaluation of the two solutions showing that the nest approach, compared to the flat one, leads to improvements in both query and validation performances. This motivates us to systematically investigate the best way to nest XML structures. We identify two different nesting solutions: a maximum depth nesting, that keeps low the number of costly join operations that are necessary to reconstruct information at query time using the mapped schema, and a maximum density nesting, that minimizes the number of schema constraints used in the mapping of the conceptual schema, thus reducing the validation overhead. On the one hand, the problem of finding a maximum depth nesting turns out to be NP-complete and, moreover, it admits no constant ratio approximation algorithm. On the other hand, we devise a graph-theoretic algorithm, NiduX, that solves the maximum density problem in linear time. Interestingly, NiduX finds the optimal solution for the harder maximum depth problem whenever the conceptual design graph is either acyclic or complete. In randomly generated intermediate cases of the graph topology, we experimentally show that NiduX finds a good approximation of the optimal solution.

Many systems, both natural and artificial, exhibit a mixed discrete-continuous behavior that cannot be fully captured by either continuous nor discrete models: they evolve in accordance to continuous laws, but these laws are controlled by a finite set of modes. Hybrid automata were proposed to represent such kind of behaviors and they have been used to model numerous natural phenomena in the last decades. Unfortunately, the Model Checking problem over them was proved undecidable and, because of that, many techniques were suggested so far to both approximate the original models and reduce the analysis complexity. This paper surveys some of such techniques and reports some open questions.

Product configuration systems are an emerging software technology that supports companies in deploying mass customization strategies. In this paper, we describe a CLP-based reasoning engine that we developed for a commercial configuration system. We

Lists, multisets, and sets are well-known data structures whose usefulness is widely recognized in various areas of computer science. They have been analyzed from an axiomatic point of view with a parametric approach in Dovier et al. [1998], where the relevant unification algorithms have been developed. In this article, we extend these results considering more general constraints, namely, equality and membership constraints and their negative counterparts.

We present a general unwinding framework for the definition of information flow security properties of concurrent programs, described in a simple imperative language enriched with parallelism and atomic statement constructors. We study different classes of programs obtained by instantiating the general framework and we prove that they entail the noninterference principle. Accurate proof techniques for the verification of such properties are defined by exploiting the Tarski decidability result for first-order formulae over the reals. Moreover, we illustrate how the unwinding framework can be instantiated in order to deal with intentional information release and we extend our verification techniques to the analysis of security properties of programs admitting downgrading.

Information flow security in a multilevel system aims at guaranteeing that no high level information is revealed to low level users, even in the presence of any possible malicious process. This requirement could be stronger than necessary when some knowledge about the environment (context) in which the process is going to run is available. To relax this requirement we introduce the notion of secure contexts for a class of processes. This notion is parametric with respect to both the observation equivalence and the operation used to characterize the low level view of a process. As observation equivalence we consider the cases of weak bisimulation and trace equivalence. We describe how to build secure contexts in these cases and we show that two well-known security properties, named BNDC and NDC, are just special instances of our general notion.

We propose an alternative way to represent graphs via OBDDs based on the observation that a partition of the graph nodes allows sharing among the employed OBDDs. In the second part of the paper we present a method to compute at the same time the quotient w.r.t. the maximum bisimulation and the OBDD representation of a given graph. The proposed computation is based on an OBDD-rewriting of the notion of Ackermann encoding of hereditarily finite sets into natural numbers.

Information flow security in a multilevel system aims at guaranteeing that no high level information is revealed to low level users, even in the presence of any possible malicious process. This requirement could be too demanding when some knowledge about the environment (context) in which the process is going to run is available. To deal with these simulations we introduce the notion of secure contexts for a class of processes. This notion is parametric with respect to both the observation equivalence and the operation used to characterize the low level behavior of a process. We mainly analyze the cases of bisimulation and trace equivalence. We describe how to build secure contexts in these cases and we show that two well-known security properties, named BNDC and NDC, are just special instances of our general notion.

The systematic development of complex systems usually relies on a stepwise refinement procedure from an abstract specification to a more concrete one that can finally be implemented. The use of refinement operators preserving system properties is clearly essential since it avoids properties to be re-investigated at each development step. In this paper, we formalize the notion of refinement for processes described as terms of the security process algebra (SPA). We consider several information flow security properties and provide sufficient conditions under which our refinement operators preserve such security properties. Finally, we study how refinements can be composed still preserving the security of the system.

Abstract We define an interpretation of modal languages with polyadic operators in modal languages that use monadic operators (diamonds) only. We also define a simulation operator which associates a logic Λsim in the diamond language with each logic Λ in the language with polyadic modal connectives. We prove that this simulation operator transfers several useful properties of modal logics, such as finite/recursive axiomatizability, frame completeness and the finite model property, canonicity and first-order definability.

We study the complexity of the Subgraph Bisimulation Problem, which relates to Graph Bisimulation as Subgraph Isomorphism relates to Graph Isomorphism, and we prove its NP-Completeness. Our analysis is motivated by its applications to semistructured databases.

In this paper we present a study of the problem of handling constraints made by conjunctions of positive and negative literals based on the predicate symbols =, ∈,∪ and || (i.e., disjointness of two sets) in a (hybrid) universe of finite sets . We also review and compare the main techniques considered to represent finite sets in the context of logic languages. The resulting contraint algorithms are embedded in a Constraint Logic Programming (CLP) language which provides finite sets—along with basic set-theoretic operations—as first-class objects of the language. The language—called CLP( SET )—is an instance of the general CLP framework, and as such it inherits all the general features and theoretical results of this scheme. We provide, through programming examples, a taste of the expressive power offered by programming in CLP( SET ).