Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Specification and Model Checking of Temporal Properties in Time Petri Nets and Timed Automata

  • Conference paper
Applications and Theory of Petri Nets 2004 (ICATPN 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3099))

Included in the following conference series:

Abstract

The paper surveys some of the most recent approaches to verification of properties, expressible in some timed and untimed temporal logics (LTL, CTL, TCTL), for real-time systems represented by time Petri nets (TPN’s) and timed automata (TA). Firstly, various structural translations from TPN’s to TA are discussed. Secondly, model abstraction methods, based on state class approaches for TPN’s, and on partition refinement for TA, are given. Next, SAT-based verification techniques, like bounded and unbounded model checking, are discussed. The main focus is on bounded model checking for TCTL and for reachability properties. The paper ends with a comparison of experimental results for several time Petri nets, obtained using the above solutions, i.e., either model abstractions for TPN’s, or a translation of a net to a timed automaton and then verification methods for TA. The experiments have been performed using some available tools for TA and TPN’s.

Partly supported by the State Committee for Scientific Research under the grant No. 3T11C 00426 and a special grant supporting ALFEBIITE.

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abdulla, P.A., Nylén, A.: Timed Petri Nets and BQOs. In: Colom, J.-M., Koutny, M. (eds.) ICATPN 2001. LNCS, vol. 2075, pp. 53–70. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  2. Alur, R., Courcoubetis, C., Dill, D.: Model checking for real-time systems. In: Proc. of LICS 1990, pp. 414–425. IEEE, Los Alamitos (1990)

    Google Scholar 

  3. Alur, R., Courcoubetis, C., Dill, D.: Model checking in dense real-time. Information and Computation 104(1), 2–34 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  4. Alur, R., Courcoubetis, C., Dill, D., Halbwachs, N., Wong-Toi, H.: An implementation of three algorithms for timing verification based on automata emptiness. In: Proc. of RTSS 1992, pp. 157–166. IEEE Comp. Soc. Press, Los Alamitos (1992)

    Google Scholar 

  5. Alur, R., Courcoubetis, C., Dill, D., Halbwachs, N., Wong-Toi, H.: Minimization of timed transition systems. In: Cleaveland, W.R. (ed.) CONCUR 1992. LNCS, vol. 630, pp. 340–354. Springer, Heidelberg (1992)

    Chapter  Google Scholar 

  6. Alur, R., Dill, D.: Automata for modelling real-time systems. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 322–335. Springer, Heidelberg (1990)

    Chapter  Google Scholar 

  7. Alur, R., Henzinger, T., Ho, P.: Automatic symbolic verification of embedded systems. IEEE Trans. on Software Eng. 22(3), 181–201 (1996)

    Article  Google Scholar 

  8. Alur, R., Kurshan, R.: Timing analysis in COSPAN. In: Alur, R., Sontag, E.D., Henzinger, T.A. (eds.) HS 1995. LNCS, vol. 1066, pp. 220–231. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  9. Asarin, E., Bozga, M., Kerbrat, A., Maler, O., Pnueli, A., Rasse, A.: Datastructures for the verification of Timed Automata. In: Maler, O. (ed.) HART 1997. LNCS, vol. 1201, pp. 346–360. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  10. Audemard, G., Cimatti, A., Kornilowicz, A., Sebastiani, R.: Bounded model checking for timed systems. In: Peled, D.A., Vardi, M.Y. (eds.) FORTE 2002. LNCS, vol. 2529, pp. 243–259. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  11. Behrmann, G., Larsen, K., Pearson, J., Weise, C., Yi, W.: Efficient timed reachability analysis using Clock Difference Diagrams. In: Halbwachs, N., Peled, D.A. (eds.) CAV 1999. LNCS, vol. 1633, pp. 341–353. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  12. Bengtsson, J.: Clocks, DBMs and States in Timed Systems. PhD thesis, Dept. of Information Technology, Uppsala University (2002)

    Google Scholar 

  13. Bengtsson, J., Yi, W.: On clock difference constraints and termination in reachability analysis in Timed Automata. In: Dong, J.S., Woodcock, J. (eds.) ICFEM 2003. LNCS, vol. 2885, pp. 491–503. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  14. Berthomieu, B., Diaz, M.: Modeling and verification of time dependent systems using Time Petri Nets. IEEE Trans. on Software Eng. 17(3), 259–273 (1991)

    Article  MathSciNet  Google Scholar 

  15. Berthomieu, B., Menasche, M.: An enumerative approach for analyzing Time Petri Nets. In: Proc. of the IFIP 9th World Computer Congress, September 1983. Information Processing, vol. 9, pp. 41–46. North Holland/IFIP (1983)

    Google Scholar 

  16. Berthomieu, B., Ribet, P.-O., Vernadat, F.: The tool TINA - construction of abstract state spaces for Petri nets and Time Petri Nets. International Journal of Production Research (2004) (to appear)

    Google Scholar 

  17. Berthomieu, B., Vernadat, F.: State class constructions for branching analysis of Time Petri Nets. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 442–457. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  18. Beyer, D.: Rabbit: Verification of real-time systems. In: Proc. of the Workshop on Real-Time Tools (RT-TOOLS 2001), pp. 13–21 (2001)

    Google Scholar 

  19. Bobbio, A., Horváth, A.: Model checking time Petri nets using NuSMV. In: Proc. of the 5th Int. Workshop on Performability Modeling of Computer and Communication Systems (PMCCS5), September 2001, pp. 100–104 (2001)

    Google Scholar 

  20. Bouajjani, A., Fernandez, J.-C., Halbwachs, N., Raymond, P., Ratel, C.: Minimal state graph generation. Science of Computer Programming 18, 247–269 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  21. Bouajjani, A., Tripakis, S., Yovine, S.: On-the-fly symbolic model checking for real-time systems. In: Proc. of RTSS 1997, pp. 232–243. IEEE Comp. Soc. Press, Los Alamitos (1997)

    Google Scholar 

  22. Boucheneb, H., Berthelot, G.: Towards a simplified building of Time Petri Nets reachability graph. In: Proc. of the 5th Int. Workshop on Petri Nets and Performance Models, October 1993, pp. 46–55 (1993)

    Google Scholar 

  23. Bowden, F.: Modelling time in Petri nets. In: Proc. of the 2nd Australia-Japan Workshop on Stochastic Models (STOMOD 1996) (July 1996)

    Google Scholar 

  24. Bryant, R.: Graph-based algorithms for boolean function manipulation. IEEE Transaction on Computers 35(8), 677–691 (1986)

    Article  MATH  Google Scholar 

  25. Cassez, F., Roux, O.H.: Traduction structurelle des Réseaux de Petri Temporels vers le Automates Temporisés. In: Proc. of 4ieme Colloque Francophone sur la Modélisation des Systémes Réactifs (MSR 2003). Hermes Science (October 2003)

    Google Scholar 

  26. Ciardo, G., Lüttgen, G., Simniceanu, R.: Efficient symbolic state-space construction for asynchronous systems. In: Nielsen, M., Simpson, D. (eds.) ICATPN 2000. LNCS, vol. 1825, pp. 103–122. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  27. Coolahan, J., Roussopoulos, N.: Timing requirements for time-driven systems using augmented Petri nets. IEEE Trans. on Software Eng. SE-9(5), 603–616 (1983)

    Article  Google Scholar 

  28. Cortés, L.A., Eles, P., Peng, Z.: Verification of real-time embedded systems using Petri net models and Timed Automata. In: Proc. of the 8th Int. Conf. on Real-Time Computing Systems and Applications (RTCSA 2002), March 2002, pp. 191–199 (2002)

    Google Scholar 

  29. Couvreur, J.-M., Encrenaz, E., Paviot-Adet, E., Pointrenaud, D., Wacrenier, P.-A.: Data Decision Diagrams for Petri net analysis. In: Esparza, J., Lakos, C.A. (eds.) ICATPN 2002. LNCS, vol. 2360, pp. 101–120. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  30. Daws, C., Tripakis, S.: Model checking of real-time reachability properties using abstractions. In: Steffen, B. (ed.) TACAS 1998. LNCS, vol. 1384, pp. 313–329. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  31. Dembiński, P., Janowska, A., Janowski, P., Penczek, W., Półrola, A., Szreter, M., Woźna, B., Zbrzezny, A.: VerICS: A tool for verifying Timed Automata and Estelle specifications. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 278–283. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  32. Dembiński, P., Penczek, W., Półrola, A.: Verification of Timed Automata based on similarity. Fundamenta Informaticae 51(1-2), 59–89 (2002)

    MATH  MathSciNet  Google Scholar 

  33. Dickhofer, M., Wilke, T.: Timed Alternating Tree Automata: The automatatheoretic solution to the TCTL model checking problem. In: Proc. of ICALP 1998. LNCS, vol. 1664, pp. 281–290. Springer, Heidelberg (1998)

    Google Scholar 

  34. Dill, D.: Timing assumptions and verification of finite state concurrent systems. In: Sifakis, J. (ed.) CAV 1989. LNCS, vol. 407, pp. 197–212. Springer, Heidelberg (1989)

    Google Scholar 

  35. Gardey, G., Roux, O.H., Roux, O.F.: Using zone graph method for computing the state space of a Time Petri Net. In: Larsen, K.G., Niebert, P. (eds.) FORMATS 2003. LNCS, vol. 2791. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  36. Gu, Z., Shin, K.: Analysis of event-driven real-time systems with Time Petri Nets. In: Proc. of DIPES 2002. IFIP Conference Proceedings, vol. 219, pp. 31–40. Kluwer, Dordrecht (2002)

    Google Scholar 

  37. Haar, S., Kaiser, L., Simonot-Lion, F., Toussaint, J.: On equivalence between Timed State Machines and Time Petri Nets. Technical Report RR-4049, INRIA Rhône-Alpes, 655, avenue de l’Europe, 38330 Montbonnot-St-Martin (November 2000)

    Google Scholar 

  38. Hanisch, H.-M.: Analysis of place/transition nets with timed arcs and its application to batch process control. In: Ajmone Marsan, M. (ed.) ICATPN 1993. LNCS, vol. 691, pp. 282–299. Springer, Heidelberg (1993)

    Google Scholar 

  39. Henzinger, T., Ho, P.: HyTech: The Cornell hybrid technology tool. In: Antsaklis, P.J., Kohn, W., Nerode, A., Sastry, S.S. (eds.) HS 1994. LNCS, vol. 999, pp. 265–293. Springer, Heidelberg (1995)

    Google Scholar 

  40. Henzinger, T., Nicollin, X., Sifakis, J., Yovine, S.: Symbolic model checking for real-time systems. Information and Computation 111(2), 193–224 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  41. Huhn, M., Niebert, P., Wallner, F.: Verification based on local states. In: Steffen, B. (ed.) TACAS 1998. LNCS, vol. 1384, pp. 36–51. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  42. Hulgaard, H., Burns, S.M.: Efficient timing analysis of a class of Petri Nets. In: Wolper, P. (ed.) CAV 1995. LNCS, vol. 939, pp. 923–936. Springer, Heidelberg (1995)

    Google Scholar 

  43. Janicki, R.: Nets, sequential components and concurrency relations. Theoretical Computer Science 29, 87–121 (1984)

    Article  MathSciNet  Google Scholar 

  44. Kang, I., Lee, I.: An efficient state space generation for the analysis of real-time systems. In: Proc. of Int. Symposium on Software Testing and Analysis (1996)

    Google Scholar 

  45. Kupferman, O., Henzinger, T.A., Vardi, M.Y.: A space-efficient on-the-fly algorithm for real-time model checking. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 514–529. Springer, Heidelberg (1996)

    Google Scholar 

  46. Larsen, K.G., Larsson, F., Pettersson, P., Yi, W.: Efficient verification of realtime systems: Compact data structures and state-space reduction. In: Proc. of RTSS 1997, pp. 14–24. IEEE Comp. Soc. Press, Los Alamitos (1997)

    Google Scholar 

  47. Lee, D., Yannakakis, M.: On-line minimization of transition systems. In: Proc. of the 24th ACM Symp. on the Theory of Computing, May 1992, pp. 264–274 (1992)

    Google Scholar 

  48. Lilius, J.: Efficient state space search for Time Petri Nets. In: Proc. of MFCS Workshop on Concurrency, Brno 1998. ENTCS, vol. 18. Elsevier Science Publishers, Amsterdam (1999)

    Google Scholar 

  49. Lime, D., Roux, O.H.: State class timed automaton of a time Petri net. In: Proc. of the 10th Int. Workshop on Petri Nets and Performance Models (PNPM 2003), September 2003. IEEE Comp. Soc. Press, Los Alamitos (2003)

    Google Scholar 

  50. McMillan, K.L.: Applying SAT methods in unbounded symbolic model checking. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 250–264. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  51. Merlin, P., Farber, D.J.: Recoverability of communication protocols – implication of a theoretical study. IEEE Trans. on Communications 24(9), 1036–1043 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  52. Miner, A., Ciardo, G.: Efficient reachability set generation and storage using decision diagrams. In: Donatelli, S., Kleijn, J. (eds.) ICATPN 1999. LNCS, vol. 1639, pp. 6–25. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  53. Molinaro, P., Roux, D., Delfieu, O.: Improving the calculus of the marking graph of Petri net with BDD like structure. In: Proc. of the 2nd IEEE Int. Conf. on Systems, Man and Cybernetics (SMC 2002), October 2002. IEEE Computer Society Press, Los Alamitos (2002)

    Google Scholar 

  54. Møller, J., Lichtenberg, J., Andersen, H., Hulgaard, H.: Difference Decision Diagrams. In: Flum, J., Rodríguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol. 1683, pp. 111–125. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  55. Møller, J., Lichtenberg, J., Andersen, H., Hulgaard, H.: Fully symbolic model checking of timed systems using Difference Decision Diagrams. In: Proc. of FLoC 1999. ENTCS, vol. 23(2) (1999)

    Google Scholar 

  56. Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Proc. of the 38th Design Automation Conference (DAC 2001), June 2001, pp. 530–535 (2001)

    Google Scholar 

  57. Niebert, P., Mahfoudh, M., Asarin, E., Bozga, M., Maler, O., Jain, N.: Verification of Timed Automata via satisfiability checking. In: Damm, W., Olderog, E.-R. (eds.) FTRTFT 2002. LNCS, vol. 2469, pp. 226–243. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  58. Okawa, Y., Yoneda, T.: Symbolic CTL model checking of Time Petri Nets. Electronics and Communications in Japan, Scripta Technica 80(4), 11–20 (1997)

    Google Scholar 

  59. Paige, R., Tarjan, R.: Three partition refinement algorithms. SIAM Journal on Computing 16(6), 973–989 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  60. Pastor, E., Cortadella, J., Roig, O.: Symbolic Petri net analysis using boolean manipulation. Technical Report RR-97-08, UP/DAC, Univerisitat Politécnica de Catalunya (February 1997)

    Google Scholar 

  61. Penczek, W., Półrola, A.: Abstractions and partial order reductions for checking branching properties of Time Petri Nets. In: Colom, J.-M., Koutny, M. (eds.) ICATPN 2001. LNCS, vol. 2075, pp. 323–342. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  62. Penczek, W., Woźna, B., Zbrzezny, A.: Bounded model checking for the universal fragment of CTL. Fundamenta Informaticae 51(1-2), 135–156 (2002)

    MATH  MathSciNet  Google Scholar 

  63. Penczek, W., Woźna, B., Zbrzezny, A.: Towards bounded model checking for the universal fragment of TCTL. In: Damm, W., Olderog, E.-R. (eds.) FTRTFT 2002. LNCS, vol. 2469, pp. 265–288. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  64. Półrola, A., Penczek, W.: Minimization algorithms for Time Petri Nets. Fundamenta Informaticae (2004) (to appear)

    Google Scholar 

  65. Półrola, A., Penczek, W., Szreter, M.: Reachability analysis for Timed Automata using partitioning algorithms. Fundamenta Informaticae 55(2), 203–221 (2003)

    MATH  MathSciNet  Google Scholar 

  66. Półrola, A., Penczek, W., Szreter, M.: Towards efficient partition refinement for checking reachability in Timed Automata. In: Larsen, K.G., Niebert, P. (eds.) FORMATS 2003. LNCS, vol. 2791. Springer, Heidelberg (2004)

    Google Scholar 

  67. Popova, L., Marek, S.: TINA - a tool for analyzing paths in TPNs. In: Proc. of the Int. Workshop on Concurrency, Specification and Programming (CS&P 2002). Informatik-Berichte, vol. 110, pp. 195–196. Humboldt University (1998)

    Google Scholar 

  68. Ramchandani, C.: Analysis of asynchronous concurrent systems by timed Petri nets. Technical Report MAC-TR-120, Massachusets Institute of Technology (February 1974)

    Google Scholar 

  69. Ratzer, A., Wells, L., Lassen, H., Laursen, M., Qvortrup, J., Stissing, M., Westergaard, M., Christensen, S., Jensen, K.: CPN Tools for editing, simulating, and analyzing Coloured Petri Nets. In: van der Aalst, W.M.P., Best, E. (eds.) ICATPN 2003. LNCS, vol. 2679, pp. 450–462. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  70. Romeo: A tool for Time Petri Net analysis (2000), http://www.irccyn.ec-nantes.fr/irccyn/d/en/equipes/TempsReel/logs

  71. Samolej, S., Szmuc, T.: Modelowanie systemów czasu rzeczywistego z zastosowaniem czasowych sieci Petriego. In: Mat. IX Konf. Systemy Czasu Rzeczywistego (SCR 2002), Instytut Informatyki Politechniki Śla̧skiej, pp. 45–54 (2002) (in Polish)

    Google Scholar 

  72. Sénac, P., Diaz, M., de Saqui Sannes, P.: Toward a formal specification of multimedia scenarios. Annals of Telecommunications 49(5-6), 297–314 (1994)

    Google Scholar 

  73. Seshia, S., Bryant, R.: Unbounded, fully symbolic model checking of Timed Automata using boolean methods. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 154–166. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  74. Sifakis, J., Yovine, S.: Compositional specification of timed systems. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 347–359. Springer, Heidelberg (1996)

    Google Scholar 

  75. Sorea, M.: Bounded model checking for Timed Automata. In: Proc. of MTCS 2002. ENTCS, vol. 68(5). Elsevier Science Publishers, Amsterdam (2002)

    Google Scholar 

  76. Spelberg, R.L., Toetenel, H., Ammerlaan, M.: Partition refinement in real-time model checking. In: Ravn, A.P., Rischel, H. (eds.) FTRTFT 1998. LNCS, vol. 1486, pp. 143–157. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  77. Strehl, K., Thiele, L.: Interval diagram techniques for symbolic model checking of Petri nets. In: Proc. of DATE 1999. LNCS, pp. 756–757. IEEE Comp. Soc. Press, Los Alamitos (1999)

    Google Scholar 

  78. Strichman, O., Seshia, S., Bryant, R.: Deciding separation formulas with SAT. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 209–222. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  79. Tripakis, S., Yovine, S.: Analysis of timed systems using time-abstracting bisimulations. Formal Methods in System Design 18(1), 25–68 (2001)

    Article  MATH  Google Scholar 

  80. Tsai, J., Yang, S., Chang, Y.: Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications. IEEE Trans. on Software Eng. 21(1), 32–49 (1995)

    Article  Google Scholar 

  81. van der Aalst, W.: Interval timed coloured Petri nets and their analysis. In: Ajmone Marsan, M. (ed.) ICATPN 1993. LNCS, vol. 691, pp. 452–472. Springer, Heidelberg (1993)

    Google Scholar 

  82. Virbitskaite, B., Pokozy, E.A.: A partial order method for the verification of Time Petri Nets. In: Ciobanu, G., Păun, G. (eds.) FCT 1999. LNCS, vol. 1684, pp. 547–558. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  83. Walter, B.: Timed Petri nets for modelling and analysing protocols with real-time characteristics. In: Proc. of the 3rd IFIP Workshop on Protocol Specification, Testing, and Verification, pp. 149–159. North Holland, Amsterdam (1983)

    Google Scholar 

  84. Wang, F.: Region Encoding Diagram for fully symbolic verification of real-time systems. In: Proc. of the 24th Int. Computer Software and Applications Conf. (COMPSAC 2000), October 2000, pp. 509–515. IEEE Comp. Soc. Press, Los Alamitos (2000)

    Chapter  Google Scholar 

  85. Wang, F.: Verification of Timed Automata with BDD-like data structures. In: Zuck, L.D., Attie, P.C., Cortesi, A., Mukhopadhyay, S. (eds.) VMCAI 2003. LNCS, vol. 2575, pp. 189–205. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  86. Woźna, B., Zbrzezny, A., Penczek, W.: Checking reachability properties for Timed Automata via SAT. Fundamenta Informaticae 55(2), 223–241 (2003)

    MATH  MathSciNet  Google Scholar 

  87. Yannakakis, M., Lee, D.: An efficient algorithm for minimizing real-time transition systems. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol. 697, pp. 210–224. Springer, Heidelberg (1993)

    Google Scholar 

  88. Yi, W., Pettersson, P., Daniels, M.: Automatic verification of real-time communicating systems by constraint-solving. In: Proc. of the 7th IFIP WG6.1 Int. Conf. on Formal Description Techniques (FORTE 1994). IFIP Conference Proceedings, vol. 6, pp. 243–258. Chapman & Hall, Boca Raton (1994)

    Google Scholar 

  89. Yoneda, T., Ryuba, H.: CTL model checking of Time Petri Nets using geometric regions. IEICE Trans. Inf. and Syst. 3, 1–10 (1998)

    Google Scholar 

  90. Yoneda, T., Schlingloff, B.H.: Efficient verification of parallel real-time systems. Formal Methods in System Design 11(2), 197–215 (1997)

    Article  Google Scholar 

  91. Yovine, S.: KRONOS: A verification tool for real-time systems. Springer International Journal of Software Tools for Technology Transfer 1(1/2), 123–133 (1997)

    Article  MATH  Google Scholar 

  92. Zbrzezny, A.: Improvements in SAT-based reachability analysis for Timed Automata. Fundamenta Informaticae (2004) (to appear)

    Google Scholar 

  93. Zhang, L., Madigan, C., Moskewicz, M., Malik, S.: Efficient conflict driven learning in a boolean satisfiability solver. In: Proc. of Int. Conf. on Computer-Aided Design (ICCAD 2001), pp. 279–285 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Science, PAS, Ordona 21, 01-237, Warsaw, Poland

    Wojciech Penczek

  2. Institute of Informatics, Podlasie Academy, Sienkiewicza 51, 08-110, Siedlce, Poland

    Wojciech Penczek

  3. Faculty of Mathematics, University of Lodz, Banacha 22, 90-238, Lodz, Poland

    Agata Półrola

Authors
  1. Wojciech Penczek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Agata Półrola
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universitat Politècnica de Catalunya, Spain

    Jordi Cortadella

  2. Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany

    Wolfgang Reisig

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Penczek, W., Półrola, A. (2004). Specification and Model Checking of Temporal Properties in Time Petri Nets and Timed Automata. In: Cortadella, J., Reisig, W. (eds) Applications and Theory of Petri Nets 2004. ICATPN 2004. Lecture Notes in Computer Science, vol 3099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27793-4_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-27793-4_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-22236-1

  • Online ISBN: 978-3-540-27793-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation