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

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.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:15:57 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM


  • 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⟩



Record views