Voir la notice de l'article provenant de la source Numdam
More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification of the MT-preorder, and the abstraction from internal computation. This article solves these difficulties by developing and employing a novel commutation lemma relating the sequencing of action and clock transitions in discrete-time process algebra. Most importantly, it is proved that the MT-preorder is fully-abstract with respect to a natural amortized preorder that uses a simple bookkeeping mechanism for deciding whether one process is faster than another. Together these results reveal the intuitive roots of the MT-preorder as a faster-than relation, while testifying to its semantic elegance. This lifts some of the barriers that have so far hampered progress in semantic theories for comparing the speed of processes.
@article{ITA_2005__39_3_587_0,
author = {L\"uttgen, Gerald and Vogler, Walter},
title = {Bisimulation on speed : lower time bounds},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {587--618},
publisher = {EDP-Sciences},
volume = {39},
number = {3},
year = {2005},
doi = {10.1051/ita:2005030},
mrnumber = {2157048},
zbl = {1077.68064},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005030/}
}
TY - JOUR AU - Lüttgen, Gerald AU - Vogler, Walter TI - Bisimulation on speed : lower time bounds JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 587 EP - 618 VL - 39 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005030/ DO - 10.1051/ita:2005030 LA - en ID - ITA_2005__39_3_587_0 ER -
%0 Journal Article %A Lüttgen, Gerald %A Vogler, Walter %T Bisimulation on speed : lower time bounds %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 587-618 %V 39 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005030/ %R 10.1051/ita:2005030 %G en %F ITA_2005__39_3_587_0
Lüttgen, Gerald; Vogler, Walter. Bisimulation on speed : lower time bounds. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3, pp. 587-618. doi: 10.1051/ita:2005030
Cité par Sources :