An efficient simulation algorithm based on abstract interpretation

DOI10.1016/j.ic.2009.06.002zbMath1188.68197OpenAlexW2129934517MaRDI QIDQ1049401

Francesco Tapparo, Francesco Ranzato

Publication date: 12 January 2010

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

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

zbMATH Keywords

model checkingtime complexityspace complexitysimulation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

A Simpler Alternative: Minimizing Transition Systems Modulo Alternating Simulation Equivalence, Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation, An efficient simulation algorithm on Kripke structures, A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata, Employing behavioral preorders to define controllability for nondeterministic discrete-event systems

Uses Software

• VLTS Benchmark Suite

Cites Work

• Characterizing finite Kripke structures in propositional temporal logic
• Property preserving abstractions for the verification of concurrent systems
• From bisimulation to simulation: Coarsest partition problems
• Optimal domains for disjunctive abstract interpretation
• 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
• Correcting a Space-Efficient Simulation Algorithm
• Three Partition Refinement Algorithms
• Three logics for branching bisimulation
• Systematic design of program transformation frameworks by abstract interpretation
• Simulation-based minimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item