
I submitted the final grades to Feinberg. Expect a few days delay until
you can see them in the "internal services".
You can pick up your marked exams from Gizel in room 211.
Nir (28/10/03)

Those of you who have mailboxes in the faculty can find their graded
exercises in their (respective) mailboxes.
Those of you who do not have mailboxes may contact Dan Barak (2651) in
order to get them back.
Nir (31/7/03)

The exam deadline is postponed in one week to 8/8/2003.
Nir (29/7/03)

I am sorry to say that there is an error in question 2 in the exam.
Question 2 was taken from an unpublished manuscript. Unfortunately, there
was an error in the manuscript which I was not aware of (and obviously
did not find).
Gavriel Nivasch showed me that the directions that I gave lead to an
automaton that is not backward deterministic. The requirements in the
question were laxed and now you have to prove that the resulting automaton
is `full'.
I contacted the author of the manuscript and he told me that the error was
already pointed out to him by someone else.
A corrected version of the exam with the exact definition of full
automaton is posted on the course's homepage.
My apologies,
Nir (22/7/03)
 Final exam posted.
Please submit the exam by email to Nir
(nir.piterman_at_weizmann.ac.il).
I will be abroad during 26/6/0315/7/03. During this period I
will try to read mail regularly and respond to questions that you
may have.
Good Luck,
Nir (25/6/03)
 Exercise 9 posted (18/6/03).
 The Dyck set theorem (taught in the last lecture) is often called
the Chomsky/Schutzenberger Theorem:
N. Chomsky & M.P. Schutzenberger,
The algebraic theory of contextfree languages.
In P. Braffort & D. Hirschberg, eds. Computer Programming
and Formal Systems,
NorthHolland, Amsterdam (1963) 118161.
Relayed from David.
 Exercise 8 posted (12/6/03).
 Exercise 7 posted (8/6/03)
 We request that for the last two talks (10,17/6) you recall the
basics of context free languages and pushdown automata (over finite
words).
You can use the following books:
M. Sipser
Introduction to the Theory of Computation
D. Kozen
Automata and Computability
J.E. Hopcroft and J.D. Ullman
Introduction to Automata Theory, Languages, and Computation
J.E. Hopcroft, R. Motwani, and J.D. Ullman
Introduction to Automata Theory, Languages, and Computation
(2nd edition of the above)
 A link to an automatic LTL to automata converter:
Dennis
Oddoux
The conversion this program is based on follows the way we took in
class. The LTL formula is converted to an ABW and then the ABW is
converted to NBW. There are also other optimisations. (26/5/03)
 Exercise 6 posted. (20/5/03)
 Error in Exercise 5. Correct version posted.
Deadline extended in one week to 20/5/03. (5/5/03)
 Exercise 5 posted. (30/4/03)
 Error in exercise 4.
The definition of delta' in question 3 was incorrect.
(20/4/03)
 Exercise 4 posted. (15/4/03)
 Safra's determinization construction is available
in:
 Safra's original paper:
Shmuel Safra, On the Complexity of OmegaAutomata,
In Proceedings of 29^{th} Symp. on Foundations of Computer
Science, pages 319327, 1988.

Safra's Ph.D
thesis: (pages 67 definitions, pages 917 determinization)
S. Safra, Complexity of Automata on Infinite Objects,
Ph.D. Thesis The Weizmann Institute of Science, pages 917,
1989.

Christof Loeding's M.Sc. thesis: (page 13 definitions, pages
2530 determinization)
C. Loeding, Methods for the Transformation of OmegaAutomata:
Complexity and Connection to Second Order Logic, M.Sc. Theis,
ChristianAlbrechtsUniversity of Kiel, pages 2530, 1998.
I recommend using Loeding's thesis.
(8/4/03)

No exercise this week. Please make sure that you are familiar with
Tiling decision problems for next class.(9/4/03)
 The following resources are available:
Lecture notes in the class Automata Theoretic Approach to
Verification.
The paper An
automatatheoretic approach to linear temporal
logic by Moshe
Vardi (bottom, Banff 1994).
(2/4/03)
 Exercise 3 posted. (2/4/03)
 For next class be sure that you are familiar with the constructions
for intersection, union, and complementation for both DFW and NFW.
(27/3/03)
 The paper describing E,A,C machines and the different succinctness results
is:
D. Drusinsky and D. Harel,
On the Power of Bounded Concurrency I: Finite Automata,
J. Assoc. Comput. Mach. 41 (1994), pages 517539.
It can be downloaded from David's
publication page.
(27/3/03)
 Exercises are to be typed. Figures can be hand drawn and added. (25/3/03)