Behavioural Approximations for Restricted Linear Differential Hybrid Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Behavioural Approximations for Restricted Linear Differential Hybrid Automata

  • Conference paper
Hybrid Systems: Computation and Control (HSCC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3927))

Included in the following conference series:

Abstract

We show the regularity of the discrete time behaviour of hybrid automata in which the rates of continuous variables are governed by linear differential operators in a diagonal form and in which the values of the continuous variables can be observed only with finite precision. We do not demand resetting of the values of the continuous variables during mode changes. We can cope with polynomial guards and we can tolerate bounded delays both in sampling the values of the continuous variables and in effecting changes in their rates required by mode switchings. We also show that if the rates are governed by diagonalizable linear differential operators with rational eigenvalues and there is no delay in effecting rate changes, the discrete time behaviour of the hybrid automaton is recursive. However, the control state reachability problem in this setting is undecidable.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agrawal, M., Stephan, F., Thiagarajan, P.S., Yang, S.: Behavioural approximations for restricted linear differential hybrid automata. Technical Report TR42/05, School of Computing, National University of Singapore, Singapore (2005)

    Google Scholar 

  2. Agrawal, M., Thiagarajan, P.S.: Lazy rectangular hybrid automata. In: Alur, R., Pappas, G.J. (eds.) HSCC 2004. LNCS, vol. 2993, pp. 1–15. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Agrawal, M., Thiagarajan, P.S.: The discrete time behaviour of lazy linear hybrid automata. In: Morari, M., Thiele, L. (eds.) HSCC 2005. LNCS, vol. 3414, pp. 55–69. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Alur, R., Henzinger, T.A., Lafferriere, G., Pappas, G.J.: Discrete abstractions of hybrid systems. Proc. of the IEEE 88, 971–984 (2000)

    Article  Google Scholar 

  5. Baker, A.: Transcendental Number Theory. Cambridge University Press, Cambridge (1979)

    MATH  Google Scholar 

  6. Biere, A., Cimatti, A., Clarke, E.M., Strichman, O., Zhu, Y.: Bounded Model Checking. Advances in Computers 58. Academic Press, London (2003)

    Book  Google Scholar 

  7. Gupta, V., Henzinger, T.A., Jagadeesan, R.: Robust timed automata. In: Maler, O. (ed.) HART 1997. LNCS, vol. 1201, pp. 331–345. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  8. Henzinger, T.A.: The theory of hybrid automata. In: 11th LICS, pp. 278–292. IEEE Press, Los Alamitos (1996)

    Google Scholar 

  9. Henzinger, T.A., Kopke, P.W.: State equivalences for rectangular hybrid automata. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 530–545. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  10. Henzinger, T.A., Kopke, P.W., Puri, A., Varaiya, P.: What’s decidable about hybrid automata? J. of Comp. and Sys. Sci. 57, 94–124 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hirsch, M., Smale, S.: Differential Equations, Dynamical Systems and Linear Algebra. Academic Press, London (1974)

    MATH  Google Scholar 

  12. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)

    MATH  Google Scholar 

  13. Kesten, Y., Pnueli, A., Sifakis, J., Yovine, S.: Integration graphs: A class of decidable hybrid systems. In: Grossman, R.L., Ravn, A.P., Rischel, H., Nerode, A. (eds.) HS 1991 and HS 1992. LNCS, vol. 736, pp. 179–208. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  14. Lafferriere, G., Pappas, G.J., Sastr, S.: O-minimal hybrid systems. Math. Control Signals Systems 13, 1–21 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lafferriere, G., Pappas, G.J., Yovine, S.: Symbolic reachability computation for families of linear vector fields. J. Symbolic Computation 32, 231–253 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  16. Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press (1951)

    Google Scholar 

  17. Wilkie, A.: Schanuel’s conjecture and the decidability of the real exponential field. In: Algebraic Model Theory, pp. 223–230. Kluwer, Dordrecht (1997)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, India

    Manindra Agrawal

  2. School of Computing and Department of Mathematics, National University of Singapore (NUS), Singapore

    Frank Stephan

  3. School of Computing, National University of Singapore, Singapore

    P. S. Thiagarajan & Shaofa Yang

Authors
  1. Manindra Agrawal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frank Stephan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. S. Thiagarajan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shaofa Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Center for Control, Dynamical Systems and Computation, University of California, 93106, Santa Barbara, CA, USA

    João P. Hespanha

  2. SRI International, 333 Ravenswood Ave, Menlo Park, CA, USA

    Ashish Tiwari

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Agrawal, M., Stephan, F., Thiagarajan, P.S., Yang, S. (2006). Behavioural Approximations for Restricted Linear Differential Hybrid Automata. In: Hespanha, J.P., Tiwari, A. (eds) Hybrid Systems: Computation and Control. HSCC 2006. Lecture Notes in Computer Science, vol 3927. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730637_4

Download citation

  • DOI: https://doi.org/10.1007/11730637_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33170-4

  • Online ISBN: 978-3-540-33171-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation