DECISION-PROBLEMS AND REGULAR CHAIN CODE PICTURE LANGUAGES

By interpretation of the letters u, d, r, l, up, down as ''move up, (d own, right, left)'' with the pen, ''lift'' and ''sink'' the pen of a p lotter we can associate a picture with a word. The set of pictures ass ociated with the words in a regular (context-free) string language is called a regular (context-free) picture language or chain code picture language. In this paper we discuss the decidability status of the fol lowing problems for regular and context-free picture languages: Is som e picture a subpicture of all pictures of the language? Does the langu age contain a picture with a given property? Have all pictures of the language a given property?