Abstract
The paper shows the decidability of the reachability problem for planar, monotonic, linear hybrid automata without resets. These automata are a special class of linear hybrid automata with only two variables, whose flows in all states is monotonic along some direction in the plane, and in which the continuous variables are not reset on a discrete transition.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., Yovine, S.: The algorithmic analysis of hybrid systems. Theoretical Computer Science 138(1), 3–34 (1995)
Alur, R., Dill, D.L.: A theory of timed automata. Theoretical Computer Science 126(2), 183–235 (1994)
Asarin, E., Maler, O., Pnueli, A.: Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science 138(1), 35–65 (1995)
Asarin, E., Schneider, G., Yovine, S.: Algorithmic analysis of polygonal hybrid systems, part I: Reachability. Theor. Comput. Sci. 379(1-2), 231–265 (2007)
Blondel, V.D., Bournez, O., Koiran, P., Papadimitriou, C.H., Tsitsiklis, J.N.: Deciding stability and mortality of piecewise affine dynamical systems. Theoretical Computer Science 255(1–2), 687–696 (2001)
Henzinger, T.A., Kopke, P.W., Puri, A., Varaiya, P.: What’s decidable about hybrid automata? In: Proc. 27th Annual ACM Symp. on Theory of Computing (STOC), pp. 373–382 (1995)
Karp, R.M., Miller, R.E.: Parallel program schemata. Journal of Computer and System Sciences 3(2), 147–195 (1969)
Lafferriere, G., Pappas, G., Sastry, S.: O-minimal hybrid systems (1998)
Prabhakar, P., Vladimerou, V., Viswanathan, M., Dullerud, G.E.: A Decidable Class of Planar Linear Hybrid Systems. Technical Report UIUCDCS-R-2008-2927, UIUC (January 2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Prabhakar, P., Vladimerou, V., Viswanathan, M., Dullerud, G.E. (2008). A Decidable Class of Planar Linear Hybrid Systems. In: Egerstedt, M., Mishra, B. (eds) Hybrid Systems: Computation and Control. HSCC 2008. Lecture Notes in Computer Science, vol 4981. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78929-1_29
Download citation
DOI: https://doi.org/10.1007/978-3-540-78929-1_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78928-4
Online ISBN: 978-3-540-78929-1
eBook Packages: Computer ScienceComputer Science (R0)