Search results for " Computer Science"
showing 10 items of 3983 documents
A Detailed Account of The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2021
One of the most popular state-space reduction techniques for model checking is partial-order reduction (POR). Of the many different POR implementations, stubborn sets are a very versatile variant and have thus seen many different applications over the past 32 years. One of the early stubborn sets works shows how the basic conditions for reduction can be augmented to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a stronger reduction condition and provide extensive new correc…
Verification of Well-Formed Communicating Recursive State Machines
2008
AbstractIn this paper we introduce a new (non-Turing equivalent) formal model of recursive concurrent programs called well-formed communicating recursive state machines (CRSM). CRSM extend recursive state machines (RSM) by allowing a restricted form of concurrency: a state of a module can be refined into a finite collection of modules (working in parallel) in a potentially recursive manner. Communication is only possible between the activations of modules invoked on the same fork. We study the model-checking problem of CRSM with respect to specifications expressed in a temporal logic that extends CaRet with a parallel operator (ConCaRet). We propose a decision algorithm that runs in time ex…
Implementing an ATL model checker tool using relational algebra concepts
2014
Alternating-Time Temporal Logic (ATL) is a branching-time temporal logic that naturally describes computations of open systems. An open system interacts with its environment and its behavior depends on the state of the system as well as the behavior of the environment. ATL model-checking is a well-established technique for verifying that a formal model representing such a system satisfies a given property. In this paper we describe a new interactive model checker environment based on algebraic approach. Our tool is implemented in client-server paradigm. The client part allows an interactive construction of ATL models represented by concurrent game structures as directed multi-graphs. The se…
Minimal Büchi Automata for Certain Classes of LTL Formulas
2009
In this paper we calculate the minimal number of states of Buchi automata which encode some classes of linear temporal logic (LTL) formulas that are frequently used in model checking. Our results may be used for verification of the quality of algorithms which automatically translate LTL formulas into Buchi automata and for improving the quality and speed of such translators. In the last section of this paper we compare our lower-bound estimations to Buchi automata generated by two currently used translators: LTL2BA and SPOT.
Verification of scope-dependent hierarchical state machines
2008
AbstractA hierarchical state machine (Hsm) is a finite state machine where a vertex can either expand to another hierarchical state machine (box) or be a basic vertex (node). Each node is labeled with atomic propositions. We study an extension of such model which allows atomic propositions to label also boxes (Shsm). We show that Shsms can be exponentially more succinct than Shsms and verification is in general harder by an exponential factor. We carefully establish the computational complexity of reachability, cycle detection, and model checking against general Ltl and Ctl specifications. We also discuss some natural and interesting restrictions of the considered problems for which we can …
Verifying a medical protocol with temporal graphs: the case of a nosocomial disease.
2014
Abstract Objective Our contribution focuses on the implementation of a formal verification approach for medical protocols with graphical temporal reasoning paths to facilitate the understanding of verification steps. Materials and methods Formal medical guideline specifications and background knowledge are represented through conceptual graphs, and reasoning is based on graph homomorphism. These materials explain the underlying principles or rationale that guide the functioning of verifications. Results An illustration of this proposal is made using a medical protocol defining guidelines for the monitoring and prevention of nosocomial infections. Such infections, which are acquired in the h…
Formal Modeling and Discrete-Time Analysis of BPEL Web Services
2008
International audience; Web services are increasingly used for building enterprise information systems according to the Service Oriented Architecture (SOA) paradigm. We propose in this paper a tool-equipped methodology allowing the formal modeling and analysis of Web services described in the BPEL language. The discrete-time transition systems modeling the behavior of BPEL descriptions are obtained by an exhaustive simulation based on a formalization of BPEL semantics using the Algebra of Timed Processes (ATP). These models are then analyzed by model checking value-based temporal logic properties using the CADP toolbox. The approach is illustrated with the design of a Web service for GPS na…
Estimation of the mean crystal size and the moments of the crystal size distribution in batch crystallization processes
2016
International audience; A cascade high gain observer is designed to estimate the first four leading moments of the crystal size distribution (CSD) and the mean crystal size in batch crystallization processes. The proposed observer is based on a well-known transformation of the partial differential equation describing the CSD to a set of ordinary differential equations (the method of moments). Due to numerical difficulties resulting from the important differences in the magnitudes of the moments, a set of new variables is computed to allow a good estimation of the moments and thus the mean crystal size. In this work, only solute concentration and crystallizer temperature are used to estimate…
A heuristic for problem formalization in agent based simulation studies
2015
Agent Based Modeling and Simulation (ABMS) is considered an effective approach for conducting simulation studies in many fields. In order to develop high quality simulation models, methodological approaches are demanded. In such direction we are moving by proposing a heuristic for the formalization of agent based simulation problems. The proposed heuristic is based on some guidelines developed for identifying the main elements of the problem domain description by analysing verbs and their common taxonomy in grammar.