--- _id: '4498' abstract: - lang: eng text: 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 article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Peter full_name: Kopke, Peter last_name: Kopke citation: ama: '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.492576' apa: 'Henzinger, 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.492576' chicago: Henzinger, 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. ieee: 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. ista: '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.' mla: 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. short: M.H. Henzinger, T.A. Henzinger, P. Kopke, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 453–462. conference: end_date: 1995-10-25 location: Milwaukee, WI, United States of America name: 'FOCS: Foundations of Computer Science' start_date: 1995-10-23 date_created: 2018-12-11T12:09:10Z date_published: 1995-11-01T00:00:00Z date_updated: 2023-02-09T08:43:48Z day: '01' doi: 10.1109/SFCS.1995.492576 extern: '1' language: - iso: eng month: '11' oa_version: None page: 453 - 462 publication: Proceedings of IEEE 36th Annual Foundations of Computer Science publication_identifier: isbn: - '0818671831' issn: - 0272-5428 publication_status: published publisher: IEEE publist_id: '231' quality_controlled: '1' scopus_import: '1' status: public title: Computing simulations on finite and infinite graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '1995' ...