HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Computing Approximations of Linear Transition Systems

Julien Musset 1 Michaël Rusinowitch 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Transition systems have been intensively applied to the modelling of complex systems. Their safety properties can be verified using model-checking procedures by iterative computation of fixed points. The approach has to face two main difficulties: the complexity of computations on the data domain and the termination of the iterative algorithm. In many cases an analysis of the transition system can be exploited in order to speed up the calculus. Metatransitions are upper approximations of transition relations: they lead in one step to a superset of the states occuring on an infinite trajectory. Using polynomials we compute metatransitions for linear transition systems. We apply this method to a train controller.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00071812
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:51:54 PM
Last modification on : Friday, January 21, 2022 - 3:09:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:26:49 PM

Identifiers

  • HAL Id : inria-00071812, version 1

Citation

Julien Musset, Michaël Rusinowitch. Computing Approximations of Linear Transition Systems. [Research Report] RR-4774, INRIA. 2003, pp.20. ⟨inria-00071812⟩

Share

Metrics

Record views

108

Files downloads

176