Squaregraphs

On Tuesday, Donald Knuth gave a talk about squaregraphs. I'm summarizing here what I learned, and I'm including the open problems that Knuth mentioned.

Automata on Infinite Alphabets

There are several ways of extending the standard definitions of automata to infinite alphabets. Here I try to explain why the trivial extension (just use the same definitions) is not satisfactory and present a couple of alternatives.

Group Actions

The theory of finite automata works with finite alphabets. The article Automata with Group Actions by Bojanczyk et al. is one recent attempt to extend the theory to infinite alphabets. To do so, the authors use a basic notion from group theory, namely group action. Here I review the facts about group actions that are necessary to understand Bojanczyk's article.