Regular chain code picture languages of nonlinear descriptional complexity. (English) Zbl 0617.68070

Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 414-421 (1986).
[For the entire collection see Zbl 0596.00021.]
A picture description is a word over an alphabet such as \(\{\) u,d,r,l\(\}\), where u means ”go one unit line up from the current point”, and d, r, 1 are interpreted analogously with ”down”, ”right”, ”left” instead of ”up”. A picture description describes a walk in the plane. The set of unit lines traversed by this walk is the corresponding picture. A regular (chain code) picture language is a set of pictures corresponding to a regular set of picture descriptions. It is shown in this paper that there exists a regular picture language P which is of nonlinear descriptional complexity (in the sense that, for every regular picture description language corresponding to P, the growth of the length of picture descriptions is quadratic in the size of the corresponding pictures). This solves a problem raised by Maurer, Rozenberg and Welzl.


68Q45 Formal languages and automata


Zbl 0596.00021