Three Simulation Algorithms for Labelled Transition Systems

Gérard Cécé 1, *
* Auteur correspondant
1 DISC
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
Abstract : Algorithms which compute the coarsest simulation preorder are generally designed on Kripke structures. Only in a second time they are extended to labelled transition systems. By doing this, the size of the alphabet appears in general as a multiplicative factor to both time and space complexities. Let $Q$ denotes the state space, $\rightarrow$ the transition relation, $\Sigma$ the alphabet and $P_{sim}$ the partition of $Q$ induced by the coarsest simulation equivalence. In this paper, we propose a base algorithm which minimizes, since the first stages of its design, the incidence of the size of the alphabet in both time and space complexities. This base algorithm, inspired by the one of Paige and Tarjan in 1987 for bisimulation and the one of Ranzato and Tapparo in 2010 for simulation, is then derived in three versions. One of them has the best bit space complexity up to now, $O(|P_{sim}|^2+|{\rightarrow}|.\log|{\rightarrow}|)$, while another one has the best time complexity up to now, $O(|P_{sim}|.|{\rightarrow}|)$. Note the absence of the alphabet in these complexities. A third version happens to be a nice compromise between space and time since it runs in $O(b.|P_{sim}|.|{\rightarrow}|)$ time, with $b$ a branching factor generally far below $|P_{sim}|$, and uses $O(|P_{sim}|^2.\log|P_{sim}|+|{\rightarrow}|.\log|{\rightarrow}|)$ bits.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00771518
Contributeur : Gérard Cece <>
Soumis le : mardi 8 janvier 2013 - 18:11:43
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : mardi 9 avril 2013 - 03:57:09

Fichiers

threeSimAlgo4LTS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00771518, version 1
  • ARXIV : 1301.1638

Citation

Gérard Cécé. Three Simulation Algorithms for Labelled Transition Systems. 2013. 〈hal-00771518〉

Partager

Métriques

Consultations de la notice

176

Téléchargements de fichiers

118