# zbMATH — the first resource for mathematics

A transformation system for generating description languages of chain code pictures. (English) Zbl 0678.68067
Summary: A picture is a set of unit lines from the cartesian plane considered as a squaregrid. To each connected picture a description is given by a word over the alphabet $$\{$$ r,l,u,d$$\}$$, where “r” means “go one unit line right from the current point and draw this unit line” and l,u,d are interpreted analogously with “left”, “up” and “down”, respectively. For a picture p, it was shown in [H. A. Maurer, G. Rozenberg and (INVALID INPUT)E. Welzl; Inf. Control. 54, 155-185 (1982; Zbl 0523.68065)] that the description language, i.e. all the words which describe the picture p, is a regular one. To construct such a regular language one needs geometric information about the picture. We present a system of transformations, which map one word over the alphabet $$\{$$ r,l,u,d$$\}$$ to another word, which describes the same picture. It is also shown that exactly all the picture descriptions can be generated, started by some word.

##### MSC:
 68Q45 Formal languages and automata 68T10 Pattern recognition, speech recognition
Full Text:
##### References:
 [1] M.R. Garey, D.S. Johnson, Computers and Interactability—A Guide to the Theory of NP-Completeness (Freeman, San Francisco). · Zbl 0411.68039 [2] Ginsburg, S., The mathematical theory of contextfree languages, (1966), McGraw-Hill New York · Zbl 0184.28401 [3] R. Gutbrod, Chain code picture languages, Diplomarbeit. · Zbl 0678.68067 [4] R. Gutbrod, Properties of picture description transformations for chain code picture languages, manuscript. · Zbl 0678.68067 [5] Hinz, F., Regular chain code picture languages of nonlinear descriptional complexity, (), 414-421 [6] Hinz, F., Bildsprachen von nichtlinearer beschreibungs-komplexität, Diplomarbeit, (1986) [7] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001 [8] Kim, C.; Sudborough, I.H., The membership and the equivalence problem for picture languages, Theoret. comput. sci., 52, 177-191, (1987) · Zbl 0636.68117 [9] Maurer, H.A.; Rozenberg, G.; Welzl, E., Using string languages to describe picture languages, Inform. and control, 54, (1982) · Zbl 0523.68065 [10] Maurer, H.A.; Rozenberg, G.; Welzl, E., Chain code picture languages, (), 232-244 [11] Noltemeier, H., Graphentheorie, (1976), de Gruyter Lehrbuch Berlin · Zbl 0308.05101 [12] Saloma, A.K., Formale sprachen, (1978), Springer Berlin [13] Shaw, A.C., A formal picture description scheme as a basis for picture processing systems, Inform. and control, 14, 9-52, (1969) · Zbl 0167.18203 [14] Sudborough, I.H.; Welzl, E., Complexity and decidability for chain code picture languages, Theoret. comput. sci., 36, 173-202, (1985) · Zbl 0565.68065 [15] Welzl, E., Chain code picture languages, Dissertation, (1983) · Zbl 0522.68069 [16] Winkler, G., Bildbeschreibungssprachen—was sie sind und was sie leisten, Ifb, 17, 107-125, (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.