| 1. |
- 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)
|
|
| 2. |
- Abdulla, Parosh, et al.
(författare)
-
A Survey of Regular Model Checking.
- 2004
-
Ingår i: CONCUR 2004 - Concurrency Theory. - 354022940X ; , s. 35-48
-
Konferensbidrag (refereegranskat)abstract
- Regular model checking is being developed for algorithmic verification of several classes of infinite-state systems whose configurations can be modeled as words over a finite alphabet. Examples include parameterized systems consisting of an arbitrary number of homogeneous finite-state processes connected in a linear or ring-formed topology, and systems that operate on queues, stacks, integers, and other linear data structures. The main idea is to use regular languages as the representation of sets of configurations, and finite-state transducers to describe transition relations. In general, the verification problems considered are all undecidable, so the work has consisted in developing semi-algorithms, and decidability results for restricted cases. This paper provides a survey of the work that has been performed so far, and some of its applications.
|
|
| 3. |
- 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.
|
|
