Grant: Discovery Launch Supplement

Introduction. Finite automata are an abstract model of computation that form the basis of study in formal language and automata theory. Finite automata appear in a number of computer science applications, including compiler technology, pattern matching, image analysis, and natural language processing. Descriptional complexity is a subfield of automata theory that seeks to establish lower bounds on the size of finite automata completing certain tasks; that is, to establish that no finite automaton with fewer states can accomplish the same task. Descriptional complexity is a well--studied topic for both standard finite automata as well as extensions to the model, such as visibly pushdown automata, and several conferences exist that are devoted to this topic. Motivation. Two--dimensional (2D) automata are a generalization of the standard finite automaton model that operate over nonlinear input words. While a finite automaton processes strings, a 2D automaton processes two--dimensional arrays of data in a sequential manner (i.e., one symbol at a time). While a 2D automaton is typically able to move its input head in four directions, we may also study variants of the model where the input head can move in only three or two directions. Although all 2D automaton models are conceptually simple, the four--way model is Turing-complete, making the model suitable for complex tasks. However, little work has been done to investigate the descriptional complexity properties and practical applicability of this model, despite similar work illustrating the benefits of introducing multiple dimensions to other classical models. The primary barrier to obtaining complexity results for 2D automata is the lack of a general method, akin to the fooling set method for finite automata. Goals. The long--term goal of my research is to develop a general method for establishing concrete descriptional complexity bounds in order to evaluate the feasibility of using 2D automaton models as an alternative approach for performing advanced computational tasks. To this end, I have identified four short-term goals: (O1) establish remaining unknown decidability/closure results for 2D automata; (O2) develop incremental results for establishing bounds on complexity measures for 2D automata; (O3) extend new and existing results to variants of the 2D automaton model and other unconventional models of computation; and (O4) augment software tools to simulate 2D automata and use these tools to computationally verify conjectures and results. Outcome. Determining descriptional complexity bounds for operations on 2D automata will allow researchers and practitioners to evaluate the suitability of this unconventional computational model for implementing tasks that are reliant on multidimensional nonlinear data. With my research establishing a baseline, the 2D automaton model can be adapted to work with a number of more advanced applications, including computer vision and medical image processing.