Computing simulations on finite and infinite graphs
Henzinger, Monika
Thomas Henzinger
Kopke, Peter W
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 ∀CTL* model-checking problem are decidable for 2D rectangular automata
IEEE
1995
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/4498
Henzinger M, Henzinger TA, Kopke P. Computing simulations on finite and infinite graphs. In: IEEE; 1995:453-462. doi:<a href="https://doi.org/10.1109/SFCS.1995.492576">10.1109/SFCS.1995.492576</a>
info:eu-repo/semantics/altIdentifier/doi/10.1109/SFCS.1995.492576
info:eu-repo/semantics/closedAccess