|
T-79.146 Logic in Computer Science: Special Topics I (2 cr)
Spring 2003
[General Information]
[Lectures]
[Tutorials]
[Home assignments]
[Other Interesting Stuff]
[TOPI]
Previous years:
[Spring 2002]
[Spring 2001]
[Spring 2000]
[Spring 1999]
[Spring 1998]
This is an advanced course on logic and its applications in computer
science and engineering. Subjects covered this year are:
modal logics (syntax, semantics, proof theory and computational
properties) and applications of temporal logic in concurrent and
distributed systems.
- NEWS: Additional material illustrating the LTL model checking
exercises of Tutorial 12 is now available online (see
Tutorials).
- Lectures by
Prof. Ilkka Niemelä:
Wednesday 14-16, room TB353
- Tutorials by
M.Sc.(Tech.) Heikki Tauriainen:
Fridays 9-10, room TB353
- The course starts on Wed Jan 15 at 14.15
- Course material:
Lecture notes.
M. Fitting, Basic Modal Logic, Handbook of Logic in
Artificial Intelligence and Logic Programming, Volume 1, Logical
Foundations, 1993.
E. Clarke and O. Grumberg and D. Peled,
Model Checking, The MIT Press, 1999. (Chapters 1-4)
E.A. Emerson,
Automated Temporal Reasoning about Reactive Systems,
Logics for Concurrency, F. Moller and G. Birtwistle (Eds.),
Springer-Verlag, 1996, LNCS 1043, pp. 41-99.
- In order to pass the course one has to
- pass the home assignments
- pass the exam (with a grade greater than 0)
- Newsgroup: opinnot.tik.logiikka
- Brochure in Finnish
- Program of the course
- Exam: 8.5.2003, 9-12, T1;
paper in Finnish [PS]
- Next exams: 29.9.2003, 16-19, T1; 12.1.2004, 16-19, T1
- Instructions for the exam.
Back to menu.
Lecture Notes
(Slides in Finnish; Postscript/PDF form)
-
Refresher [ps] [pdf]
- A refresher on propositional and predicate logic
-
Introduction [ps] [pdf]
- Introduction to the course
-
Modal Logic I [ps] [pdf]
- Introduction to modal logics
-
Modal Logic II [ps] [pdf]
- Modal logics: syntax, semantics
-
Modal Logic III [ps] [pdf]
- Basic properties
-
Modal Logic IV [ps] [pdf]
- Example modal logics
-
Modal Logic V [ps] [pdf]
- Hilbert style proof theory
-
Modal Logic VI [ps] [pdf]
- Tableau Method
-
Modal Logic VII [ps] [pdf]
- Translation to predicate logic, multi-modal logic, decidability and
computational complexity
-
Modal Logic VIII [ps] [pdf]
- Introduction to temporal logic; CTL and LTL
-
Modal Logic IX [ps] [pdf]
- CTL vs. LTL; Expressing properties of systems
-
Modal Logic X [ps] [pdf]
- Model checking CTL and LTL
-
Modal Logic XI [ps] [pdf]
- Tableau method for CTL
Back to menu.
Tutorial exercises and solutions
(in Finnish)
Back to menu.
Home Assignments
There are 3 compulsory home assignments
(see Program).
Each student is given a personal assignment.
-
The first home assignment is distributed starting on Wednesday
29.1.2003 at the lecture 14-16 o'clock.
The deadline for the first assignment is Wednesday 12.2.2003.
- The second home assignment is distributed starting on
Wednesday 5.3.2003 at the lecture 14-16 o'clock.
The deadline for the second assignment is 26.3.2003.
- The third home assignment can be obtained here
([ps] [pdf]) in electronic form
starting on Wednesday
2.4.2003. The deadline is Thursday 24.4.2003.
For more detailed instructions, see
how to get started,
CTL syntax
used by the model checker, and
general
information on PROD.
The software (PROD/probe) that is needed in the third home assignment
has been installed at HUT/Computing Centre
SUN workstations ("Gaulls").
See, PROD
if you wish to install the software on your own PC.
In the third assignment the task is to analyse a mutex algorithm whose
Pr/T-net model can be found here.
The assignments can be returned at the lectures or tutorials or to the
box by the room TB336.
If you cannot come to pick up your assignment at the lectures, please
contact the lecturer directly.
If you have returned your assignment, see the
results.
Back to menu.
Other Interesting Stuff
-
Formal methods
-
Information and links
-
Formal Methods in System Design, 22 (2) March 2003.
-
Special Issue on Industrial Practice of Formal Hardware Verification
-
Interesting books on modal logic, temporal logic and verification of
reactive systems.
-
-
Brian F. Chellas. Modal Logic: An Introduction,
Cambridge University Press, 1980.
- Melvin Fitting. Proof Methods for Modal and Intuitionistic Logic,
Reidel, 1983.
- Robert Goldblatt. Logics of Time and Computation, CSLI Lecture
Notes Number 7, Center for the Study of Language and Information,
Stanford University.
- Hughes, G.E. and Cresswell, M.J.
A Companion to Modal Logic, Methuen and Co.,
1984.
- Hughes, G.E. and Cresswell, M.J. New Introduction to Modal Logic,
Routledge, 1995.
- Patrick Blackburn, Maarten de Rijke, Yde Venema. Modal Logic,
Cambridge University Press, to appear in May 2001.
- Zohar Manna and Amir Pnueli. The Temporal Logic of Reactive and
Concurrent Systems. Springer-Verlag, 1992.
- Zohar Manna and Richard Waldinger. The Deductive Foundations of
Computer Programming. Addison-Wesley, 1993.
- Zohar Manna and Amir Pnueli. Temporal Verification of Reactive Systems: Safety. Springer-Verlag, 1995.
- B. Berard et al., Systems and Software Verification, Model-Checking
Techniques and Tools. Springer, 2001.
- Doron A. Peled: Software Reliability Methods, Springer 2001.
Back to menu.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 30 May 2004.
|