Simple O(m logn) Time Markov Chain Lumping

DOI10.1007/978-3-642-12002-2_4zbMath1284.68437OpenAlexW2031728268MaRDI QIDQ3557064

Antti Valmari, Giuliana Franceschinis

Publication date: 27 April 2010

Published in: Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-12002-2_4

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Minimality Notions via Factorization Systems and Examples, Reasoning about proportional lumpability, Lumpability for uncertain continuous-time Markov chains, Lumping and reversed processes in cooperating automata, A space-efficient simulation algorithm on probabilistic automata, An efficient algorithm to determine probabilistic bisimulation, Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence, Out of control: reducing probabilistic models by control-state elimination, Unnamed Item, Explainability of probabilistic bisimilarity distances for labelled Markov chains, On the tradeoff between compositionality and exactness in weak bisimilarity for integrated-time Markovian process calculi, Efficient CTMC Model Checking of Linear Real-Time Objectives, From generic partition refinement to weighted tree automata minimization, Persistent Stochastic Non-Interference, Lumping-based equivalences in Markovian automata: algorithms and applications to product-form analyses, Unnamed Item, The linear time-branching time spectrum of equivalences for stochastic systems with non-determinism, \textit{D\_PSNI}: delimited persistent stochastic non-interference, Bounding inferences for large-scale continuous-time Markov chains: a new approach based on lumping and imprecise Markov chains, Symbolic computation of differential equivalences, Quantitative Abstractions for Collective Adaptive Systems, Efficient Coalgebraic Partition Refinement