The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
What's Decidable about Hybrid Automata?
Open accessAbstract
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 a boundary between decidability and undecidability for the reachability problem of 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 independent 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ω-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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Alur, R., & Dill, D. L. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90010-8 · Cited by 6,689
The algorithmic analysis of hybrid systems
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., & Yovine, S. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00202-t · Cited by 1,876
Self-citationAn Automata-Theoretic Approach to Automatic Program Verification
Vardi, M. Y., & Wolper, P. (1986) · ORBi (University of Liège) · Cited by 1,261
Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems
Alur, R., Courcoubetis, C., Henzinger, T. A., & Ho, P. H. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57318-6_30 · Cited by 1,106
Self-citationHYTECH: a model checker for hybrid systems
Henzinger, T. A., Ho, P.-H., & Wong-Toi, H. (1997) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s100090050008 · Cited by 774
Self-citationAlgorithmic analysis of nonlinear hybrid systems
Henzinger, T. A., & Ho, P. H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60045-0_53 · Cited by 308
Self-citationVerification of linear hybrid systems by means of convex approximations
Halbwachs, N., Proy, Y. E., & Raymond, P. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58485-4_43 · Cited by 173
Using HyTech to synthesize control parameters for a steam boiler
Henzinger, T. A., & Wong-Toi, H. (1996) · Lecture notes in computer science · doi:10.1007/bfb0027241 · Cited by 77
Self-citationTiming analysis of Ada tasking programs
Corbett, J. C. (1996) · IEEE Transactions on Software Engineering · doi:10.1109/32.538604 · Cited by 64
Cited by
Discrete abstractions of hybrid systems
Alur, R., Henzinger, T. A., Lafferriere, G., & Pappas, G. J. (2000) · Proceedings of the IEEE · doi:10.1109/5.871304 · Cited by 801
Self-citationA survey of computational complexity results in systems and control
Blondel, V. D., & Tsitsiklis, J. N. (2000) · Automatica · doi:10.1016/s0005-1098(00)00050-9 · Cited by 732
Linear Time Logic Control of Discrete-Time Linear Systems
Tabuada, P., & Pappas, G. J. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2006.886494 · Cited by 343
Automatic verification of real-time systems with discrete probability distributions
Kwiatkowska, M., Norman, G., Segala, R., & Sproston, J. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00046-9 · Cited by 333
Requirements-driven test generation for autonomous vehicles with machine learning components
Tuncali, C. E., Fainekos, G., Prokhorov, D., Ito, H., & Kapinski, J. (2020) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2019.2955903 · Cited by 129
Metadata
- Authors
- Henzinger, T. A., Kopke, P. W., Puri, A., & Varaiya, P.
- Venue
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Published
- 1998-08
- Volume
- 57
- Issue
- 1
- Pages
- 94-124
- ISSN
- 0022-0000 (ISSN-L)
- OpenAlex
- W2085838366
- Cited by
- 660
- References
- 9
- FWCI
- 17.08
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.