CHARACTERIZING TWO-DIMENSIONAL SOFIC SYSTEMS
In this paper, three different ways of characterizing two-dimensional sofic systems are presented. The first characterization is as a symbolic factor of a subshift of finite type. The second is in terms of two-dimensional follower set and the third is in terms of two-dimensional semi-groups. The relationship between two-dimensional sofic systems and subshift of finite type is also showed. We prove that as in the one-dimensional case, every subshift of finite type is a sofic system, but the converse is not necessarily true. Some examples are presented to illustrate this relationship.
subshifts of finite type, sofic system and semi-group.