A First Approach of Grouping Problem in Stochastic Automata Network

Dominique Barth Johanne Cohen 1 Mathieu Le Coz Franck Quessette
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In the Stochastic Automata Network (SAN) formalism, a SAN is composed of a set of automata and a set of synchronizations which model an underlying Markov chain. For each automaton and each pair of automaton-synchronization one has to store a matrix. This leads to a low storage compared to the storage of the underlying Markov chain but the time complexity depends on the number of automata and synchronizations. We propose to contract automata together in order to get a contraction of the number of automata and synchronizations and a reduction of time complexity at the price of a larger storage. In this first work, we assume no function, we do not take into account, the reachability function and we assume dense storage for the matrices. Assuming a maximal amount of storage capacity, we prove that to find the best contraction, under our assumptions, is a NP-complete problem. Then we give a heuristic and make some comparisons between the heuristic and the best value and we show that this heuristic gives quite good results.
Type de document :
[Intern report] A04-R-072 || barth04e, 2004
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:15:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00100238, version 1



Dominique Barth, Johanne Cohen, Mathieu Le Coz, Franck Quessette. A First Approach of Grouping Problem in Stochastic Automata Network. [Intern report] A04-R-072 || barth04e, 2004. 〈inria-00100238〉



Consultations de la notice