# Automaton

There have been 1 completed talk and 2 topic suggestions tagged with automaton.

## Completed Talks

### Automatic sequences

Delivered by Laindon Burnett on Wednesday October 25, 2017

This talk will begin with a brief overview behind the theory of words in mathematics as well as the theory of finite automata in theoretical computer science. After this, we will define what an automatic sequence is, prove some fundamental theorems about them, and investigate some of their more intriguing properties. The majority of information presented comes from the text “Automatic Sequences: Theory, Applications, Generalisations” by Jean-Paul Allouche and the University of Waterloo's own Jeffrey Shallit, from the department of Computer Science.

The speaker has provided a PDF document covering the same content as this talk.

## Talk Suggestions

### Conway’s Game of Life

Possible reference materials for this topic include

Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.