Parametric Timed Bisimulation | SpringerLink
Skip to main content
Springer Nature Link
Log in

Parametric Timed Bisimulation

  • Conference paper
  • First Online:
Leveraging Applications of Formal Methods, Verification and Validation: Engineering Principles (ISoLA 2020)

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

Included in the following conference series:

  • 648 Accesses

Abstract

Timed automata (TA) constitute a mature formalism for discrete-state/continuous-time behavior of time-critical cyber-physical systems. Concerning the fundamental analysis problem of comparing a candidate implementation against a specification both given as TA, it has been shown that timed trace equivalence is undecidable, whereas timed bisimulation is decidable. However, the limited expressiveness of TA is a serious obstacle in practice such that many TA extensions have been proposed. For instance, parametric timed automata (PTA) incorporate parametric clock constraints with freely-adjustable time intervals thus generalizing the constant time bounds of TA. In this way, PTA constitute a promising theoretical foundation for re-engineering static real-time specifications, originally given as TA, in a generic and customizable way. In this paper, we provide, to the best of our knowledge, the first proposal for lifting the notion of timed bisimulation from TA to PTA. Unfortunately, as PTA are Turing-complete, most interesting semantic properties being decidable for TA (including timed bisimulation), become undecidable for PTA. To tackle this issue, we propose an over-approximation of PTA semantics in terms of plain TA semantics and investigate decidability properties of a promising sub-class of PTA, called L/U-PTA.

L. Luthmann—This work was funded by the Hessian LOEWE initiative within the Software-Factory 4.0 project.

H. Göttmann—This work has been funded by the German Research Foundation (DFG) as part of project A4 within the Collaborative Research Center (CRC) 1053 MAKI.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Alur, R., Dill, D.: Automata for modeling real-time systems. In: Paterson, M.S. (ed.) ICALP 1990. LNCS, vol. 443, pp. 322–335. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0032042

    Chapter  MATH  Google Scholar 

  2. Alur, R., Henzinger, T.A., Vardi, M.Y.: Parametric real-time reasoning. In: STOC 1993, pp. 592–601. ACM (1993). https://doi.org/10.1145/167088.167242

  3. Alur, R., Madhusudan, P.: Decision problems for timed automata: a survey. In: Bernardo, M., Corradini, F. (eds.) SFM-RT 2004. LNCS, vol. 3185, pp. 1–24. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30080-9_1

    Chapter  MATH  Google Scholar 

  4. André, É.: What’s decidable about parametric timed automata? In: Artho, C., Ölveczky, P.C. (eds.) FTSCS 2015. CCIS, vol. 596, pp. 52–68. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29510-7_3

    Chapter  Google Scholar 

  5. André, É.: What’s decidable about parametric timed automata? Int. J. Softw. Tools Technol. Transf. 21(2), 203–219 (2017). https://doi.org/10.1007/s10009-017-0467-0

    Article  Google Scholar 

  6. Bengtsson, J., Yi, W.: Timed automata: semantics, algorithms and tools. In: Desel, J., Reisig, W., Rozenberg, G. (eds.) ACPN 2003. LNCS, vol. 3098, pp. 87–124. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27755-2_3

    Chapter  MATH  Google Scholar 

  7. Bérard, B., Petit, A., Diekert, V., Gastin, P.: Characterization of the expressive power of silent transitions in timed automata. Fundamenta Informaticae 36(2,3), 145–182 (1998). https://doi.org/10.3233/FI-1998-36233

    Article  MathSciNet  MATH  Google Scholar 

  8. Čerāns, K.: Decidability of bisimulation equivalences for parallel timer processes. In: von Bochmann, G., Probst, D.K. (eds.) CAV 1992. LNCS, vol. 663, pp. 302–315. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-56496-9_24

    Chapter  Google Scholar 

  9. Cordy, M., Schobbens, P.Y., Heymans, P., Legay, A.: Behavioural modelling and verification of real-time software product lines. In: Proceedings of the 16th International Software Product Line Conference, vol. 1, pp. 66–75. ACM (2012)

    Google Scholar 

  10. Guha, S., Krishna, S.N., Narayan, C., Arun-Kumar, S.: A unifying approach to decide relations for timed automata and their game characterization. In: EXPRESS/SOS’13. EPTCS, vol. 120 (2013). https://doi.org/10.4204/EPTCS.120.5

  11. Guha, S., Narayan, C., Arun-Kumar, S.: On decidability of prebisimulation for timed automata. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 444–461. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31424-7_33

    Chapter  Google Scholar 

  12. Henzinger, T.A., Manna, Z., Pnueli, A.: Timed transition systems. In: de Bakker, J.W., Huizing, C., de Roever, W.P., Rozenberg, G. (eds.) REX 1991. LNCS, vol. 600, pp. 226–251. Springer, Heidelberg (1992). https://doi.org/10.1007/BFb0031995

    Chapter  Google Scholar 

  13. Henzinger, T.A., Nicollin, X., Sifakis, J., Yovine, S.: Symbolic model checking for real-time systems. Inf. Comput. 111(2), 193–244 (1994). https://doi.org/10.1006/inco.1994.1045

    Article  MathSciNet  MATH  Google Scholar 

  14. Hune, T., Romijn, J., Stoelinga, M., Vaandrager, F.: Linear parametric model checking of timed automata. J. Logic Algebraic Program. 52–53, 183–220 (2002). https://doi.org/10.1016/S1567-8326(02)00037-1

    Article  MathSciNet  MATH  Google Scholar 

  15. Liva, G., Khan, M.T., Pinzger, M.: Extracting timed automata from java methods. In: 2017 IEEE 17th International Working Conference on Source Code Analysis and Manipulation (SCAM), pp. 91–100. IEEE (2017)

    Google Scholar 

  16. Luthmann, L., Stephan, A., Bürdek, J., Lochau, M.: Modeling and testing product lines with unbounded parametric real-time constraints. In: Proceedings of the 21st International Systems and Software Product Line Conference - Volume A, SPLC 2017, pp. 104–103. ACM, New York (2017). https://doi.org/10.1145/3106195.3106204

  17. Moller, F., Tofts, C.: A temporal calculus of communicating systems. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 401–415. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0039073

    Chapter  Google Scholar 

  18. Nicollin, X., Sifakis, J.: The algebra of timed processes, ATP: theory and application. Inf. Comput. 114(1), 131–178 (1994). https://doi.org/10.1006/inco.1994.1083

    Article  MathSciNet  MATH  Google Scholar 

  19. Waez, M.T.B., Dingel, J., Rudie, K.: A survey of timed automata for the development of real-time systems. Comput. Sci. Rev. 9, 1–26 (2013). https://doi.org/10.1016/j.cosrev.2013.05.001

    Article  MATH  Google Scholar 

  20. Weise, C., Lenzkes, D.: Efficient scaling-invariant checking of timed bisimulation. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 177–188. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0023458

    Chapter  Google Scholar 

  21. Wang, Y.: Real-time behaviour of asynchronous agents. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 502–520. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0039080

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Model-Based Engineering Group, University of Siegen, Siegen, Germany

    Malte Lochau

  2. Real-Time Systems Lab, Technical University of Darmstadt, Darmstadt, Germany

    Lars Luthmann, Hendrik Göttmann & Isabelle Bacher

Authors
  1. Malte Lochau
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lars Luthmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hendrik Göttmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Isabelle Bacher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Malte Lochau , Lars Luthmann , Hendrik Göttmann or Isabelle Bacher .

Editor information

Editors and Affiliations

  1. University of Limerick and Lero, Limerick, Ireland

    Tiziana Margaria

  2. TU Dortmund, Dortmund, Germany

    Bernhard Steffen

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Lochau, M., Luthmann, L., Göttmann, H., Bacher, I. (2020). Parametric Timed Bisimulation. In: Margaria, T., Steffen, B. (eds) Leveraging Applications of Formal Methods, Verification and Validation: Engineering Principles. ISoLA 2020. Lecture Notes in Computer Science(), vol 12477. Springer, Cham. https://doi.org/10.1007/978-3-030-61470-6_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-61470-6_5

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-61469-0

  • Online ISBN: 978-3-030-61470-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation