Automaton
There have been 1 completed talk and 2 topic suggestions tagged with automaton.
Related Tags
- cellular automaton
- theoretical computer science
- recreational mathematics
- open problem
- computer science
- number theory
- first year friendly
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
Quick links: Google search, arXiv.org search, propose to present a talk
automaton cellular automaton computer science first year friendly recreational mathematics theoretical computer science
Separating Words Problem
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.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
automaton computer science open problem theoretical computer science