Improving the construction of the DBM over approximation of the state spce of real-time preemptive systems

Abdelkrim Abdelli: Improving the construction of the DBM over approximation of the state spce of real-time preemptive systems. In: Acta cybernetica, (20) 3. pp. 347-384. (2012)

[thumbnail of actacyb_20_3_2012_1.pdf]
Előnézet
Cikk, tanulmány, mű
actacyb_20_3_2012_1.pdf

Letöltés (546kB) | Előnézet

Absztrakt (kivonat)

We present in this paper an algorithm allowing an efficient computation of the tightest DBM over-approximation of the state space of preemptive systems modeled by using Time Petri Nets with inhibitor arcs. First of all, we propose an algorithm that reduces the effort of computing the tightest DBM over-approximated graph. For this effect, each class of this graph is expressed as a pair (M, D), where M is a marking and D is the system of all DBM inequalities even the redundant ones. We thereby make it possible to compute the system D straightforwardly in its normal form, without requiring to compute the intermediary polyhedra. Hence, we succeed to remove the errors reported in the implementation of other DBM approximations. Then we show that by relaxing a bit in the precision of the DBM approximation, we can achieve to construct more compact graphs while reducing still more the cost of their computation. We provide for this abstraction a suitable equivalence relation that contract yet more the graphs. The experimental results comparing the defined constructions with other approaches are reported.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 2012
Kötet: 20
Szám: 3
ISSN: 0324-721X
Oldalak: pp. 347-384
Nyelv: angol
Kiadás helye: Szeged
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/38533/
DOI: 10.14232/actacyb.20.3.2012.1
Kulcsszavak: Számítástechnika, Kibernetika, Matematika
Megjegyzések: Bibliogr.: p. 383-384. és a lábjegyzetekben ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.01. Matematika
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2016. okt. 17. 10:38
Utolsó módosítás: 2022. jún. 17. 14:23
URI: http://acta.bibl.u-szeged.hu/id/eprint/30836
Bővebben:
Tétel nézet Tétel nézet