dc.contributor.author Henzinger, Thomas A. en_US dc.contributor.author Kopke, Peter W. en_US dc.contributor.author Puri, Anuj en_US dc.contributor.author Varaiya, Pravin en_US dc.date.accessioned 2007-04-23T18:04:05Z dc.date.available 2007-04-23T18:04:05Z dc.date.issued 1995-09 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1541 en_US dc.identifier.uri https://hdl.handle.net/1813/7198 dc.description.abstract Hybrid automata model systems with both digital and analog components, such as embedded control programs. Many verification tasks for such programs can be expressed as reachability problems for hybrid automata. By improving on previous decidability and undecidability results, we identify the precise boundary between decidability and undecidability of the reachability problem for hybrid automata. On the positive side, we give an (optimal) PSPACE reachability algorithm for the case of initialized rectangular automata, where all analog variables follow trajectories within piecewise-linear envelopes and are reinitialized whenever the envelope changes. Our algorithm is based on the construction of a timed automaton that contains all reachability information about a given initialized rectangular automaton. The translation has practical significance for verification, because it guarantees the termination of symbolic procedures for the reachability analysis of initialized rectangular automata. The translation also preserves the $\omega$-languages of initialized rectangular automata with bounded nondeterminism. On the negative side, we show that several slight generalizations of initialized rectangular automata lead to an undecidable reachability problem. In particular, we prove that the reachability problem is undecidable for timed automata augmented with a single stopwatch. en_US dc.format.extent 497900 bytes dc.format.extent 684005 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title What's Decidable About Hybrid Automata? en_US dc.type technical report en_US
﻿