You are here: Home › Teaching › Summer Term 2012 › Real-Time Systems (Lecture)

Real-Time Systems (Lecture)

Real-time systems need to react to certain input stimuli within given time bounds. For example, an airbag in a car has to unfold within 300 milliseconds in a crash. There are many embedded safety-critical applications and each requires real-time specification techniques. We will study and apply some of these techniques, based on logic and automata, most prominently timed automata.
Course type Lecture
Instructors Prof. Dr. Andreas Podelski, Dr. Bernd Westphal
Lecture Tuesday, 10:00–12:00, HS 51-03-026
Thursday, 10:00–12:00, HS 51-03-026
Exercise Tuesday, 10:00–12:00, HS 51-03-026 (two-weekly)
First session Lecture 24.4.12
Language of instruction English
Credits 6
Exams TBA
Course Catalog Real-Time Systems

 

 

Quicklinks: News - Formalia - Plan - Links & Literature

 

News

  • 2012-06-21: the second half of the recordings got lost, sorry
  • 2012-04-18: -

Formalia

Prerequisites for admission to the final exam, form of the final exam, and everything will be announced in the first lecture.

Admission criteria

50% of the total admission (or: good will) points in the exercises are sufficient for exam admission. (For example, perfect solutions to exercise sheets 1, 3, 5, and 7 and no solutions to 2, 4, and 6 would satisfy this requirement; so would 50% of the points in each exercise). 

Exercise Submission Scheme

The exercise sheets are online early in order to allow you to be aware of the tasks while following the lecture. There will be an early/regular submission scheme following a pattern to be announced.

Note: The exercises will be rated on two scales: admission points (given your knowledge before the tutorial, how sensible is your proposal; "good will rating", "upper bound") and exam points (given the additional knowledge from the comments on your proposal and the tutorial, how many points would your proposal at least be worth in a written exam; "evil rating", "lower bound").

Exam

For the students in the master program, there will be a written exam of length 90 min. (unless the number of candidates drops below a certain threshold),

  • date/time: tba, room: tba

For the students in the bachelor program, there will be oral exams of length 30 min.,

  • dates/times: tba

 Note: The module result (grade, "Note") is completely determined by the exam.

Resources

Slides, Exercises, and Recordings

Note: the following plan is tentative in the sense that the assignment of topics to dates is subject to change depending on the flow of the lecture. The assignment of form (lecture or tutorial) to dates is fixed. Slides will be typically only provided after the lecture.

 

Note: the TechSmith Screen Capture Codec seems to be necessary for playback of the recordings provided on the Electure portal.

  • Di, 24.4.: VL 01 "Introduction"
    Motivation, Overview, Formalia.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 26.4.: VL 02 "Timed Behaviour" + exercise sheet 1 online
    A formal representation of timed behaviour.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 1.5.: - (labour day)
  • Do, 3.5.: VL 03 "Duration Calculus I"
    Symbols, state assertions, timing diagrams.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 8.5.: Tutorial 1
  • Do, 10.5.: VL 04 "DC II" + exercise sheet 2 online
    Terms, formulae.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 15.5.: VL 05 "DC III"
    Substitution, valid/satisfiable/realisable, correctness proof.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 17.5.: - (ascension day)
  • Di, 22.11.: Tutorial 2
  • Do, 24.5.: VL 06 "DC Properties I"
    Decidable discrete time.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 29.5.: - (whitsun break)
  • Do, 31.5.: - (whitsun break)
  • Di, 5.6.: VL 07 "DC Properties II" + exercise sheet 3 online
    Undecidable dense time.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 7.6.: - (feast of corpus christi)
  • Di, 12.6.: VL 08 "DC Implementables"
    Implementables.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 14.6.: VL 09 "PLC Automata"
    An abstract view on programmable logic controllers.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 19.6.: Tutorial 3
  • Do, 21.6.: VL 10 "Timed Automata" + exercise sheet 4 online
    Basic Timed Automata.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 26.6.: VL 11 "Networks of Timed Automata"
    Synchronisation, hiding.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 28.6.: VL 12 "Region Abstraction"
    Decidability of the reachability problem for timed automata.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 3.7.: Tutorial 4
  • Do, 5.7.: VL 13 "Zone Abstraction" + exercise sheet 5 online
    An alternative representation of sets of regions.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 10.7.: VL 14 "Extended Timed Automata"
    Variables, and urgent and committed locations.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 12.7.: VL 15 "Automated DC/PLC Verification"
    How to automatically verify whether a PLC automaton satisfies a DC requirement.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 17.7.: Tutorial 5
  • Do, 19.7.: VL 16 "Timed Büchi Automata" + exercise sheet 6 online, example SPI model
    An alternative automaton model with time.  
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Di, 24. 7.: VL 17 "The Universality Problem for TBA"
    Undedicable problems for automata with time.
    (Slides (with annotations), 2-up, 6-up, Recording)
  • Do, 26.7.: Tutorial 6 + "Wrapup + Questions"
    (Slides (with annotations), 2-up, 6-up, Recording)

Links & Literature