The finiteness of synchronous, tabled picture languages is decidable

摘要

In the present paper, synchronous, tabled chain code picture systems based on Lindenmayer systems (sTOL system) are studied with respect to the finiteness of their picture languages. The finiteness is proved to be decidable. Additionally, a method is given for deciding whether or not an sTOL system generates a finite picture language. Chain code picture systems give a possibility for describing pictures. They are based on generating words over a special alphabet and interpreting these words as pictures. They can be regarded as a formal description of the method of working of plotters. FREEMAN introduced chain code picture languages. A picture is formed by a sequence of drawing commands represented by symbols (letters). A string describes a picture, which is built by the drawing commands of its letters. FREEMAN used the alphabet {0,..., 7}, whose elements are interpreted according to the following sketch.