The University of Western Ontario
Department of Computer Science

CS 883b: New Directions in Automata and Formal Language Theory

Course Information -- Winter 2008

Description

This course is designed to expose the students to the new developments in automata and formal language theory. The course will cover the recent results that are motivated by applications such as image processing and compression, parallel processing and web applications. The major part of the course will cover two-dimensional words and languages, and devices that recognize or generate them, which include deterministic and nondeterministic four-way finite automata, grammars and expressions for 2-D languages, and titling sets that recognize 2-D languages.

Prerequisites

CS331 Foundations of Computer Science I or equivalent
Mathematical maturity.

Topics

  • Two-dimensional (2-D) words and languages
  • Regular expressions for 2-D languages
  • Deterministic and nondeterministic four-way automata
  • Grammars for 2-D languages
  • Titling systems for 2-D languages
  • Other related systems
  • Relations between different systems

Instructor

Professor Sheng Yu, MC374, syu@csd.uwo.ca, Ext. 83715

Office hours

Tuesday 3:30-4:30

Class meeting time and place

2:30-5:30 Thursday, MC 316

Textbook

No textbook is specified for the course.
References will be specified in class.

Assignments/exams/seminars

  • Each student is required to give a seminar in class. The duration of the seminar depends on the number of students registered for the course.
  • There are several assignments given by the instructors during the term.
  • No tests or exams.

Evaluation

The final mark is given according to the following factors:

  • Seminar 40%
  • Assignments 40%
  • Participation 20%