Generic partition refinement and weighted tree automata

DOI10.1007/978-3-030-30942-8_18MaRDI QIDQ6535955zbMATH OpenFDO

Authors Hans-Peter Deifel, Stefan Milius, Lutz Schröder, Thorsten Wißmann

Publication date 14 March 2024

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• From generic partition refinement to weighted tree automata minimization
• Distributed coalgebraic partition refinement
• Efficient and modular coalgebraic partition refinement
• Efficient Coalgebraic Partition Refinement
• A generalized partition refinement algorithm, instantiated to language equivalence checking for weighted automata

Cites work

• scientific article; zbMATH DE number 149518 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 2090149 (Why is no real title available?)
• A hierarchy of probabilistic system types
• An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
• An efficient algorithm for computing bisimulation equivalence
• An efficient algorithm to determine probabilistic bisimulation
• Automata theory in nominal sets
• Backward and forward bisimulation minimization of tree automata
• Bisimilarity Minimization in O(m logn) Time
• Bisimulation Minimisation for Weighted Tree Automata
• Bisimulation relations for weighted automata
• CCS expressions, finite state processes, and three problems of equivalence
• Deciding bisimilarity and similarity for probabilistic processes.
• Describing an algorithm by Hopcroft
• Distributed branching bisimulation reduction of state spaces
• Efficient Coalgebraic Partition Refinement
• Generalizing the Paige-Tarjan algorithm by abstract interpretation
• Nominal automata with name binding
• Optimal state-space lumping in Markov chains
• Re-describing an algorithm by Hopcroft
• Simple \(O(m \log n)\) time Markov chain lumping
• Simple bisimilarity minimization in \(O(m \log n)\) time
• Structural operational semantics for stochastic and weighted transition systems
• Three Partition Refinement Algorithms
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Tools and Algorithms for the Construction and Analysis of Systems
• Universal coalgebra: A theory of systems

Cited in

(2)

• Explicit Hopcroft's trick in categorical partition refinement
• Distributed coalgebraic partition refinement

This page was built for publication: Generic partition refinement and weighted tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535955)