---
_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: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>.
    IEEE; 1995:453-462. doi:<a href="https://doi.org/10.1109/SFCS.1995.492576">10.1109/SFCS.1995.492576</a>'
  apa: 'Henzinger, M. H., Henzinger, T. A., &#38; Kopke, P. (1995). Computing simulations
    on finite and infinite graphs. In <i>Proceedings of IEEE 36th Annual Foundations
    of Computer Science</i> (pp. 453–462). Milwaukee, WI, United States of America:
    IEEE. <a href="https://doi.org/10.1109/SFCS.1995.492576">https://doi.org/10.1109/SFCS.1995.492576</a>'
  chicago: Henzinger, Monika H, Thomas A Henzinger, and Peter Kopke. “Computing Simulations
    on Finite and Infinite Graphs.” In <i>Proceedings of IEEE 36th Annual Foundations
    of Computer Science</i>, 453–62. IEEE, 1995. <a href="https://doi.org/10.1109/SFCS.1995.492576">https://doi.org/10.1109/SFCS.1995.492576</a>.
  ieee: M. H. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on
    finite and infinite graphs,” in <i>Proceedings of IEEE 36th Annual Foundations
    of Computer Science</i>, 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.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    IEEE, 1995, pp. 453–62, doi:<a href="https://doi.org/10.1109/SFCS.1995.492576">10.1109/SFCS.1995.492576</a>.
  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'
...