College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||Hybrid Automata with Finite Mutual Simulations|
|Authors: ||Henzinger, Thomas A.|
Kopke, Peter W.
|Keywords: ||computer science|
|Issue Date: ||Mar-1995|
|Publisher: ||Cornell University|
|Abstract: ||Many decidability results for hybrid automata rely upon the finite region bisimulation of timed automata [AD94]. Rectangular automata do not have finite bisimulations [Hen95], yet have many decidable verification problems [PV94,HKPV95]. We prove that every two-dimensional rectangular automaton A with positive-slope variables has a finite mutual simulation relation, which is the intersection of the region bisimulations defined by the extremal slopes of the variables of A. While the mutual simulation is infinite for two-dimensional automata with one variable taking both positive and negative slopes, it forms a regular tesselation of the plane, and therefore can be encoded by one counter. As a corollary, we obtain the decidability of model checking linear temporal logic on these automata.|
|Appears in Collections:||Computer Science Technical Reports|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.