A Unifying Approach to Picture Automata
For researchers in picture language recognition, this work provides a unifying framework that extends DAG automata to 2D, with input-driven encodings offering improved expressiveness over existing methods.
The paper proposes using DAG automata to recognize picture languages by encoding 2D inputs into DAGs. Input-agnostic encodings characterize three known automata classes, while input-driven encodings enable recognition of context-sensitive string languages and outperform online tessellation automata in 2D.
A directed acyclic graph (DAG) can represent a two-dimensional string or picture. We propose recognizing picture languages using DAG automata by encoding 2D inputs into DAGs. An encoding can be input-agnostic (based on input size only) or input-driven (depending on symbols). Three distinct input-agnostic encodings characterize classes of picture languages accepted by returning finite automata, boustrophedon automata, and online tessellation automata. Encoding a string as a simple directed path limits recognition to regular languages. However, input-driven encodings allow DAG automata to recognize some context-sensitive string languages and outperform online tessellation automata in two dimensions.