CS786 Spring 04
Introduction to Kleene Algebra
Course Information



Dexter Kozen
Upson 5143
255-9209 office
257-4579 home
592-2437 cell

Teaching Assistant

In my dreams


Kelly Patwell
Upson 5147
255-7790 office

Time and Place

Mondays 5:15-7pm, Upson 5126.

Office Hours

By appointment.  For an appointment with Dexter, please contact Kelly.



The following text will be used.

This book is out of print and unavailable from the publisher.  Photocopies are available from Kelly for a nominal charge.

Other useful sources:

These titles are on reserve in the Engineering Library, Carpenter Hall.


All handouts, articles, homework sets, etc. will be available on the web in pdf or html format.  It is your responsibility to check often for new postings.  For viewing pdf files, we recommend Adobe Reader, available free of charge.

Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems, due in class on the due date.  You may collaborate on homework.  If you collaborate, pass in one copy of your solutions with the names of all collaborators.  Acknowledge all sources, including others in the class from whom you obtained ideas.  Late homework will not be accepted without a good excuse.  Assignments and solutions will be posted on the web.

There will be two 72-hour takehome exams, open book and notes.  No collaboration is allowed on the exams.

Approximate weights: Homework 50%, exams 25% each.


Familiarity with the content of CS481 is essential.  In addition, familiarity with the content of CS682 and (CS482 or CS681), as well as elementary logic and algebra (Math 432, Math 481, Math 681) will be helpful.  In particular, we will assume knowledge of:

Approximate Syllabus

Entries in italics will be covered as time permits.