Skip to main content


eCommons@Cornell >
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
technical report
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

Files in This Item:

File Description SizeFormat
95-1497.pdf193.03 kBAdobe PDFView/Open
95-1497.ps241.9 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us