Search

I show that in a standard process algebra extended with time-outs one can correctly model mutual exclusion in such a way that starvation-freedom holds without assuming fairness or justness, even when one makes the problem more challenging by assuming memory accesses to be atomic. This can be achieved only when dropping the requirement of speed independence. [ABSTRACT FROM AUTHOR]

The main objective of this article is to present a complete finite black-box testing theory for non-deterministic Kripke structures with possibly infinite input domains, but finite domains for internal state variables and outputs. To this end, an abstraction from Kripke structures of this sub-domain to finite state machines is developed. It is shown that every complete black-box testing theory for (deterministic or nondeterministic) finite state machines in the range of this abstraction induces a complete black-box input equivalence class partition testing (IECPT) theory for the Kripke structures under consideration. Additionally, it is shown that each of these IECPT theories can be combined with random testing, such that a random value is selected from an input equivalence class, whenever a representative from this class is required in a test step. Experiments have shown that this combination increases the test strength of equivalence class tests for systems under test (SUT) outside the fault domain, while we show here that this randomisation preserves the completeness property for SUT inside the domain. The investigations lead to several complete IECPT strategies which, to our best knowledge, were not known before for this sub-domain of Kripke structures. The elaboration and presentation of results is performed on a semantic level, so that the testing theories under consideration can be applied to models presented in any concrete formalism, whose behaviour is reflected by a member of our semantic category. [ABSTRACT FROM AUTHOR]

This paper presents an approach to P system verification using the Spin model checker. It proposes a P system implementation in PROMELA, the modeling language accepted by SPIN. It also provides the theoretical background for transforming the temporal logic properties expressed for the P system into properties of the executable implementation. Furthermore, a comparison between P systems verification using SPIN and NUSMV is realized. The results obtained show that the PROMELA implementation is more adequate, especially for verifying more complex models, such as P systems that model ecosystems. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents some testing approaches based on model checking and using different testing criteria. First, test sets are built from different Kripke structure representations. Second, various rule coverage criteria for transitional, non-deterministic, cell-like P systems, are considered in order to generate adequate test sets. Rule based coverage criteria (simple rule coverage, context-dependent rule coverage and variants) are defined and, for each criterion, a set of LTL (Linear Temporal Logic) formulas is provided. A codification of a P system as a Kripke structure and the sets of LTL properties are used in test generation: for each criterion, test cases are obtained from the counterexamples of the associated LTL formulas, which are automatically generated from the Kripke structure codification of the P system. The method is illustrated with an implementation using a specific model checker, NuSMV. [Copyright &y& Elsevier]

Biological processes such as circadian rhythms, cell division, metabolism, and development occur as ordered sequences of events. The synchronization of these coordinated events is essential for proper cell function, and hence the determination of critical time points in biological processes is an important component of all biological investigations. In particular, such critical time points establish logical ordering constraints on subprocesses, impose prerequisites on temporal regulation and spatial compartmentalization, and situate dynamic reorganization of functional elements in preparation for subsequent stages. Thus, building temporal phenomenological representations of biological processes from genome-wide datasets is relevant in formulating biological hypotheses on: how processes are mechanistically regulated; how the regulations vary on an evolutionary scale, and how their inadvertent disregulation leads to a diseased state or fatality. This paper presents a general framework (GOALIE) to reconstruct temporal models of cellular processes from time-course gene expression data. We mathematically formulate the problem as one of optimally segmenting datasets into a succession of "informative" windows such that time points within a window expose concerted clusters of gene action whereas time points straddling window boundaries constitute points of significant restructuring. We illustrate here how GOALIE successfully brings out the interplay between multiple yeast processes, inferred from combined experimental datasets for the cell cycle and the metabolic cycle. [ABSTRACT FROM AUTHOR]

Abstract: Rewriting logic is a flexible and general logic to specify concurrent systems. To prove properties about concurrent systems in temporal logic, it is very useful to use simulations that relate the transitions and atomic predicates of a system to those of a potentially much simpler one; then, if the simpler system satisfies a property in a suitable temporal logic we are guaranteed that the more complex system does too. In this paper, the suitability of rewriting logic as a formal framework not only to specify concurrent systems but also to specify simulations is explored in depth. For this, increasingly more general notions of simulation (allowing stuttering) are first defined for Kripke structures, and suitable temporal logics allowing properties to be reflected back by such simulations are characterized. The paper then proves various representability results à la Bergstra and Tucker, showing that recursive Kripke structures and recursive simulation maps (resp.r.es˙imulation relations) can always be specified in a finitary way in rewriting logic. Using simulations typically requires both model checking and theorem proving, since their correctness requires discharging proof obligations. In this regard, rewriting logic, by containing equational logic as a sublogic and having equationally-based inductive theorem proving at its disposal, is shown to be particularly well-suited for verifying the correctness of simulations. [Copyright &y& Elsevier]

Although testing is an essential part of software development, until recently, P system testing has been completely neglected. Mutation testing (mutation analysis) is a structural software testing method which involves modifying the program in small ways. In this paper, we provide a formal way of generating mutants for systems specified by context-free grammars. Furthermore, the paper shows how the proposed method can be used to construct mutants for a P system specification. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of updating of an agent''s knowledge. We propose a formal method of knowledge update on the basis of the semantics of modal logic S5. In our method, an update is specified according to the minimal change on both the agent''s actual world and knowledge. We discuss general minimal change properties of knowledge update and show that our knowledge update operator satisfies all the update postulates of Katsuno and Mendelzon. We characterize several specific forms of knowledge update which have important applications in reasoning about change of agents'' knowledge. We also examine the persistence property of knowledge and ignorance associated with knowledge update. We then investigate the computational complexity of model checking for knowledge update. We first show that in general the model checking for knowledge update is -complete. We then identify a subclass of knowledge update problems that has polynomial time complexity for model checking. We point out that some important knowledge update problems belong to this subclass. We further address another interesting subclass of knowledge update problems for which the complexity of model checking is NP-complete. [Copyright &y& Elsevier]

For every poset $(I,\leq)$ and every family $(G_i)_{i\in I}$ of groups there exists a family of separable Kripke structures $(K_i)_{i\in I}$ on the same set, such that $G_i\cong Aut(K_i)$ and $K_i$ is subalgebra of $K_j iff i\leq j, \rom {for} i, j\in I$ . More generally, this work is concerned with representations of algebraic categories by means of the category of separable Kripke structures. Consequences thereof are mentioned. Thus, in contrast to the algebraic non-universality of the category of Boolean algebras we conclude the algebraic universality of the category of separable dynamic algebras. Perfect classes of Kripke structures are introduced. [ABSTRACT FROM AUTHOR]

In 1997, Coleman showed that a variety V is n-permutable for some n iff every T 0-topological Algebra in V is T 1. Here we show that the implication " $T_0\Rightarrow$ sober" is another such characterization for n-permutability. Other implications of a similar nature are given. For example, an n-permutable variety having a majority term satisfies " $T_0\Rightarrow T_2$ ". [ABSTRACT FROM AUTHOR]