Specification and Modeling of Reactive Real-Time Systems

Edward A. Lee

This is an evolving list. Please send updates or additional references to eal@eecs.berkeley.edu. Ideally, send the HTML formatting. When colors are used, they have the following meaning:

References

    Automata

  1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979.
  2. A. Mazurkiewicz, ``Traces, Histories, Graphs: Instances of a Process Monoid,'' in Proc. Conf. on Mathematical Founations of Computer Science, M. P. Chytil and V. Koubek, eds., Springer-Verlag LNCS 176, 1984.
  3. G. E. Revesz, Introduction to Formal Languages, Dover Publications Inc., New York, 1983.

    Concurrency

  4. S. Abramsky, ``Reasoning About Concurrent Systems,'' in F. B. Chambers, D. A. Duce, and G. P. Jones, editors, Distributed Computing, Academic Press, London, 1984.
  5. G. Berry, P.-L. Curien, ``Theory and Practice of Sequential Algorithms: the Kernel of the Applicative Language CDS,'' in Algebraic Methods in Semantics, M. Nivat and J. C. Reynolds (eds.), Cambridge University Press, 1985.
  6. N. Carriero and D. Gelernter, ``Linda in Context,'' Comm. of the ACM, Vol. 32, No. 4, pp. 444-458, April 1989.
  7. P. Caspi, D. Pilaud, N. Halbwachs, and J. A. Plaice, ``LUSTRE: A Declarative Language for Programming Synchronous Systems,'' Conference Record of the 14th Annual ACM Symp. on Principles of Programming Languages, Munich, Germany, January, 1987.
  8. J. W. De Bakker and J. I. Zucker, "Processes and the Denotational Semantics of Concurrency," Information and Control, Vol. 54, pp 70-120, 1982.
  9. E. Dijkstra, ``Cooperating Sequential Processes'', in Programming Languages, E F. Genuys, editor, Academic Press, New York, 1968.
  10. G. Kahn, ``The Semantics of a Simple Language for Parallel Programming,'' Proc. of the IFIP Congress 74, North-Holland PubG. Kahn, ``The Semantics of a Simple Language for Parallel Programming,'' Proc. of the IFIP Congress 74, North-Holland Publishing Co., 1974.
  11. G. Kahn and D. B. MacQueen, ``Coroutines and Networks of Parallel Processes,'' Information Processing 77, B. Gilchrist, editor, North-Holland Publishing Co., 1977.
  12. C. A. R. Hoare, ``Communicating Sequential Processes,'' Communications of the ACM, Vol. 21, No. 8, August 1978.
  13. L. Lamport, ``Time, Clocks, and the Ordering of Events in a Distributed System,'' Communications of the ACM, Vol. 21, No. 7, July, 1978.
  14. R. Milner, Communication and Concurrency, Prentice-Hall, Englewood Cliffs, NJ, 1989.
  15. T. M. Parks, Bounded Scheduling of Process Networks, Technical Report UCB/ERL-95-105. PhD Dissertation. EECS Department, University of California. Berkeley, CA 94720, December 1995.
  16. J. L. Peterson, ``Petri Nets'', Computing Surveys, Vol. 9, No. 3, September, 1977.
  17. V. R. Pratt, ``Modeling Concurrency with Partial Orders,'' Int. J. of Parallel Programming, Vol. 15, No. 1, pp. 33-71, Feb. 1986.
  18. D. Scott, ``Outline of a mathematical theory of computation'', Proc. of the 4th annual Princeton conf. on Information sciences and systems, 1970, 169-176.
  19. V. A. Saraswat, Concurrent Constraint Programming, The MIT Press, Cambridge, MA, 1993.

    Dataflow

  20. W. B. Ackerman, ``Data Flow Languages,'' Computer, Vol. 15, No. 2, February 1982.
  21. Arvind and K. P. Gostelow, ``The U-Interpreter'', Computer, 15(2), February 1982.
  22. E. A. Ashcroft and W. W. Wadge, ``Lucid, a Nonprocedural Language with Iteration,'' Comm. of the ACM, vol. 20, no. 7, pp. 519-526, July 1977.
  23. S. S. Bhattacharyya, P. K. Murthy and E. A. Lee, ``Software Synthesis from Dataflow Graphs., Kluwer Academic Publishers, Norwell, Mass, 1996.
  24. J. T. Buck, Scheduling Dynamic Dataflow Graphs with Bounded Memory Using the Token Flow Model, Tech. Report UCB/ERL 93/69, Ph.D. Dissertation, Dept. of EECS, University of California, Berkeley, CA 94720, 1993.
  25. W.-T. Chang, A. Kalavade, and E. A. Lee, ``Effective Heterogeneous Design and Cosimulation,'', NATO Advanced Study Institute Workshop on Hardware/Software Codesign, Lake Como, Italy, June 18 -- 30, 1995 .
  26. A. L. Davis and R. M. Keller, ``Data Flow Program Graphs'', Computer, 15(2), February, 1982.
  27. J. B. Dennis, ``First Version Data Flow Procedure Language'', Technical Memo MAC TM61, May, 1975, MIT Laboratory for Computer Science.
  28. R. M. Karp, R. E. Miller, ``Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing,'' SIAM Journal, Vol. 14, pp. 1390-1411, November, 1966.
  29. E. A. Lee and A. Sangiovanni-Vincentelli, ``The Tagged Signal Model --A Preliminary Version of a Denotational Framework for Comparing Models of Computation,'' ERL Memorandum UCB/ERL M96/33, University of California, Berkeley, CA 94720, June 4, 1996.
  30. E. A. Lee and T. M. Parks, ``Dataflow Process Networks,'', Proceedings of the IEEE, vol. 83, no. 5, pp. 773-801, May, 1995.
  31. E. A. Lee and D. G. Messerschmitt, ``Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing,'' IEEE Trans. on Computers, January, 1987.
  32. S. G. Matthews, "An Extensional Treatment of Lazy Data flow Deadlock," Theoretical Computer Science, Vol. 151, pp. 195-205, 1995.
  33. E.W. Stark, ``An algebra of dataflow networks,'' Fundamenta Informaticae, Jan.-Feb. 1995, vol.22, (no.1-2):167-85.
  34. W. W. Wadge and E. A. Ashcroft, Lucid, the dataflow programming language, London Academic Press, 1985.

    Discrete-Event Systems

  35. F. Baccelli, G. Cohen, G. J. Olsder, J.-P. Quadrat, Synchronization and Linearity - An Algebra for Discrete Event Systems, John Wiley & Sons, New York, 1992.
  36. C. Cassandras, Discrete Event Systems, Modeling and Performance Analysis, Irwin, Homewood IL, 1993.
  37. G. S. Fishman, Principles of Discrete Event Simulation, Wiley, New York, 1978.
  38. Y.-C. Ho (Ed.), Discrete Event Dynamic Systems: Analyzing Complexity and Performance in the Modern World, IEEE Press, New York, 1992.
  39. D. Jefferson, ``Virtual Time,'' ACM Trans. Programming Languages and Systems, Vol. 7, No. 3, 1985, pp. 404-425.
  40. J. Misra, ``Distributed Discrete Event Simulation,'' ACM Computing Surveys, Vol. 18, No. 1, 1986, pp. 39-65.
  41. R. Righter and J. Walrand, ``Distributed Simulation of Discrete Event Systems,'' Proc. IEEE, Jan., 1989, pp. 99-113.

    Functional Programming

  42. Arvind and J. D. Brock, ``Resource Managers in Functional Programming,'' J. of Parallel and Distributed Computing, Vol. 1, No. 5-21, 1984
  43. P. Hudak, ``Conception, Evolution, and Application of Functional Programming Languages,'' ACM Computing Surveys, Vol. 21, No. 3, September 1989.
  44. L. C. Paulson, ML for the Working Programmer, Cambridge University Press, 1991. (Reprinted in 1993.)
  45. J. D. Ullman, Elements of ML Programming, Prentice-Hall, 1994.

    Hybrid Systems

  46. R. Alur, C. Courcoubetis, T. A. Henzinger, P.-H. Ho, ``Hybrid Automata: An Algorithmic Approach to the Speicification and Verification of Hybrid Systems,'' LNCS 736, Springer-Verlag, Berlin, 1993.
  47. Z. Manna and A. Pnueli, ``Verifying Hybrid Systems,'' LNCS 736, R. L. Grossman, A. Nerode, A. P. Ravn, H. Rischel (Eds.), Springer-Verlag, Berlin, 1993.

    Lambda Calculus and Turing Machines

  48. A. Church, The Calculi of Lambda-Conversion, Princeton University Press, Princeton, NJ, 1941.
  49. A. M. Turing, ``Computability and Lambda-Definability,'' J. Symbolic Logic, Vol. 2, pp. 153-163, 1937.

    Mathematics

  50. V. Bryant, Metric Spaces - Iteration and Application, Cambridge University Press, 1985.
  51. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990.
  52. M. C. Gemignani, Elementary Topology, Second Edition, Dover Publications Inc., New York, 1972.
  53. M. C. Golumbic, ``Algorithmic Graph Theory and Perfect Graphs,'' Academic Press, New York, 1980.
  54. S. G. Matthews, "Partial Metric Topology," in General Topology & its Applications, eds. S. Andima et al, Proc. of the 8th Summer Conf., Queen's College (1992), Annals of the New York Academy of Science, Vol. 728 (New York Academy of Sci., 1994), pp. 183-197.
  55. B. C. Pierce, Basic Category Theory for Computer Scientists, The MIT Press, Cambridge, MA, 1991.
  56. F. Robert, Discrete Iterations: A Metric Study, volume 6 of Springer Series in Computational Mathematics, Springer-Verlag, 1986.
  57. A. Tarski, "A Lattice-Theoretic Fixpoint Theorem and its Applications," Pacific Journal of Mathematics, Vol. 5, pp. 285-309, 1955.
  58. W. T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins University Press, Baltimore, Maryland, 1992.
  59. R. F. C. Walters, Categories and Computer Science, Cambridge University Press, 1991.

    Nondeterminism

  60. K. R. Apt and G. D. Plotkin, ``Countable Nondeterminism and Random Assignment,'' J. of the ACM, Vol. 33, No. 4, pp. 724-767, 1986.
  61. J. D. Brock and W. B. Ackerman, ``Scenarios, a Model of Non-Determinate Computation,'', Proc. Conf. on Formal Definition of Programming Concepts, LNCS 107, pp. 252-259, Springer-Verlag, Berlin, 1981.
  62. M. Broy, ``Nondeterministic Dataflow Program: How to avoid the merge anomaly,'' Science of Computer Programming, vol. 10, no. 1, pp. 65-85, Feb. 1988.
  63. R. M. Keller, ``Denotational Models for Parallel Programs with Indeterminate Operators,'' Formal Description of Programming Concepts, Ed. E. J. Neuhold, North-Holland, Amsterdam, 1978, pp. 337-366.
  64. P. R. Kosinski, ``A Straightforward Denotational Semantics for Non-Determinate Data Flow Programs,'' Proc. of the 5th Annual ACM Symp. Principles of Programming Languages, pp. 214-221, Tuscon, AZ, Jan., 1978.
  65. P. Panangaden and V. Shanbhogue, ``The Expressive Power of Indeterminate Dataflow Primitives,'' Information and Computation, Vol. 98, No. 1, May 1992.

    Parallel Computing

  66. S. Y. Kung, VLSI Array Processors, Prentice-Hall, Englewood Cliffs, New Jersey, 1988.
  67. V. Sunderam, ``PVM: A Framework for Parallel Distributed Computing,'' Concurrency: Practice and Experience, Vol. 2, No. 4, Dec. 1990, pp. 315-339.

    Scheduling

  68. E. G. Coffman, Jr., Computer and Job Scheduling Theory, Wiley, New York, 1976.
  69. C. E. Leiserson and J. B. Saxe, "Retiming synchronous circuitry," Algorithmica, 1991, vol.6, (no.1):5-35.
  70. V. Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989.

    Semantics

  71. N. Francez, Fairness, Springer-Verlag, 1986.
  72. C. A. Gunter, Semantics of Programming Languages: Structures and Techniques, The MIT Press, Cambridge MA, 1992.
  73. Z. Manna, Mathematical Theory of Computation, McGraw-Hill, New York, 1974.
  74. D. Scott and C. Stachey, ``Towards a mathematical semantics for computer languages'', Proc. Symp. on Computers and Automata, Polytechnic Inst. of Brooklyn, 1971.
  75. M. B. Smyth, "Quasi-Uniformities: Reconciling Domains with Metric Spaces," Mathematical Foundations of Programming Language Semantics, 3rd Workshop, Tulane, in Lecture Notes in Computer Science 298, M. Main et al. eds., Springer-Verlag, New York, 1987.
  76. G. Winskel, The Formal Semantics of Programming Languages, the MIT Press, Cambridge, MA, USA, 1993.

    Software

  77. S. Ahuja, N. Carreiro, and D. Gelernter, ``Linda and Friends,'' Computer, Vol. 19, No. 8, Aug. 1986, pp. 26-34.
  78. J. T. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt, ``Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems,'' Int. Journal of Computer Simulation, special issue on ``Simulation Software Development,'' vol. 4, pp. 155-182, April, 1994. .
  79. J. Rasure and C. S. Williams, ``An Integrated Visual Language and Software Development Environment'', Journal of Visual Languages and Computing, Vol 2, pp 217-246, 1991.
  80. D. Verkest, K. Van Rompaey, I. Bolsens, H. De Man, ``POPE -- A Design Environment for Heterogeneous Hardware/Software Systems,'' to appear, Design Automation for Embedded Systems, 1996.

    Synchronous-Reactive Systems

  81. A. Benveniste, P. Caspi, P. Le Guernic, N. Halbwachs, ``Data-flow Synchronous Languages,'' in J. W. de Bakker W.-P. de Roever, and G. Rozenberg, eds., A Decade of Concurrency -- Reflections and Perspectives, Lecture Notes in Computer Science no. 803, Springer-Verlag, Berlin, 1994.
  82. A. Benveniste and P. Le Guernic, ``Hybrid Dynamical Systems Theory and the SIGNAL Language,'' IEEE Tr. on Automatic Control, Vol. 35, No. 5, pp. 525-546, May 1990.
  83. A. Benveniste, P. Le Guernic, Y. Sorel, and M. Sorine, ``A Denotational Theory of Synchronous Reactive Systems'', Information and Computing, Vol. 99, No. 2, pp. 192-230, 1992.
  84. A. Benveniste and G. Berry, ``The Synchronous Approach to Reactive and Real-Time Systems,'' Proceedings of the IEEE, Vol. 79, No. 9, 1991, pp. 1270-1282.
  85. G. Berry and G. Gonthier, ``The Esterel synchronous programming language: Design, semantics, implementation,'' Science of Computer Programming, 19(2):87-152, 1992.
  86. F. Boussinot, R. De Simone, ``The ESTEREL Language,'' Proceedings of the IEEE, Vol. 79, No. 9, September 1991.
  87. P. Caspi, D. Pilaud, N. Halbwachs, and J. A. Plaice, ``LUSTRE: A Declarative Language for Programming Synchronous Systems,'' Conference Record of the 14th Annual ACM Symp. on Principles of Programming Languages, Munich, Germany, January, 1987.
  88. P. Caspi, ``Clocks in Dataflow Languages,'' Theoretical Computer Science, Vol. 94, No. 1, March 1992.
  89. N. Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Dordrecht, 1993.
  90. P. Le Guernic, T. Gauthier, M. Le Borgne, C. Le Maire, ``Programming Real-Time Applications with SIGNAL,'' Proceedings of the IEEE, Vol. 79, No. 9, September 1991.
  91. S. Malik, ``Analysis of cyclic combinational circuits'', Proceedings of the ICCAD 93 Conference, IEEE Computer Society Press, Santa Clara, November 1993.
  92. F. Maraninchi, ``The Argos Language: Graphical Representation of Automata and Description of Reactive Systems,'' in Proc. of the IEEE Workshop on Visual Languages, Kobe, Japan, Oct. 1991.
  93. S. Narayan, F. Vahid, D. D. Gajski, ``SpecCharts: A Language for System Level Specification and Synthesis'', Proc. of Int. Symp. on Computer Hardware Description Languages, Marseille, April 1991.
  94. M. von der Beeck, ``A Comparison of Statecharts Variants,'' in Proc. of Formal Techniques in Real Time and Fault Tolerant Systems, LNCS 863, pp. 128-148, Springer-Verlag, Berlin, 1994.
  95. D. Harel, ``Statecharts: A Visual Formalism for Complex Systems,'' Sci. Comput. Program., vol 8, pp. 231-274, 1987.
Home page