Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00100238
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:15:57 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

Identifiers

  • HAL Id : inria-00100238, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

222