Generalizing the Paige-Tarjan algorithm by abstract interpretation

DOI10.1016/J.IC.2008.01.001MaRDI QIDQ924726zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Tools and Algorithms for the Construction and Analysis of Systems
• Generalized Strong Preservation by Abstract Interpretation
• An efficient algorithm for computing bisimulation equivalence
• An efficient simulation algorithm based on abstract interpretation
• Programming Languages and Systems

Cites work

• scientific article; zbMATH DE number 1705168 (Why is no real title available?)
• scientific article; zbMATH DE number 177845 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1927588 (Why is no real title available?)
• scientific article; zbMATH DE number 1834576 (Why is no real title available?)
• scientific article; zbMATH DE number 898449 (Why is no real title available?)
• A calculus of communicating systems
• A classification of symbolic transition systems
• Algebraic laws for nondeterminism and concurrency
• Branching time and abstraction in bisimulation semantics
• Characterizing finite Kripke structures in propositional temporal logic
• Depth-First Search and Linear Graph Algorithms
• From bisimulation to simulation: Coarsest partition problems
• Generalized Strong Preservation by Abstract Interpretation
• Making abstract interpretations complete
• Partition refinement techniques: an interesting algorithmic tool kit
• Refining and compressing abstract domains
• Simulation-based minimization
• Systematic design of program transformation frameworks by abstract interpretation
• Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice
• The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
• Three Partition Refinement Algorithms
• Three logics for branching bisimulation
• Tools and Algorithms for the Construction and Analysis of Systems
• Transformational design and implementation of a new efficient solution to the ready simulation problem

Cited in

(19)

• An O(m n) algorithm for computing stuttering equivalence and branching bisimulation
• Efficient and modular coalgebraic partition refinement
• scientific article; zbMATH DE number 7327941 (Why is no real title available?)
• Deriving Bisimulations by Simplifying Partitions
• Bisimulations for fuzzy automata
• Computing Stuttering Simulations
• An abstract interpretation framework for genotype elimination algorithms
• On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
• Computation of the greatest simulations and bisimulations between fuzzy automata
• Reduction of fuzzy automata by means of fuzzy quasi-orders
• From generic partition refinement to weighted tree automata minimization
• Nondeterministic automata: equivalence, bisimulations, and uniform relations
• Fuzzy relation equations and reduction of fuzzy automata
• Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences
• Team equivalences for finite-state machines with silent moves
• Causal Semantics for BPP Nets with Silent Moves
• Generic partition refinement and weighted tree automata
• Efficient Coalgebraic Partition Refinement
• A generalization of Takane's algorithm for DEDICOM

Describes a project that uses

Uses Software

• VLTS Benchmark Suite

This page was built for publication: Generalizing the Paige-Tarjan algorithm by abstract interpretation

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