Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7155
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
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1497
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.
URI: http://hdl.handle.net/1813/7155
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