Boustrophedon Pushdown Automata for Two-Dimensional Picture Languages
摘要
In the area of picture languages, many mechanisms have been studied to describe language classes, often inspired by what has been done before for string languages. Following this tradition, we are now introducing a pushdown automaton (PDA) extension of two previously defined variants of finite automata (FA) working on arrays, namely boustrophedon finite automata (BFA) and returning finite automata (RFA), leading to BPDA and RPDA, respectively. While BFA and RFA characterize the same class of array languages, BPDA and RPDA turn out to describe incomparable classes of array languages. We also prove that BPDA and RPDA can be viewed as a proper generalization of context-free matrix languages, which is interesting, as it is known that (apart from a transposition) BFA and RFA characterize the regular matrix languages.