JavaScript is disabled for your browser. Some features of this site may not work without it.
Hybrid Automata with Finite Mutual Simulations

Author
Henzinger, Thomas A.; Kopke, Peter W.
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.
Date Issued
1995-03Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1497
Type
technical report