Specification and Modeling of Reactive and Real-Time Systems

Edward A. Lee

2 Units - Fall, 1996 - Tu, Th: 11-12:30 - 299 Cory

Assignments

Project

• October 3: One page project proposal due.
• October 31: Short presentations in class.
• December 5: Final presentations, Wang Room, 9:30-11:30am.
• December 11: Final presentations, Wang Room, 1-6pm.
• December 13: Project reports due

Problems

Due September 10:

Let (X,d) be a metric space. Prove:

1. Both X and the empty set are closed.
2. The intersection of any number of closed sets is closed.
3. The union of any two closed sets is closed.

Due September 19:

See postscript file. Solution postscript file.

Optional

Let (Y,d) be a metric space where d:YxY->R is an ultrametric. Consider the product space Y^N consisting of N-tuples of members of Y. Define an ultrametric for this space in terms of the ultrametric d, and show that it is an ultrametric.

Due October 8:

Let S be the set of one-sided ordered signals. Show that for any subset Q of S the following are equivalent:

• Q is a non-empty chain.
• Q is a directed set.
• Q is joinable.
• Q is has an upper bound.

In addition, prove that S is not a lattice. Solution postscript file.

Reading

• 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.
• By B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990, chapters 1-4. <
• 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. <
• G. Kahn and D. B. MacQueen, ``Coroutines and Networks of Parallel Processes,'' Information Processing 77, B. Gilchrist, editor, North-Holland Publishing Co., 1977.