Generic partition refinement and weighted tree automata

DOI10.1007/978-3-030-30942-8_18zbMATH Open1539.68156MaRDI QIDQ6535955FDOQ6535955

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

Publication date: 14 March 2024

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

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)

Cites Work

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

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)