Computing simulations on finite and infinite graphs

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 ? 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 model-checking problem are decidable for 2D rectangular automata.


Published in:
Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science, 453-462
Presented at:
Milwaukee, WI, USA
Year:
1995
Publisher:
IEEE
Keywords:
Other identifiers:
Scopus: 2-s2.0-0029488964
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)