Course Number and Title: CS 5653, Automata and Finite State Machines
Time: 2:00-4:30 Tuesdays Place: MSCS 237

Instructor: M. Samadzadeh Office: MSCS 215 Phone: 744-5674
Office Hours: 11:30-12:15 Monday, Tuesday, Wednesday, Thursday, Friday, or by appointment if necessary

Prerequisite: CS 5313 (Formal Language Theory)

Optional/Recommended Texts, etc.:

· Andras Adam, Behavior and Simplicity of Finite Moore Automata, Akademiai Kiado, Budapest, 1996.

· Taylor L. Booth, Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York, NY, 1967.

· J. Glenn Brookshear, Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc., Redwood City, CA, 1989.

· Parimal Pal Chaudhuri, et al., Additive Cellular Automata: Theory and Applications, IEEE Computer Society Press, Los Alamitos, CA, 1997.

· Peter J. Denning, Jack B. Dennis, and Joseph E. Qualitz, Machines, Languages, and Computation, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1978.

· Vladimir Drobot, Formal Languages and Automata Theory, Computer Science Press, Inc., Rockville, MD, 1989.

· Ding-Zhu Du and Ker-I. Ko, Problem Solving in Automata, Languages, and Complexity, A Wiley-Interscience Publication, New York, NY, 2001.

· Hartmut Ehrig, et al., Universal Theory of Automata: A Categorical Approach, Teubner Press, Stuttgart, Germany, 1974.

· Abraham Ginzburg, Algebraic Theory of Automata, Academic Press, New York, NY, 1968.

· W. M. L. Holcombe, Algebraic Automata Theory, Cambridge University Press, New York, NY, 1982.

· John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edition, Pearson Addison-Wesley Publishing Company, Inc., Reading, MA, 2006.

· Richard Y. Kain, Automata Theory: Machines and Languages, McGraw-Hill Book Company, New York, NY, 1972.

· Bakhadyr Khoussainov and Anil Nerode, Automata Theory and Its Applications, Birkhauser, Boston, MA, 2001.

· Zvi Kohavi, Switching and Finite Automata, McGraw-Hill, New York, NY, 1978.

· Dexter C. Kozen, Automata and Computability, Springer-Verlag, Inc., New York, NY, 1997.

· Mark V. Lawson, Finite Automata, Chapman & Hall/CRC, Washington, DC, 2004.

· Peter Linz, An Introduction to Formal Languages and Automata, 4th edition, Jones and Bartlett, Boston, MA, 2006.

· R. McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice-Hall Inc., 1982.

· Alexander Meduna, Automata and Languages: Theory and Applications, Springer Verlag, London, UK, 2000.

· M. L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall Inc., 1967.

· John N. Mordeson and Davender S. Malik, Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002.

· John E. Savage, Models of Computation: Exploring the Power of Computing, Addison Wesley Longman, Inc., Reading, MA, 1998.

· Matthew Simon, Automata Theory, World Scientific Press, Singapore, 1999.

· Rudolph Sommerhalder and S. C. van Westrhenen, The Theory of Computability: Programs, Machines, Effectiveness and Feasibility, Addison-Wesley Publishing Company, Inc., Workingham, England, 1988.

· Peter H. Starke, Abstract Automata, North-Holland Publishing Company, Amsterdam and American Elsevier Publishing Company, Inc., New York, NY, 1972.

· Thomas A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science, 3rd Edition, Pearson - Addison-Wesley Longman, Inc., Reading, MA, 2005.

Journals and Conferences/Symposia/Workshops:

· International Workshop on Probabilistic Automata and Logics (PAuL).

· International Conference on Language and Automata Theory and Application (LATA).

· Journal of Theoretical Computer Science.

· International Conference on Implementation and Application of Automata (CIAA).

· International Colloquium on Automata, Languages, and Programming (ICALP).

· Games and Automata for Synthesis and Validation (GAMES).

· Journal of Logic and Algebraic Programming.

· International Workshop on Implementation of Automata (WIA).

· SIGACT News, ACM Special Interest Group on Algorithms and Computation Theory.

· International Symposium on Theoretical Aspects of Computer Science (STACS).

· International Symposium on Mathematical Foundations of Computer Science (MFCS).

· Journal of Symbolic Computation.

· ACM Symposium on Theory of Computing (STOC).

· Conference on Algebra and Coalgebra in Computer Science (CALCO).

· International Conference on Cellular Automata for Research and Industry.

· SIAM Journal on Computing (SICOMP).

· Symposium on Foundations of Computer Science (FOCS).

· The European Joint Conferences on Theory and Practice of Software (ETAPS).

· International Conference on Compiler Construction (CC).

· International Workshop on Termination (WST).

· International Conference on Graph Transformation.

· Fundamental Approaches to Software Engineering (FASE).

· Foundations of Software Science and Computation Structures (FOSSACS).

· Tools and Algorithms for the Construction and Analysis of Systems (TACAS).

· Automated Verification of Infinite-State Systems (AVIS).

· International Workshop on Coalgebraic Methods in Computer Science (CMCS)

· International Colloquium on Theoretical Aspects of Computing (ICTAC)

· IFIP International Conference on Theoretical Computer Science (TCS)

· International Workshop on Combinatorial Image Analysis (IWCIA)

· \fTheoretical and Mathematical Foundations of Computer Science (TMFCS)

Course Description: Sequential machines and automata. Hierarchy of recognizers. Decision problems and closure properties. Finite and infinite state machines. Cellular and stochastic automata. Coverings of Automata.

Grading: Homeworks and Programs 30%
Tests (2) 20% each
Final Examination 30%

Letter Grades: [90-100] A, [80-90) B, [70-80) C, [60-70) D, [0-60) F

Notes:

(1) Assignments are due at the beginning of class on the date they are due (unless announced in class otherwise). Homework assignments are to be submitted in hard copies, i.e., on paper. Assignment legibility is a requirement. The "word processing and formatting" of the assignments is a recommended option but not a requirement. Late assignments will not be accepted. Only when verifiable extenuating circumstances can be demonstrated will make-up exams or extended assignment due dates be considered. Verifiable extenuating circumstances must be reasons beyond control of the students, such as illness or accidental injury. Poor performance in class is not an extenuating circumstance. Advise your instructor of the verifiable extenuating circumstances in advance or as soon as possible. In such situations, the date and nature of the make-up exams and the extended due dates for the assignments will be decided by the instructor.

(2) A general point about assignments and tests: It is understood and it is always the case that you must justify your answers, show all your work, and state your assumptions on all problems and exercises in the assignments and examinations. A correct answer with no justification and no work shown may be worth less than a wrong answer with full justification and having shown all the work.

(3) Cell phones should be turned off during class and in examination sessions. Computer use (i.e., the use of a laptop, etc.) is not allowed in class unless a clear and convincing case is made for the use of one.

Attendance Policy:

(1) Attendance is strongly encouraged, but not required or monitored. Students are responsible for all material covered in class. Some of the material covered in class will not be in the text book. Announcements about assignments, project due dates, etc. will be made in class and/or by email. Students are to check their CSA email regularly using their class account, i.e., userid@cs.okstate.edu. [Passwords for new accounts on CSA are the PR&SM passwords (PR&SM = Password Reset and System Management) that students can get via their O-Key accounts. If you have a new CSA account, you should use your PR&SM password.] Students are responsible for all announcements made in class and/or by email. Students are to either check their class account email on CSA regularly or to put an appropriate forwarding mechanism in place to make sure to read their class-related email.

(2) Taking a course as a remote student is not the same as taking a correspondence course or taking an on-line course. Although the lectures are generally made available after the fact and may be viewed at the students' leisure, that does not free the students from keeping up with the class. This course has a pace and progress rate that must be followed by all students. The deadlines and due dates apply to all students.

(3) Attending this class requires registration or formal audit, no informal "sitting in" is allowed.

Collaboration Policy for CS 5653

Homework: Discussion of any kind is allowed. After discussion, each student must write up his/her own solution. Copying another student's work is not allowed. Giving another student your work is considered cheating as well.

Programs: Discussion of techniques in a natural language (such as English) is allowed, but a discussion in a computer or algorithmic language is not allowed. Computer language discussions and questions are to be limited to the language and should not concern the assignment. Stealing, giving or receiving any code, drawings, diagrams, texts or designs is not allowed. Every line of work that you turn in must be your own.

Examinations: No discussion of any kind (except with the instructor) is allowed. No access to any type of written material is allowed.

Students who do not comply with the described collaboration policy will receive a grade of F in the course. Furthermore, the case will be reported to the University Officials.

Attachments:

· Computer Science Department General Computer Use and Misuse Policy

· Disabilities Act

· Academic Integrity Policy

· Fall Semester 2008 Calendar

· Fall 2008 Final Examination Schedule

· OSU-Stillwater Syllabus Attachment, Fall 2008

· OSU-Tulsa Syllabus Attachment, Fall 2008