Weighted Two-Dimensional Finite Automata

摘要

Two-dimensional finite automata (2D-FA) are a natural generalization of finite automata to two-dimension and used to recognize picture languages. In order to study quantitative aspects of computations of 2D-FA, we introduce weighted two-dimensional finite automata (W2D-FA), which can represent, functions from some input alphabet into a semiring. In this work, we investigate some basic properties of these functions like upper bounds and closure properties. First, we prove that the value of such a function is bounded by 2~(O(n~2)). Then, we will see that this upper bound is actually sharp, and a deterministic W2D-FA of a restricted type already can compute a function that reaches this bound. Finally, we study the closure properties of the classes of functions that are computed by W2D-FA of various types under some rational operations, e.g., sum, Hadamard product, vertical (horizontal) multiplication, and scalar multiplication.