Computing simulations on finite and infinite graphs
Authors:
- M.R. HenzingerMHM.R. Henzinger
- T.A. HenzingerTHT.A. Henzinger
- P.W. KopkePKP.W. Kopke
Top Cited Papers
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 453-462
Abstract
We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we present an O(mn) algorithm for computing the similarity relation of a graph with n vertices and m edges (assuming m/spl ges/n). For effectively presented infinite graphs, we present a symbolic similarity-checking procedure that terminates if a finite similarity relation exists. We show that 2D rectangular automata, which model discrete reactive systems with continuous environments, define effectively presented infinite graphs with finite similarity relations. It follows that the refinement problem and the /spl forall/CTL* model-checking problem are decidable for 2D rectangular automata.Keywords
This publication has 19 references indexed in Scilit:
- Transformational design and implementation of a new efficient solution to the ready simulation problemScience of Computer Programming, 1995
- A theory of timed automataTheoretical Computer Science, 1994
- A linear-time model-checking algorithm for the alternation-free modal mu-calculusFormal Methods in System Design, 1993
- The concurrency workbenchACM Transactions on Programming Languages and Systems, 1993
- Symbolic model checking: 1020 States and beyondInformation and Computation, 1992
- Forward and backward simulations for timing-based systems1992
- Simulations between specifications of distributed systems1991
- Model checking and modular verification1991
- Three Partition Refinement AlgorithmsSIAM Journal on Computing, 1987
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985