Efficient Coalgebraic Partition Refinement
From MaRDI portal
Publication:5111646
Computational methods in Markov chains (60J22) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Abstract data types; algebraic specification (68Q65) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Abstract: We present a generic partition refinement algorithm that quotients coalgebraic systems by behavioural equivalence, an important task in reactive verification; coalgebraic generality implies in particular that we cover not only classical relational systems but also various forms of weighted systems. Under assumptions on the type functor that allow representing its finite coalgebras in terms of nodes and edges, our algorithm runs in time where and are the numbers of nodes and edges, respectively. Instances of our generic algorithm thus match the runtime of the best known algorithms for unlabelled transition systems, Markov chains, and deterministic automata (with fixed alphabets), and improve the best known algorithms for Segala systems.
Recommendations
- Efficient and modular coalgebraic partition refinement
- Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata
- Exploiting parallelism in coalgebraic logic programming
- Coalgebraic semantics for parallel derivation strategies in logic programming
- Enhanced coalgebraic bisimulation
- Coalgebras in functional programming and type theory
- An efficient Coq tactic for deciding Kleene algebras
- A partition refinement algorithm for the -calculus
- Coalgebraic components in a many-sorted microcosm
- Transposing partial components--an exercise on coalgebraic refinement
Cites work
- scientific article; zbMATH DE number 3716792 (Why is no real title available?)
- scientific article; zbMATH DE number 149518 (Why is no real title available?)
- scientific article; zbMATH DE number 1064116 (Why is no real title available?)
- scientific article; zbMATH DE number 1927574 (Why is no real title available?)
- scientific article; zbMATH DE number 2172972 (Why is no real title available?)
- scientific article; zbMATH DE number 195102 (Why is no real title available?)
- A calculus of communicating systems
- A distributed algorithm for strong bisimulation reduction of state spaces
- A hierarchy of probabilistic system types
- An efficient algorithm for computing bisimulation equivalence
- Bisimilarity Minimization in O(m logn) Time
- Bisimulation Minimisation Mostly Speeds Up Probabilistic Model Checking
- Bisimulation for labelled Markov processes
- Bisimulation minimization and symbolic model checking
- Bisimulation relations for weighted automata
- Bisimulation through probabilistic testing
- CCS expressions, finite state processes, and three problems of equivalence
- Deciding bisimilarity and similarity for probabilistic processes.
- Describing an algorithm by Hopcroft
- Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
- Formal verification of timed properties of randomized distributed algorithms
- Generalizing the Paige-Tarjan algorithm by abstract interpretation
- Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata
- Introduction to coalgebra. Towards mathematics of states and observation
- Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra
- Monoid-labeled transition systems
- On the final sequence of a finitary set functor
- Optimal state-space lumping in Markov chains
- Re-describing an algorithm by Hopcroft
- Simple \(O(m \log n)\) time Markov chain lumping
- Structural Operational Semantics for Weighted Transition Systems
- Three Partition Refinement Algorithms
- Universal coalgebra: A theory of systems
Cited in
(14)- Efficient and modular coalgebraic partition refinement
- Lumpability for uncertain continuous-time Markov chains
- Probabilistic mediator: a coalgebraic perspective
- A (co)algebraic theory of succinct automata
- From generic partition refinement to weighted tree automata minimization
- Minimality Notions via Factorization Systems and Examples
- Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata
- A generalized partition refinement algorithm, instantiated to language equivalence checking for weighted automata
- scientific article; zbMATH DE number 7649889 (Why is no real title available?)
- Playing with abstraction and representation
- Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence
- Explicit Hopcroft's trick in categorical partition refinement
- Distributed coalgebraic partition refinement
- Generic partition refinement and weighted tree automata
This page was built for publication: Efficient Coalgebraic Partition Refinement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111646)
