Abstract
This paper introduces and formalizes a new variant of Timed Automata, called Time Labeled Scheduling Automata. A Time Labeled Scheduling Automaton is a single clock implementation model expressing globally the time constraints that a system has to meet. An algorithm is presented to show how a Time Labeled Scheduling Automaton can be synthesized from a minimal reachability graph derived from a high-level specification expressing the composition of different time constraints. It is shown how the reachability graph may be corrected before synthesizing the Time Labeled Scheduling Automaton to remove all its potentially inconsistent behaviors. Current applications of the model are the scheduling of interactive multimedia documents and a simple illustration is given in this area.
Chapter PDF
Similar content being viewed by others
Keywords
References
K. Altisen, G. Gossler, and J. Sifakis. A methodology for the construction of scheduled systems. In FTRTFT 2000, volume 1926 of Lecture Notes in Computer Science, pages 106–120, Pune, India, September 2000.
R. Alur, C. Courcoubetis, and N. Halbwachs. Minimization of timed transition systems. In CONCUR’92, volume 630 of Lecture Notes in Computer Science. Springer Verlag, 1992.
R. Alur and D. Dill. The theory of timed automata. In REX Workshop “Real-Time: Theory in Practice”, volume 600 of Lecture Notes in Computer Science. Springer Verlag, 1991.
R. Alur, L. Fix, and T.A. Heizinger. Event-clock automata: A determinizable class of timed automata. In 6 th Annual Conference on Computeraided Verification, Lecture Notes in Computer Science 818, pages 1–13. Springer Verlag, 1994.
E. Asarin, O. Maler, and A. Pnueli. Symbolic controller synthesis for discrete and timed systems. In Hybrid Systems, pages 1–20, 1994.
B. Berthomieu and M. Diaz. Modeling and verification of time-dependent systems using time Petri nets. In IEEE Transactions on Software Engineering, volume 17. nℴ3, 1991.
J.P. Courtiat and R.C. R. de Oliveira. A reachability analysis of RT-Lotos specifications. In 8 th International Conference on Formal Description Techniques, Montreal, Canada, October 1995. Chapman&Hall.
J.P Courtiat, C.A.S. Santos, C. Lohr, and B. Outtaj. Experience with RT-Lotos, a temporal extension of the Lotos formal description technique. Computer Communications, 23:1104–1123, 2000.
H. Dierks. Synthesising controllers from real-time specifications. In Tenth International Symposium on System Synthesis, pages 126–133. IEEE Computer Society, September 1997.
I. Kang and I. Lee. An efficient state space generation for analysis of real-time systems. In International Symposium on Software Testing and Analysis, pages 4–13, 1996.
X. Nicollin and J. Sifakis. An overview and synthesis on timed process algebras. In REX Workshop “Real-Time: Theory in Practice”, volume 600 of Lecture Notes in Computer Science. Springer Verlag, 1991.
A. Pnueli, E. Asarin, O. Maler, and J. Sifakis. Controller synthesis for timed automata. In System Structure and Control. Elsevier Science, 1998.
P.N.M. Sampaio and J.P. Courtiat. A formal approach for the presentation of interactive multimedia documents. In ACM Multimedia’2000, pages 435–438, Los Angeles, USA, October 2000.
P.N.M. Sampaio and J.P. Courtiat. Scheduling and presenting interactive multimedia documents. In International Conference on Multimedia and Exposition’2001, pages 1227–1227, Tokyo, Japan, August 2001.
P.N.M Sampaio, C. Lohr, and J.P. Courtiat. An integrated environment for the presentation of consistent SMIL 2.0 documents. In ACM Symposium on Document Engineering, Atlanta, Georgia, USA, November 2001.
C.A.S. Santos, P.N.M. Sampaio, and J.P. Courtiat. Revisiting the concept of hypermedia document consistency. In ACM Multimedia’99, Orlando, USA, November 1999.
P. Sénac, M. Diaz, A. Leger, and P. de Saqui-Sannes. Modelling logical and temporal synchronization in hypermedia systems. In IEEE Journal on Selected Areas in Communications, volume 14(1), pages 84–103, January 1996.
M. Yannakakis and D. Lee. An efficient algorithm for minimizing real-time transition systems. In CAV’93, volume 697 of Lecture Notes in Computer Science. Springer Verlag, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lohr, C., Courtiat, JP. (2002). From the Specification to the Scheduling of Time-Dependent Systems. In: Damm, W., Olderog, E.R. (eds) Formal Techniques in Real-Time and Fault-Tolerant Systems. FTRTFT 2002. Lecture Notes in Computer Science, vol 2469. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45739-9_10
Download citation
DOI: https://doi.org/10.1007/3-540-45739-9_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44165-6
Online ISBN: 978-3-540-45739-8
eBook Packages: Springer Book Archive