Abstract. This paper introduces different types of picture grammars (or array grammars) and plane finite automata with controlled reading. The proof of the equivalence between classes of plane finite automata languages and some of classes of picture languages is given. This paper also contains some results about the complexity of the membership problem in different classes of picture languages. Namely, classes with linear-time and cubic-time decidable membership problem are found as well as classes with NP-complete membership problem.

Full text (in electronic form) is available on request.