Efficient Coalgebraic Partition Refinement
From MaRDI portal
Publication:5111646
DOI10.4230/LIPIcs.CONCUR.2017.32zbMath1442.68112arXiv1705.08362OpenAlexW2963074164MaRDI QIDQ5111646
Ulrich Dorsch, Stefan Milius, Lutz Schröder, Thorsten Wißmann
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1705.08362
Computational methods in Markov chains (60J22) Analysis of algorithms (68W40) Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Minimality Notions via Factorization Systems and Examples, Lumpability for uncertain continuous-time Markov chains, Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence, A (co)algebraic theory of succinct automata, Unnamed Item, From generic partition refinement to weighted tree automata minimization, Probabilistic mediator: a coalgebraic perspective
Cites Work
- On the final sequence of a finitary set functor
- Bisimulation minimization and symbolic model checking
- CCS expressions, finite state processes, and three problems of equivalence
- Generalizing the Paige-Tarjan algorithm by abstract interpretation
- Optimal state-space lumping in Markov chains
- A calculus of communicating systems
- Bisimulation through probabilistic testing
- Universal coalgebra: A theory of systems
- Re-describing an algorithm by Hopcroft
- An efficient algorithm for computing bisimulation equivalence
- Deciding bisimilarity and similarity for probabilistic processes.
- Bisimulation relations for weighted automata
- Bisimulation for labelled Markov processes
- Describing an algorithm by Hopcroft
- Introduction to Coalgebra
- Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra
- Structural Operational Semantics for Weighted Transition Systems
- Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata
- Simple O(m logn) Time Markov Chain Lumping
- Bisimilarity Minimization in O(m logn) Time
- Three Partition Refinement Algorithms
- Monoid-labeled transition systems
- Formal verification of timed properties of randomized distributed algorithms
- Bisimulation Minimisation Mostly Speeds Up Probabilistic Model Checking
- Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
