Abstract:
We design a novel algorithm for solving Mean-Payoff Games (MPGs). Besides solving an MPG in the usual sense, our algorithm computes more information about the game, information that is important with respect to applications. The weights of the edges of an MPG can be thought of as a gained/consumed energy -- depending on the sign. For each vertex, our algorithm computes the minimum amount of initial energy that is sufficient for player Max to ensure that in a play starting from the vertex, the energy level never goes below zero. Our algorithm is not the first algorithm that computes the minimum sufficient initial energies, but according to our experimental study it is the fastest algorithm that computes them. The reason is that it utilizes the strategy improvement technique which is very efficient in practice.

Abstract:
To express temporal properties of dense-time real-valued signals, the Signal Temporal Logic (STL) has been defined by Maler et al. The work presented a monitoring algorithm deciding the satisfiability of STL formulae on finite discrete samples of continuous signals. The logic has been used to express and analyse biological systems, but it is not expressive enough to sufficiently distinguish oscillatory properties important in biology. In this paper we define the extended logic STL* in which STL is augmented with a signal-value freezing operator allowing us to express (and distinguish) detailed properties of biological oscillations. The logic is supported by a monitoring algorithm prototyped in Matlab. The monitoring procedure of STL* is evaluated on a biologically-relevant case study.

Abstract:
In this paper we present a tool that performs CUDA accelerated LTL Model Checking. The tool exploits parallel algorithm MAP adjusted to the NVIDIA CUDA architecture in order to efficiently detect the presence of accepting cycles in a directed graph. Accepting cycle detection is the core algorithmic procedure in automata-based LTL Model Checking. We demonstrate that the tool outperforms non-accelerated version of the algorithm and we discuss where the limits of the tool are and what we intend to do in the future to avoid them.

Abstract:
Computation of optimal cycle mean in a directed weighted graph has many applications in program analysis, performance verification in particular. In this paper we propose a data-parallel algorithmic solution to the problem and show how the computation of optimal cycle mean can be efficiently accelerated by means of CUDA technology. We show how the problem of computation of optimal cycle mean is decomposed into a sequence of data-parallel graph computation primitives and show how these primitives can be implemented and optimized for CUDA computation. Finally, we report a fivefold experimental speed up on graphs representing models of distributed systems when compared to best sequential algorithms.

Abstract:
In this paper a novel tool BioDiVinEfor parallel analysis of biological models is presented. The tool allows analysis of biological models specified in terms of a set of chemical reactions. Chemical reactions are transformed into a system of multi-affine differential equations. BioDiVinE employs techniques for finite discrete abstraction of the continuous state space. At that level, parallel analysis algorithms based on model checking are provided. In the paper, the key tool features are described and their application is demonstrated by means of a case study.

Abstract:
We propose a new framework for rigorous robustness analysis of stochastic biochemical systems that is based on probabilistic model checking techniques. We adapt the general definition of robustness introduced by Kitano to the class of stochastic systems modelled as continuous time Markov Chains in order to extensively analyse and compare robustness of biological models with uncertain parameters. The framework utilises novel computational methods that enable to effectively evaluate the robustness of models with respect to quantitative temporal properties and parameters such as reaction rate constants and initial conditions. We have applied the framework to gene regulation as an example of a central biological mechanism where intrinsic and extrinsic stochasticity plays crucial role due to low numbers of DNA and RNA molecules. Using our methods we have obtained a comprehensive and precise analysis of stochastic dynamics under parameter uncertainty. Furthermore, we apply our framework to compare several variants of two-component signalling networks from the perspective of robustness with respect to intrinsic noise caused by low populations of signalling components. We have successfully extended previous studies performed on deterministic models (ODE) and showed that stochasticity may significantly affect obtained predictions. Our case studies demonstrate that the framework can provide deeper insight into the role of key parameters in maintaining the system functionality and thus it significantly contributes to formal methods in computational systems biology.

Abstract:
In the last decade it became a common practice to formalise software requirements to improve the clarity of users' expectations. In this work we build on the fact that functional requirements can be expressed in temporal logic and we propose new sanity checking techniques that automatically detect flaws and suggest improvements of given requirements. Specifically, we describe and experimentally evaluate approaches to consistency and redundancy checking that identify all inconsistencies and pinpoint their exact source (the smallest inconsistent set). We further report on the experience obtained from employing the consistency and redundancy checking in an industrial environment. To complete the sanity checking we also describe a semi-automatic completeness evaluation that can assess the coverage of user requirements and suggest missing properties the user might have wanted to formulate. The usefulness of our completeness evaluation is demonstrated in a case study of an aeroplane control system.

In 2011, Chinese researcher Ni found
the solution of the Oppenheimer-Volkoff problem for a stable configuration of
stellar object with no internal source of energy. The Ni’s solution is the
nonrotating hollow sphere having not only an outer, but an inner physical
radius as well. The upper mass of the object is not constrained. In our paper,
we contribute to the description of the solution. Specifically, we give the
explicit description of metrics inside the object and attempt to link it with
that in the corresponding outer Schwarzschild solution of Einstein field
equations. This task appears to be non-trivial. We discuss the problem and
suggest a way how to achieve the continuous linkup of both object-interior and
outer-Schwarzschild metrics. Our suggestion implies an important fundamental
consequence: there is no universal relativistic speed limit, but every compact
object shapes the adjacent spacetime and this action results in the specific
speed limit for the spacetime dominated by the object. Regardless our
suggestion will definitively be proved or the successful linkup will also be
achieved in else, still unknown way, the success in the linkup represents a
constraint for the physical acceptability of the models of compact objects.

The metrics of the compact
objects should be the continuous function of coordinates. The metrics inside
every object is set by its internal structure. The metrics in the adjacent
empty space is described by the outer Schwarzschild or Kerr solution of the
Einstein field equations. It appears that the linkup of both object-interior
and empty-space metrics is not continuous at the physical surfaces of the
objects for the common, generally (by convention) accepted set of assumptions.
We suggest the new way of how to achieve the success in the linkup, which does
not assume the higher value of the relativistic speed limit in the empty space
governed by the object, in contrast to our previous suggestion. We also give a
more detailed explanation of the existence of inner physical surface of compact
objects and suggest the way of the linkup of metrics in this surface. To achieve
the continuous linkup, we assume a lower value of the speed limit in the
object’s interior as well as a new gauging of the outer Schwarzschild solution
for the inner empty space of the object. Newly established gauging constants
are calculated and the success of the linkup is shown in several examples. The
new gauging implies a lower gravitational attraction (lower gravitational
constant) in the inner empty space in comparison with that in the outer space,
which is measured in the common, observed, gravitational interactions of
material objects.