# Computing simulations on finite and infinite graphs

Henzinger MH, Henzinger TA, Kopke P. 1995. Computing simulations on finite and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 453–462.

Download

**No fulltext has been uploaded. References only!**

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

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⩾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

Publishing Year

Date Published

1995-11-01

Proceedings Title

Proceedings of IEEE 36th Annual Foundations of Computer Science

Page

453 - 462

Conference

FOCS: Foundations of Computer Science

Conference Location

Milwaukee, WI, United States of America

Conference Date

1995-10-23 – 1995-10-25

ISBN

ISSN

IST-REx-ID

### Cite this

Henzinger MH, Henzinger TA, Kopke P. Computing simulations on finite and infinite graphs. In:

*Proceedings of IEEE 36th Annual Foundations of Computer Science*. IEEE; 1995:453-462. doi:10.1109/SFCS.1995.492576Henzinger, M. H., Henzinger, T. A., & Kopke, P. (1995). Computing simulations on finite and infinite graphs. In

*Proceedings of IEEE 36th Annual Foundations of Computer Science*(pp. 453–462). Milwaukee, WI, United States of America: IEEE. https://doi.org/10.1109/SFCS.1995.492576Henzinger, Monika H, Thomas A Henzinger, and Peter Kopke. “Computing Simulations on Finite and Infinite Graphs.” In

*Proceedings of IEEE 36th Annual Foundations of Computer Science*, 453–62. IEEE, 1995. https://doi.org/10.1109/SFCS.1995.492576.M. H. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on finite and infinite graphs,” in

*Proceedings of IEEE 36th Annual Foundations of Computer Science*, Milwaukee, WI, United States of America, 1995, pp. 453–462.Henzinger, Monika H., et al. “Computing Simulations on Finite and Infinite Graphs.”

*Proceedings of IEEE 36th Annual Foundations of Computer Science*, IEEE, 1995, pp. 453–62, doi:10.1109/SFCS.1995.492576.