![[Mail]](../../../../Images/umschlag.gif)
| Webmaster | Disclaimer | Last modified: 2005-10-11 07:50 UTC |
![[I2 logo]](../../../../Images/i2.gif)
![[RWTH logo]](../../../../Images/rwth-rot90.gif)
(Informatik 2)
HomeNewsJobsContactStaffTeachingResearchMOVES SeminarDFG-GK AlgoSynCS ChairsLuFG I2
Theory of Control Structures
Graduate Course - Winter Term 2005/06
Schedule
| Type | Time | Place | Start | Lecturer |
|---|---|---|---|---|
| V2 | Wed 11:45-13:15 | AH II | 02.11. | Indermark |
| Ü1 | Fri 09:00-09:45 | AH II | 04.11. | Indermark |
Contents
In this course we analyze the computational power of control constructs of programming languages. Although it is known from computability theory that already WHILE-programs suffice to express all computable functions and as a consequence iteration and recursion seem to be equivalent, there is a different experience in compiler construction where the implementation of recursion requires a stack technique in contrast to iteration. In the theory of control structures, also known as the theory of program schemes, these differences can be expressed by means of formal languages. It is shown that WHILE-programs, iterative programs, and recursive programs form a hierarchy with respect to their computational power.Previous knowledge
The participants should have basic knowledge of automata and formal language theory.Combination with other courses
Diploma students can combine this course with Modelling Concurrent Systems (Th. Noll) or with Automata on Infinite Words (W. Thomas) to a full four-hour course (V4, Ü2).Examination
Solutions to exercises will be given weekly in the tutorial on Friday. To obain a certificate, students have to pass the final exam at the end of this course.Transparencies
All transparencies used during the course will be presented here.Exercises
Exercises will be issued weekly.Literature
- J. Engelfriet: Simple Program Schemes and Formal Languages
LNCS 20, 1974 - S. Greibach: Theory of Program Structures: Schemes, Semantics, Verification
LNCS 36, 1975 - Z. Manna: Mathematical Theory of Computation
McGraw-Hill, 1974 - B. Courcelle: Recursive applicative
program schemes
In J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Vol. B, 1990 -
C. Stirling:
Decidability of
DPDA Equivalence
Theoretical Computer Science 255, 1-31, 2001
(short version: An Introduction to Decidability of DPDA equivalence
FSTTCS'01, LNCS 2245, 42-56, 2001)
