| 1. |
|
|
| 2. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Algorithmic Improvements in Regular Model Checking
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Regular model checking is a form of symbolic model checking for parameterized and infinite-state systems, whose states can be represented as finite strings of arbitrary length over a finite alphabet, in which regular sets of words are used to represent sets of states. In earlier papers, we have developed methods for computing the transitive closure (or the set of reachable states) of the transition relation, represented by a regular length-preserving transducer. In this paper, we present several improvements of these techniques, which reduce the size of intermediate approximations of the transitive closure: One improvement is to pre-process the transducer by \em bi-determinization, another is to use a more powerful equivalence relation for identifying histories (columns) of states in the transitive closure. We also present a simplified theoretical framework for showing soundness of the optimization, which is based on commuting simulations. The techniques have been implemented, and we report the speedups obtained from the respective optimizations.
|
|
| 3. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Monotonic and downward closed games
- 2008
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press (OUP). - 0955-792X .- 1465-363X. ; 18:1, s. 153-169
-
Tidskriftsartikel (refereegranskat)abstract
- In an earlier work [Abdulla et al. (2000, Information and Computation, 160, 109127)] we presented a general framework for verification of infinite-state transition systems, where the transition relation is monotonic with respect to a well quasi-ordering on the set of states. In this article, we investigate extending the framework from the context of transition systems to that of games with infinite state spaces. We show that monotonic games with safety winning conditions are in general undecidable. In particular, we show this negative results for games which are defined over Petri nets. We identify a subclass of monotonic games, called downward closed games. We provide algorithms for analysing downward closed games subject to safety winning conditions. We apply the algorithm to games played on lossy channel systems. Finally, we show that weak parity games are undecidable for the above classes of games.
|
|
| 4. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Regular Model Checking for LTL(MSO)
- 2004
-
Ingår i: Proc. 16th Int. Conf. on Computer Aided Verification, LNCS.
-
Tidskriftsartikel (refereegranskat)
|
|
| 5. |
|
|
| 6. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Tree Regular Model Checking : A simulation-based approach
- 2006
-
Ingår i: Journal of Logic and Algebraic Programming. - : Elsevier BV. - 1567-8326 .- 1873-5940. ; 69:1-2, s. 93-121
-
Tidskriftsartikel (refereegranskat)abstract
- Regular model checking is the name of a family of techniques for analyzing infinite-state systems in which states are represented by words, sets of states by finite automata, and transitions by finite-state transducers. In this framework, the central problem is to compute the transitive closure of a transducer. Such a representation allows to compute the set of reachable states of the system and to detect loops between states. A main obstacle of this approach is that there exists many systems for which the reachable set of states is not regular. Recently, regular model checking has been extended to systems with tree-like architectures. In this paper, we provide a procedure, based on a new implementable acceleration technique, for computing the transitive closure of a tree transducer. The procedure consists of incrementally adding new transitions while merging states, which are related according to a pre-defined equivalence relation. The equivalence is induced by a downward and an upward simulation relation, which can be efficiently computed. Our technique can also be used to compute the set of reachable states without computing the transitive closure. We have implemented and applied our technique to various protocols.
|
|
| 7. |
- Abdulla, Parosh, et al.
(författare)
-
Regular Model Checking for LTL(MSO)
- 2004
-
Ingår i: Computer Aided Verification. - 3540223428 ; , s. 348-360
-
Konferensbidrag (refereegranskat)abstract
- Regular model checking is a form of symbolic model checking for parameterized and infinite-state systems whose states can be represented as words of arbitrary length over a finite alphabet, in which regular sets of words are used to represent sets of states. We present $\logic$, a combination of the logics MSO and LTL as a natural logic for expressing temporal properties to be verified in regular model checking. $\logic$ is a two-dimensional modal logic, where MSO is used for specifying properties of system states and transitions, and LTL is used for specifying temporal properties. In addition, the first-order quantification in MSO can be used to express properties parameterized on a position or process.We give a technique for model checking $\logic$, which is adapted from the automata-theoretic approach: a formula is translated to a (\buchi) transducer with a regular set of accepting states, and regular model checking techniques are used to search for models. We have implemented the technique and show its application to a number of parameterized algorithms from the literature.
|
|
| 8. |
- Abdulla, Parosh, et al.
(författare)
-
Regular model checking for LTL(MSO)
- 2012
-
Ingår i: International Journal on Software Tools for Technology Transfer. - Springer : Springer Science and Business Media LLC. - 1433-2779 .- 1433-2787. ; 14:2, s. 223-241
-
Tidskriftsartikel (refereegranskat)abstract
- Regular model checking is a form of symbolic model checking for parameterized and infinite-state systems whose states can be represented as words of arbitrary length over a finite alphabet, in which regular sets of words are used to represent sets of states. We present LTL(MSO), a combination of the logics MSO and LTL as a natural logic for expressing temporal properties to be verified in regular model checking. In other words, LTL(MSO) is a natural specification language for both the system and the property under consideration. LTL(MSO) is a two-dimensional modal logic, where MSO is used for specifying properties of system states and transitions, and LTL is used for specifying temporal properties. In addition, the first-order quantification in MSO can be used to express properties parameterized on a position or process. We give a technique for model checking LTL(MSO), which is adapted from the automata-theoretic approach: a formula is translated to a Buechi regular transition system with a regular set of accepting states, and regular model checking techniques are used to search for models. We have implemented the technique, and show its application to a number of parameterized algorithms from the literature.
|
|
| 9. |
- Aziz Abdulla, Parosh, et al.
(författare)
-
Simulation-Based Iteration of Tree Transducers
- 2005
-
Ingår i: Proc. TACAS'05, 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems.
-
Konferensbidrag (refereegranskat)
|
|
| 10. |
- David, Alexandre, et al.
(författare)
-
A Formal Semantics for UML Statecharts
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The UML language is a large set of notations and rules to describe different aspects of a system. It provides a set of diagrams to view the system from different angles: use case diagrams, class diagrams, statecharts diagrams, and deployment diagrams are some of them. In this report we are interested in the statecharts diagrams that describe dynamic behaviours. We give a formal semantics for a large subset of these statecharts, in particular we focus on the action language semantics. Our subset and semantics are very close to the one supported by the tool Rhapsody.
|
|
| 11. |
- d'Orso, Julien, 1975-
(författare)
-
New Directions in Symbolic Model Checking
- 2003
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In today's computer engineering, requirements for generally high reliability have pushed the notion of testing to its limits. Many disciplines are moving, or have already moved, to more formal methods to ensure correctness. This is done by comparing the behavior of the system as it is implemented against a set of requirements. The ultimate goal is to create methods and tools that are able to perform this kind of verfication automatically: this is called Model Checking. Although the notion of model checking has existed for two decades, adoption by the industry has been hampered by its poor applicability to complex systems. During the 90's, researchers have introduced an approach to cope with large (even infinite) state spaces: Symbolic Model Checking. The key notion is to represent large (possibly infinite) sets of states by a small formula (as opposed to enumerating all members). In this thesis, we investigate applying symbolic methods to different types of systems: Parameterized systems. We work whithin the framework of Regular Model Chacking. In regular model checking, we represent a global state as a word over a finite alphabet. A transition relation is represented by a regular length-preserving transducer. An important operation is the so-called transitive closure, which characterizes composing a transition relation with itself an arbitrary number of times. Since completeness cannot be achieved, we propose methods of computing closures that work as often as possible. Games on infinite structures. Infinite-state systems for which the transition relation is monotonic with respect to a well quasi-ordering on states can be analyzed. We lift the framework of well quasi-ordered domains toward games. We show that monotonic games are in general undecidable. We identify a subclass of monotonic games: downward-closed games. We propose an algorithm to analyze such games with a winning condition expressed as a safety property. Probabilistic systems. We present a framework for the quantitative analysis of probabilistic systems with an infinite state-space: given an initial state sinit, a set F of final states, and a rational Θ > 0, compute a rational ρ such that the probability of reaching F form sinit is between ρ and ρ + Θ. We present a generic algorithm and sufficient conditions for termination.
|
|
| 12. |
- Parosh Aziz Abdulla, Ahmed Bouajjani, and Julien d'Orso.
(författare)
-
Deciding Monotonic Games.
- 2003
-
Ingår i: CSL/KGC'03, Computer Science Logic and 8th Kurt Gödel Colloquium.
-
Konferensbidrag (refereegranskat)
|
|
