
A two-dimensional (2D) automaton is a natural extension of the finite automaton model that operates on two-dimensional words; that is, on arrays or matrices of symbols. The 2D automaton model has a long history dating back to the 1960s and many of the major results were established in the 1970s and 1980s, but there has been a resurgence of interest in variants of the model in the past decade or so. Since the standard 2D automaton model is Turing-equivalent and thus more difficult to reason about, recent work has focused on the properties of restricted variants of 2D automata: namely, variants where the input head can move in only three (or even two) directions through the input word. In this talk, I will discuss some of the major results in the area of two-dimensional automata theory and draw connections between 2D automata and formal language theory, with a focus on the closure, decidability, and complexity properties of restricted variants of 2D automata. I will also present recent algorithmic work on computing efficient randomized approximate solutions to 2D decision problems that are computationally hard to solve. Throughout, I will share a number of open problems that will guide the future study of 2D automaton models.