Semantics of Biological Regulatory Networks

The aim of the paper is to revisit the model of Biological Regulatory Networks (BRN) which was proposed by René Thomas to model the interactions between a set of genes. We give a formal semantics for BRN in terms of transition systems which formalizes the evolution rules given by René Thomas. Then we show how to use this model to find interesting properties of a BRN like the set of stable states, cycles etc using tools for analyzing transition systems.     

Adaptive estimation and identification for discrete systems with Markov jump parameters

Linear discrete-time stochastic dynamical systems with parameters which may switch among a finite set of values are considered. The switchings are modeled by a finite state ergodic Markov chain whose transition probability matrix is unknown and is assumed to belong to a compact set. A novel scheme, called truncated maximum likelihood estimation, is proposed for consistent estimation of the transition probabilities given noisy observations of the system output variables. Conditions for strong consistency are investigated assuming that the measurements are taken after the system has achieved a statistical steady state. The case when the true transition matrix does not belong to the unknown transition matrix set is also considered. The truncated maximum likelihood procedure is computationally feasible, whereas the standard maximum likelihood procedure is not, given large observation records. Finally, using the truncated ML algorithm, a suboptimal adaptive state estimator is proposed and its asymptotic behavior is analyzed.     

A Completion Procedure for Finitely Presented Groups That Is Based on Word Cycles

A Knuth–Bendix-style completion procedure for groups is presented that, instead of working with sets of string-rewriting rules, manipulates finite sets of word cycles. A characterization is given for the resulting sets of persistent word cycles, from which it follows that the completion procedure terminates successfully if and only if the reduced word problem of the finite group presentation considered is a finite set. In this case the resulting set of persistent word cycles yields a finite canonical string-rewriting system for every linear reduction ordering.     

Automatic verification for a class of distributed systems

Summary. The paper presents a new analysis method for a class of concurrent systems which are formed of several interacting components with the same structure. The model for these systems is composed of a control process and a set of homogeneous user processes. The control and user processes are modeled by finite labeled state transition systems which interact by means of enabling functions and triggering mechanisms. Based on this structure, an analysis method is presented which allows system properties, derived by reachability analysis for a finite number of user processes, to be generalized to an arbitrary number of user processes. A procedure for the automatic verification of properties such as mutual exclusion and absence of deadlocks is presented and is then used to provide for the first time a fully automated verification of the Lamport's fast mutual exclusion algorithm. Received: October 1998/Accepted January 2000     

<Emphasis FontCategory="SansSerif">VeriSiMPL</Emphasis> 2: An open-source software for the verification of max-plus-linear systems

This work presents a technique to generate finite abstractions of autonomous Max-Plus-Linear (MPL) systems, a class of discrete-event systems employed to characterize the dynamics of the timing related to the synchronization of successive events. Abstractions of MPL systems are derived as finite-state transition systems. A transition system is obtained first by partitioning the state space of the MPL system into finitely many regions and then by associating a unique state of the transition system to each partitioning region. Relations among the states of the transition system are then set up based on the underlying dynamical transitions between the corresponding partitioning regions of the MPL state space. In order to establish formal equivalences, the obtained finite abstractions are proven either to simulate or to bisimulate the original MPL system. The approach enables the study of general properties of the original MPL system formalized as logical specifications, by verifying them over the finite abstraction via model checking. The article presents a new, extended and improved implementation of a software tool (available online) for the discussed formal abstraction of MPL systems, and is tested on a numerical benchmark against a previous version.     

Limit cycle computation for describing function approximable nonlinear systems with box‐constrained parametric uncertainties

We propose an algorithm to compute the limit cycle set of uncertain non‐rational nonlinear systems with nonlinear parametric dependencies. The proposed algorithm computes the limit cycles for a wide class of uncertain nonlinear systems, where the transfer function of the linear element and describing function of the nonlinear element need to be only continuous with respect to the parameters and continuously differentiable with respect to the amplitude and frequency of periodic input signal. The proposed algorithm guarantees that the limit cycles are reliably computed to a prescribed accuracy, and that none of the actual limit cycle point is missed out irrespective of the tightness of the prescribed accuracy. Moreover, for a prescribed accuracy, the proposed algorithm computes all the limit cycles in a finite number of iterations, and an upper bound for this number is also computable. The algorithm is demonstrated on a challenging non‐rational example with nonlinear parametric dependencies. Copyright © 2005 John Wiley & Sons, Ltd.     

On spiking neural P systems

This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants. A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems and the capability these models have to generate certain classes of languages. Further, by making a slight modification to the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.     

On the periodicity of symbolic observations of piecewise smoothdiscrete-time systems

A study is made of the behavior of discrete-time systems composed of a set of smooth transition maps coupled by a quantized feedback function. The feedback function partitions the state space into disjoint regions and assigns a smooth transition function to each region. The main result is that under a constraint on the norm of the derivative of the transition maps, a bounded state trajectory with limit points in the interior of the switching regions leads to a region index sequence that is eventually periodic. Under these assumptions, it is shown that eventually the feedback function is determined by a finite state automaton. A similar result is proved in the case of finite state dynamic feedback     

A modal characterization of alternating approximate bisimilarity

Recently, alternating transition systems are adopted to describe control systems with disturbances and their finite abstract systems. In order to capture the equivalence relation between these systems, a notion of alternating approximate bisimilarity is introduced. This paper aims to establish a modal characterization for alternating approximate bisimilarity. Based on this result, we provide a link between specifications satisfied by the samples of control systems with disturbances and their finite abstractions. Moreover, a simple example is given to illustrate the application of such link in the design of controller of control systems.     

Reachability Problems on Regular Ground Tree Rewriting Graphs

We consider the transition graphs of regular ground tree (or term) rewriting systems. The vertex set of such a graph is a (possibly infinite) set of trees. Thus, with a finite tree automaton one can represent a regular set of vertices. It is known that the backward closure of sets of vertices under the rewriting relation preserves regularity, i.e., for a regular set T of vertices the set of vertices from which one can reach T can be accepted by a tree automaton. The main contribution of this paper is to lift this result to the recurrence problem, i.e., we show that the set of vertices from which one can reach infinitely often a regular set T is regular, too. Since this result is effective, it implies that the problem whether, given a tree t and a regular set T, there is a path starting in t that infinitely often reaches T, is decidable. Furthermore, it is shown that the problems whether all paths starting in t eventually (respectively, infinitely often) reach T, are undecidable. Based on the decidability result we define a fragment of temporal logic with a decidable model-checking problem for the class of regular ground tree rewriting graphs.     

On the reachability of quantized control systems

In this paper, we study control systems whose input sets are quantized, i.e., finite or regularly distributed on a mesh. We specifically focus on problems relating to the structure of the reachable set of such systems, which may turn out to be either dense or discrete. We report results on the reachable set of linear quantized systems, and on a particular but interesting class of nonlinear systems, i.e., nonholonomic chained-form systems. For such systems, we provide a complete characterization of the reachable set, and, in case the set is discrete, a computable method to completely and succinctly describe its structure. Implications and open problems in the analysis and synthesis of quantized control systems are addressed     

The Garden of Eden theorem for cellular automata on group sets

ABSTRACT

We prove the Garden of Eden theorem for big-cellular automata with finite set of states and finite neighbourhood on right amenable left homogeneous spaces with finite stabilisers. It states that the global transition function of such an automaton is surjective if and only if it is pre-injective. Pre-Injectivity means that two global configurations that differ at most on a finite subset and have the same image under the global transition function must be identical. The theorem is proven by showing that the global transition function of an automaton as above is surjective if and only if its image has maximal entropy and that its image has maximal entropy if and only if it is pre-injective. Entropy of a subset of global configurations measures the asymptotic growth rate of the number of finite patterns with growing domains that occur in the subset.     

Robust one-step receding horizon control of discrete-time Markovian jump uncertain systems

This paper proposes a receding horizon control scheme for a set of uncertain discrete-time linear systems with randomly jumping parameters described by a finite-state Markov process whose jumping transition probabilities are assumed to belong to some convex sets. The control scheme for the underlying systems is based on the minimization of the worst-case one-step finite horizon cost with a finite terminal weighting matrix at each time instant. This robust receding horizon control scheme has a more general structure than the existing robust receding horizon control for the underlying systems under the same design parameters. The proposed controller is obtained using semidefinite programming.     

Game-theoretic simulation checking tool

Model checking is one of the most commonly used methods for checking program correctness. In this method, one verifies a program model given by the Kripke structure (labeled transition system) rather than the program itself. The specification is usually given as a temporal logic formula. In many subtasks of model checking, it is necessary to use relations that are defined on the set of program models and preserve the satisfiability of temporal logic formulas. There exist many relations of this kind, which are called simulation relations. In the present paper, we introduce a tool designed to check a wide class of simulation relations between finite models of programs. This tool is based on the simulation checking game-theoretic approach. The tool consists of two components. The first component is the formal language, which allows one to define various simulation relations in terms of an antagonistic two-player game. The second component is a software tool that, given two labeled transition systems and simulation definition, is able to check whether this simulation is satisfied between these labeled transition systems.     

广义循环系统的特性分析

本文将正常循环系统推广为广义循环大系统，并利用矩阵理论，集中分析了这类大系统的一些重要性质及其分散固定模的特征。结果表明，Nn阶的广义循环大系统的性质如稳定性、能控性、能观性、固定模的存在性等，均可由一些低阶系统的相应性质来描述。并且广义循环大系统的有穷固定模可通过低阶系统的不可控不可观模态求得，从而避免了因系统的高雏性带来的计算困难。本文的结论为进一步研究这类系统提供了理论基础。     

Exploiting symmetry in temporal logic model checking

In practice, finite state concurrent systems often exhibit considerable symmetry. We investigate techniques for reducing the complexity of temporal logic model checking in the presence of symmetry. In particular, we show that symmetry can frequently be used to reduce the size of the state space that must be explored during model checking. In the past, symmetry has been exploited in computing the set of reachable states of a system when the transition relation is represented explicitly [14, 11, 19]. However, this research did not consider arbitrary temporal properties or the complications that arise when BDDs are used in such procedures.We have formalized what it means for a finite state system to be symmetric and described techniques for reducing such systems when the transition relation is given explicitly in terms of states or symbolically as a BDD. Moreover, we have identified an important class of temporal logic formulas that are preserved under this reduction. Our paper also investigates the complexity of various critical steps, like the computation of the orbit relation, which arise when symmetry is used in this type of verification. Finally, we have tested our ideas on a simple cache-coherency protocol based on the IEEE Futurebus + standard.This research was sponsored in part by the Avionics Laboratory, Wright Research and Development Center, Aeronautical Systems Division (AFSC), U.S. Air Force, Wright-Patterson AFB, Ohio 45433-6543 under Contract F33615-90-C-1465, ARPA Order No. 7597 and in part by the National Science Foundation under Grant No. CCR-8722633 and in part by the Semiconductor Research Corporation under Contract 92-DJ-294.The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. government.     

Using binary decision diagrams for representation and analysis of communication protocols

A symbolic representation of a state/transition system based on binary decision diagrams (BDDs) is generally more compact than an explicit representation like a state/transition table. This is due to regular and repetitive patterns occurring in state/transition systems. By exploiting this property, huge state spaces can be represented, and the resulting BDDs can be profitably used for activities such as symbolic model checking and sequential circuit synthesis. This paper shows how such techniques can be applied to communication protocols by presenting a systematic method to build BDD representations from protocol specifications expressed in the ISO standard protocol specification language LOTOS. The method exploits the compositionality of the process algebra of LOTOS to avoid the enumeration of all the states and transitions, takes also data into account, enables building the BDDs in the more convenient disjunctive partitioned form, and can handle any LOTOS specification characterized by a finite LTS. The method consists in partitioning the set of process definitions according to their mutual recursion relationships, building an LTS for each set of mutually recursive process definitions, encoding these LTSs as BDDs which in turn are combined together, according to the process algebraic operators, to obtain the overall BDD representation. An example is used throughout the paper to illustrate the method.     

Computable processes and bisimulation equivalence

A process is calledcomputable if it can be modelled by a transition system that has a recursive structure—implying finite branching. The equivalence relation between transition systems considered is strong bisimulation equivalence. The transition systems studied in this paper can be associated to processes specified in common specification languages such as CCS, LOTOS, ACP and PSF. As a means for defining transition systems up to bisimulation equivalence, the specification languageCRL is used. Two simple fragments of,CRL are singled out, yielding universal expressivity with respect to recursive and primitive recursive transition systems. For both these domains the following properties are classified in the arithmetical hierarchy:bisimilarity, perpetuity (both ₁ ⁰ ),regularity (having a bisimilar, finite representation, ₂ ⁰ ),acyclic regularity ( ₁ ⁰ ), anddeadlock freedom (distinguishing deadlock from successful termination, ₁ ⁰ ). Finally, it is shown that in the domain of primitive recursive transition systems over a fixed, finite label set, a genuine hierarchy in bisimilarity can be defined by the complexity of the witnessing relations, which extends r.e. bisimilarity. Hence, primitive recursive transition systems already form an interesting class.