Computing Simulations on Finite and Infinite Graphs

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/spl ges/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 /spl forall/CTL* model-checking problem are decidable for 2D rectangular automata.

Authors

• Monika Henzinger
• Thomas A. Henzinger
• Peter W. Kopke

Keywords

• Computational modeling
• Automata
• Computer science
• Application software
• Analytical models
• System analysis and design
• Engineering profession
• Contracts
• Algorithm design and analysis
• State-space methods
• Finite Graph
• Infinite Graph
• Rectangular
• Reaction System
• Deterministic
• State Space
• Boolean Operators
• State Machine
• Equivalence Relation
• Starting State
• Maximum Slope
• Binary Relation
• Input Graph
• Unit Square
• Temporal Logic
• Linear Logic
• Minimum Slope