Generalizing the Paige-Tarjan algorithm by abstract interpretation

DOI10.1016/j.ic.2008.01.001zbMath1197.68054OpenAlexW2050965526MaRDI QIDQ924726

Francesco Ranzato, Francesco Tapparo

Publication date: 19 May 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.01.001

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

An O ( m log n ) Algorithm for Computing Stuttering Equivalence and Branching Bisimulation, Computing Stuttering Simulations, Unnamed Item, Unnamed Item, On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations, Bisimulations for fuzzy automata, Nondeterministic automata: equivalence, bisimulations, and uniform relations, An abstract interpretation framework for genotype elimination algorithms, Team equivalences for finite-state machines with silent moves, From generic partition refinement to weighted tree automata minimization, Causal Semantics for BPP Nets with Silent Moves, Computation of the greatest simulations and bisimulations between fuzzy automata, Fuzzy relation equations and reduction of fuzzy automata, Reduction of fuzzy automata by means of fuzzy quasi-orders, Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences, Efficient Coalgebraic Partition Refinement

Uses Software

• VLTS Benchmark Suite

Cites Work

• Characterizing finite Kripke structures in propositional temporal logic
• A calculus of communicating systems
• From bisimulation to simulation: Coarsest partition problems
• Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice
• Transformational design and implementation of a new efficient solution to the ready simulation problem
• Generalized Strong Preservation by Abstract Interpretation
• Algebraic laws for nondeterminism and concurrency
• Three Partition Refinement Algorithms
• Three logics for branching bisimulation
• Branching time and abstraction in bisimulation semantics
• Refining and compressing abstract domains
• Systematic design of program transformation frameworks by abstract interpretation
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Simulation-based minimization
• A classification of symbolic transition systems
• Making abstract interpretations complete
• Depth-First Search and Linear Graph Algorithms
• Tools and Algorithms for the Construction and Analysis of Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item