---
_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
author:
- first_name: Monika
full_name: Henzinger, Monika
last_name: Henzinger
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Peter
full_name: Kopke, Peter W
last_name: Kopke
citation:
ama: 'Henzinger M, Henzinger TA, Kopke P. Computing simulations on finite and infinite
graphs. In: IEEE; 1995:453-462. doi:10.1109/SFCS.1995.492576'
apa: 'Henzinger, M., Henzinger, T. A., & Kopke, P. (1995). Computing simulations
on finite and infinite graphs (pp. 453–462). Presented at the FOCS: Foundations
of Computer Science, IEEE. https://doi.org/10.1109/SFCS.1995.492576'
chicago: Henzinger, Monika, Thomas A Henzinger, and Peter Kopke. “Computing Simulations
on Finite and Infinite Graphs,” 453–62. IEEE, 1995. https://doi.org/10.1109/SFCS.1995.492576.
ieee: 'M. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on finite
and infinite graphs,” presented at the FOCS: Foundations of Computer Science,
1995, pp. 453–462.'
ista: 'Henzinger M, Henzinger TA, Kopke P. 1995. Computing simulations on finite
and infinite graphs. FOCS: Foundations of Computer Science, 453–462.'
mla: Henzinger, Monika, et al. *Computing Simulations on Finite and Infinite Graphs*.
IEEE, 1995, pp. 453–62, doi:10.1109/SFCS.1995.492576.
short: M. Henzinger, T.A. Henzinger, P. Kopke, in:, IEEE, 1995, pp. 453–462.
conference:
name: 'FOCS: Foundations of Computer Science'
date_created: 2018-12-11T12:09:10Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2021-01-12T07:57:24Z
day: '01'
doi: 10.1109/SFCS.1995.492576
extern: 1
month: '01'
page: 453 - 462
publication_status: published
publisher: IEEE
publist_id: '231'
quality_controlled: 0
status: public
title: Computing simulations on finite and infinite graphs
type: conference
year: '1995'
...