Event Details

Formal Languages and Number Theory

Presenter: Dr. Jeffrey Shallit - Professor, Computer Science Department, University of Waterloo
Supervisor: Dr. Frank Ruskey, Professor, Department of Computer Science

Date: Thu, May 16, 2002
Time: 14:00:00 - 15:00:00
Place: Engineering Office Wing Building (EOW), Room # 430

ABSTRACT

ABSTRACT:

Number theory is one of the oldest parts of mathematics, and the theory of formal languages is one of the oldest parts of theoretical computer science, so it is not surprising that there are interesting and non-trivial connections between these two areas. In this talk, I will discuss some of these connections, focusing on:

  • Christol's theorem and transcendence in finite characteristic
  • State complexity
  • The primitive words problem