Complexity and decidability for chain code picture languages (Q1058857)

A picture description is a word over the alphabet \(\{\) u,d,r,l\(\}\), where u means ''go one unit line up from the current point'', and d,r, and l are interpreted analogously with down, right, and left instead of up. By this, a picture description describes a walk in the plane - its trace is the picture it describes. A set of picture descriptions describes a (chain code) picture language. This paper investigates complexity and decidability questions for these picture languages. Thus it is shown that the membership problem is NP-complete for regular picture languges (i.e., picture languages described by regular languages of picture descriptions), and that it is undecidable whether two regular picture description languages describe a picture in common. After this we investigate so-called stripe picture languages (all pictures are within a stripe defined by two parallel lines), providing 'better' complexity and decidability results: Membership is decidable in linear time for regular stripe picture languages. Emptiness of intersection and equivalence is decidable for regular stripe picture languages.