Simulating Parallel Internal Column Contextual Array Grammars Using Two-Dimensional Parallel Restarting Automata with Multiple Windows

摘要

The connection between picture languages and restarting automata has been established in Otto (2014). An interesting class of picture languages generated by parallel contextual array grammars was studied with application in image generation and analysis in Subrama-nian et al. (2008). In this paper, we introduce a variant of two dimensional restarting automata that accepts a subclass of parallel internal contextual array languages. We show that these automata can simulate parallel internal column contextual array grammars in reverse order.