In a recent paper Maurer, Rozenberg, and Welzl [1] introduced a system of representing pictures drawn on the Cartesian unit grid as walks defined by words over the alphabet &pgr;={u,d,r,l}, where u, d, r, and l stand for a unit move up, down, right, and left, respectively. Two pictures which can be superimposed on each other with a translation are regarded as equivalent, and the corresponding equivalence classes are called basic pictures. A variant of this notion, which gives the start point and the end point of the picture, is also considered. Sets of pictures are called picture languages, and such a language is termed regular, linear, context-free, etc., if it can be defined by a &pgr;-language of the appropriate type. This paper discusses some complexity and decidability questions for picture languages. The newness and the difficulty of these problems are due to the fact that any nontrivial picture can be represented in many different ways.

The first topic considered concerns minimal representations in a &pgr;-language L of a given picture belonging to the corresponding picture language bpic(L). Let f be a function from the set of basic pictures into the set of positive integers. A &pgr;-language L is f-optimal if for every p in bpic(L) there is a word in L of length at most f(p) representing p. For regular and linear &pgr;-languages the authors give asymptotically tight bounds for f which are polynomial in the size of the pictures. They also show that for context-free languages such a bound must be exponential.

The membership problem is shown to be NP-complete for regular and linear picture languages. Furthermore, it turns out that the emptiness of the intersection of two regular picture languages is undecidable. In view of these somewhat discouraging findings, the authors turn their attention to a subclass of the picture languages.

A stripe picture language consists of pictures which can be drawn into a stripe defined by two parallel lines. The authors do not try to justify this notion with any concrete examples where it is applicable; but, at least from a mathematical point of view, the choice appears fortunate. For example, it is decidable whether or not a context-free picture language is a stripe language, and regular stripe picture languages are shown to have some desirable decidability properties.

The authors skillfully utilize many results and techniques from the theory of formal languages. The pictorial component of the topic also contributes to the readability of this excellent paper.