Alex Simpson: Math. Struct. for Semantics

Mathematical Structures for Semantics (2001-2002)

This is the home page for the LFCS TPG course: Mathematical Structures for Semantics.

This half course covers a variety of mathematical structures used in semantics. The course is structured around a single weekly lecture in which a selected topic is reviewed. Reading lists are issued a week in advance of lectures, and lectures assume some acquaintance with this material. Each lecture covers a different topic, and aims to reach the frontier of research in that area.

Arrangements

Lectures: Thursdays 11-12, Room 4310

Course starts: Thursday 7th February

Course ends: Thursday 14th March

There will also be student-given lectures on miscellaneous topics in term 3.

Course outline

The reading lists will often contain a substantial amount of material for one week's reading. You should approach this by trying to obtain as good an overview as possible from the reading material, without necessarily following all technical details. The lectures should then help to consolidate your picture of the subject. After the lectures you should be well set up to read through the technical details of any topics that you find sufficiently interesting or useful.

  1. Thursday 7th February: Algebraic and continuous domains. (Handwritten lecture note. Contact me for a copy.)

    Other reading: [Sco72], [Plo83, Ch.6], [Smy83], [Jun89], [Jun90], [AR94].

  2. Thursday 21st February (note the postponement!): Recursive domain equations. Lecture note 2

    Other reading: [SP82], [Fre91], [Fre92], [Fio94], [Sim02], [Pit96].

  3. Thursday 28th February: Topological spaces from a computational perspective. Lecture note 3

    Other reading: [Vic89], [Joh86], [Abr91].

  4. Thursday 7th March: Equilogical spaces. Lecture note 4

    Other reading: [Sco72], [GHK80], [MS02], [Bau00].

  5. Thursday 14th March: Higher type exact real-number computation

  6. Friday 17th May, 2-5pm, room 2509, student presentations:

Exam

The course is assessed by a question on the LFCS TPG exam.

References

[Abr91] Samson Abramsky. Domain theory in logical form, Annals of Pure and Applied Logic, 51:1-77, 1991.

[AJ94] Samson Abramsky and Achim Jung, Domain theory, Handbook of Logic in Computer Science Vol. III, 1994.

[AR94] Jiri Adamek and Jiri Rosicky, Locally Presentable and Accessible Categories, London Mathematical Society Lecture Note Series, 189, CUP, 1994.

[Bau00] Andrej Bauer, The Realizability Approach to Computable Analysis and Topology, PhD Thesis, CMU, 2000.

[BBS02] Andrej Bauer, Lars Birkedal and Dana Scott, Equilogical spaces, to appear in Theoretical Computer Science, 2002.

[BES02] Andrej Bauer, Martín Escardó and Alex Simpson, Comparing Functional Paradigms for Exact Real-number Computation, draft paper, 2002.

[Fio94] Marcelo Fiore, Axiomatic Domain Theory in Categories of Partial Maps, PhD Thesis, University of Edinburgh, ECS-LFCS-94-307, 1994. (Published in Distinguished Dissertation Series, CUP, 1996.)

[Fre91] Peter Freyd, Algebraically complete categories, in Category Theory, Proceedings Como 1990, Springer LNM 1488, 1991.

[Fre92] Peter Freyd, Remarks on algebraically compact categories, in Applications of Categories in Computer Science, pages 95-106, LMS Lencture Notes 177, CUP, 1992.

[GHK80] Gerhard Gierz, Karl Heinrich Hofmann, Klaus Keimel, Jimmie D. Lawson, Michael W. Mislove, and Dana S. Scott, A Compendium of Continuous Lattices, Springer-Verlag, 1980

[Joh86] Peter Johnstone, Stone Spaces, CUP, 1986.

[Jun89] Achim Jung, Cartesian Closed Categories of Domains, PhD dissertation, Vol. 66 of CWI Tracts, 1989.

[Jun90] Achim Jung, The classification of continuous domains , Proc. 5th IEEE Symposium on Logic in Computer Science, 1990.

[MS02] Matías Menni and Alex Simpson, Topological and Limit-space Subcategories of Countably-based Equilogical Spaces, To appear in Math. Struct. in Comp. Sci.
2002.

[Pit96] Andrew Pitts, Relational properties of domains, Information and Computation, 127:66-90, 1996.

[Plo83] Gordon Plotkin, Domains, the "Pisa notes", 1983.

[Sco72] Dana Scott, Continuous lattices, in Toposes, algebraic geometry and logic, pp. 97-136, Springer LNM 274, 1972.

[Sim02] Alex Simpson, Computational Adequacy for Recursive Types in Models of Intuitionistic Set Theory, draft paper, 2002.

[Smy83] Michael Smyth, The largest cartesian closed category of domains, Theoretical Computer Science, 27:109-119, 1983

[Smy92] Michael Smyth, Topology, Handbook of Logic in Computer Science Vol. I, 1992.

[SP82] Michael Smyth and Gordon Plotkin, The category-theoretic solution of recursive domain equations, SIAM Journal of Computing, 11:761-783, 1982.

[Vic89] Steve Vickers, Topology in Logical Form, CUP, 1989.