Search

Concurrency as a phenomenon is observed in most of the current computer science trends. However the inherent complexity of analyzing the behavior of such a system is incremented due to the many different models of concurrency, the variety of applications and architectures, as well as the wide spectrum of specification languages and demanded correctness criteria. For the scope of this thesis we focus on state based models of concurrent computation, and on modal logics as specification languages. First we study syntactically the process algebras that describe several different concurrent behaviors, by analyzing their equational theories. Here, we use well-established techniques from the equational logic of processes to older and newer setups, and then transition to the use of more general and novel methods for the syntactical analysis of models of concurrent programs and specification languages. Our main contributions are several positive and negative axiomatizability results over various process algebraic languages and equivalences, along with some complexity results over the satisfiability of multi-agent modal logic with recursion, as a specification language., Samhliða sem fyrirbæri sést í flestum núverandi tölvunarfræði stefnur. Hins vegar er eðlislægt flókið að greina hegðun slíks kerfis- tem er aukið vegna margra mismunandi gerða samhliða, fjölbreytileikans af forritum og arkitektúr, svo og breitt svið forskrifta mælikvarða og kröfðust réttmætisviðmiða. Fyrir umfang þessarar ritgerðar leggjum við áherslu á ástandsbundin líkön af samhliða útreikningum og á formlegum rökfræði sem forskrift tungumálum. Fyrst skoðum við setningafræðilega ferlialgebrurnar sem lýsa nokkrum mismunandi samhliða hegðun, með því að greina jöfnukenningar þeirra. Hér notum við rótgróin tækni mynda jöfnunarrökfræði ferla til eldri og nýrri uppsetningar, og síðan umskipti yfir í notkun almennari og nýrra aðferða fyrir setningafræðileg greining á líkönum samhliða forrita og forskriftartungumála. Helstu framlög okkar eru nokkrar jákvæðar og neikvæðar niðurstöður um axiomatizability yfir ýmis ferli algebrumál og jafngildi, ásamt nokkrum samSveigjanleiki leiðir af því að fullnægjanleiki fjölþátta formrökfræði með endurkomu, sem a forskrift tungumál., RANNIS: `Open Problems in the Equational Logic of Processes’ (OPEL) (grant No 196050-051) Reykjavik University research fund: `Runtime and Equational Verification of Concurrent Programs' (ReVoCoP) (grant No 222021)

Model checking is a powerful method widely explored in formal verification. Given a model of a system, e.g., a Kripke structure, and a formula specifying its expected behaviour, one can verify whether the system meets the behaviour by checking the formula against the model. Classically, system behaviour is expressed by a formula of a temporal logic, such as LTL and the like. These logics are "point-wise" interpreted, as they describe how the system evolves state-by-state. However, there are relevant properties, such as those constraining the temporal relations between pairs of temporally extended events or involving temporal aggregations, which are inherently "interval-based", and thus asking for an interval temporal logic. In this paper, we give a formalization of the model checking problem in an interval logic setting. First, we provide an interpretation of formulas of Halpern and Shoham's interval temporal logic HS over finite Kripke structures, which allows one to check interval properties of computations. Then, we prove that the model checking problem for HS against finite Kripke structures is decidable by a suitable small model theorem, and we provide a lower bound to its computational complexity., In Journal: Acta Informatica, Springer Berlin Heidelber, 2015

Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q, $\rightarrow$) be a given transition system and Rinit be an initial preorder over Q. Until now, algorithms to compute Rsim , the coarsest simulation included in Rinit , are either memory efficient or time efficient but not both. In this paper we propose the foundation for a series of efficient simulation algorithms with the introduction of the notion of maximal transitions and the notion of stability of a preorder with respect to a coarser one. As an illustration we solve an open problem by providing the first algorithm with the best published time complexity, O(|Psim |.|$\rightarrow$|), and a bit space complexity in O(|Psim |^2. log(|Psim |) + |Q|. log(|Q|)), with Psim the partition induced by Rsim.

International audience; Spatial constraint systems are algebraic structures from concurrent constraint programming to specify spatial and epistemic behavior in multi-agent systems. We shall use spatial constraint systems to give an abstract characterization of the notion of normality in modal logic and to derive right inverse/reverse operators for modal languages. In particular, we shall identify the weakest condition for the existence of right inverses and show that the abstract notion of normality corresponds to the preservation of finite suprema. We shall apply our results to existing modal languages such as the weakest normal modal logic, Hennessy-Milner logic, and linear-time temporal logic. We shall discuss our results in the context of modal concepts such as bisimilarity and inconsistency invariance.

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 Σ2P-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.

Model checking is a powerful method widely explored in formal verification. Given a model of a system, e.g. A Kripke structure, and a formula specifying its expected behavior, one can verify whether the system meets the behavior by checking the formula against the model. Classically, system behavior is given as a formula of a temporal logic, such as LTL and the like. These logics are "point-wise" interpreted, as they describe how the system evolves state-by-state. However, there are relevant properties, such as those involving temporal aggregations, which are inherently "interval-based", and thus asking for an interval temporal logic. In this paper, we give a formalization of the model checking problem in an interval logic setting. First, we provide an interpretation of formulas of Halpern and Shoham's interval temporal logic HS over Kripke structures, which allows one to check interval properties of computations. Then, we prove that the model checking problem for HS against Kripke structures is decidable by a suitable small model theorem, and we outline a PSpace decision procedure for the meaningful fragments AAbarBBbar and AAbarEEbar.

For every poset (I; ) and every family .Gi /i2I of groups there exists a family of separable Kripke structures .Ki /i2I on the same set, such thatGi D Aut.Ki / andKi is subalgebra ofKj iff i j , for i; j 2 I . More generally, thiswork 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. JNICT (Programa de Formação e Mobilidade de Recursos Humanos BD1298 Cultural Agreement between Portugal and Czech Republic); Instituto de Telecomunicações.

We extend the usual notion of Kripke Structures with a weighted transition relation, and generalize the usual Boolean satisfaction relation of CTL to a map which assigns to states and temporal formulae a real-valued distance describing the degree of satisfaction. We describe a general approach to obtaining quantitative interpretations for a generic extension of the CTL syntax, and show that, for one such interpretation, the logic is both adequate and expressive with respect to quantitative bisimulation. We extend the usual notion of Kripke Structures with a weighted transition relation, and generalize the usual Boolean satisfaction relation of CTL to a map which assigns to states and temporal formulae a real-valued distance describing the degree of satisfaction. We describe a general approach to obtaining quantitative interpretations for a generic extension of the CTL syntax, and show that, for one such interpretation, the logic is both adequate and expressive with respect to quantitative bisimulation.

Every group is isomorphic to the automorphism group of a Kripke structure with Boolean part equal to a power set Boolean algebra. More generally, we prove that the category of Kripke structures with Boolean part equal to a power set Boolean algebra and morphisms with complete Boolean part is alg-universal, which means that it contains any category of universal algebras as a full subcategory. CMUC - Centro de Matemática da Universidade de Coimbra; FCT

We propose a way of performing model checking analysis for biological systems. The technics were developed for a CTL* logic built upon Ambient Calculus. We introduce labeled syntax trees for ambient processes and use them as possible worlds in a Kripke structure developed for a propositional branching temporal logic. The accessibility relation over labeled syntax trees is generated by the reduction over corresponding Ambient Calculus processes. Providing the algorithms for calculating the accessibility relation between states, we open the perspective of using model checking algorithms developed for temporal logics in analyzing any phenomena described in Ambient Calculus.

With the S5 multi-agent epistemic logic we consider the canonical maps from Krpke structures to knowledge structures. We define a cell to be a minimal subset of knowledge structures known in common semantically by the agents. A cell has finite fanout if at every point every agent considers only a finite number of other points to be possible. We define a cell to be surjective if every Kripke structure that maps to it does so surjectively. All cells with finite fanout are surjective, but the converse does not hold. To construct a counter-example we need topological insights concerning the relationship between the logic and its semantic models. The difference between syntactic and semantic common knowledge is central to this construction.

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. (C) 2010 Elsevier Inc. All rights reserved.

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.