Category Archives: Jeffrey Shallit

shallit-talk

Separating words with automata

Imagine a stupid computing device with very limited powers…
What is the simplest computational problem you could ask it to
solve?

- not the addition of two numbers
- not sorting
- it’s telling two inputs apart – distinguishing them

This problem will be featured in Jeffrey Shallit’s invited talk entitled Separating Words With Automata.