Specification and Modeling of Reactive Real-Time Systems

Edward A. Lee

Tentative Outline

This outline is highly subject to change, and will evolve as the class evolves. Right now, it is just a tentative list of topics in a tentative order in which they will be presented.

1. Organizational
2. The tagged signal.
   • tags, signals, processes, inputs, and outputs.
   • determinacy.
   • timed and untimed systems, metric time
3. Discrete-event systems.
   • metric space.
   • causality
   • determinacy
4. Implementations.
   • discrete-event simulation.
   • VHDL
5. Kahn process networks
   • semantics.
   • implementation (bounded scheduling).
6. Partial orders
   • set inclusion
   • prefix orders
   • cpo's
7. Classes of relations over cpo's
   • relations
   • functions
   • monotonic (order-preserving) functions.
   • continuous functions.
   • stable functions.
   • linear functions.
   • sequential functions.
8. Fixed-point theorems.
   • continuous functions over cpo's.
   • monotonic functions over cpo's.
   • least fixed-point semantics.
   • determinacy of Kahn process networks.
9. Dataflow
   • semantics.
   • fairness.
   • data-driven scheduling.
   • demand-driven scheduling.
   • bounded scheduling.
10. Synchronous dataflow
    • balance equations.
    • loop scheduling.
    • parallel scheduling.
11. Turing completeness
    • Turing machines.
    • undecidability.
12. Boolean dataflow
    • consistency.
    • scheduling.
13. The lambda calculus
    • the notion of syntax.
    • reduction and canonical forms.
    • recursion.
14. Synchronous-reactive systems
    • Scott orders, flat orders.
    • fixed-point semantics.
    • constructive semantics.
    • Esterel.
    • Lustre.
    • Signal.