zbMATH — the first resource for mathematics

Minimizing picture words. (English) Zbl 0735.68053
Aspects and prospects of theoretical computer science, Proc. 6th Int. Meet. Young Comput. Sci., Smolenice/Czech. 1990, Lect. Notes Comput. Sci. 464, 234-243 (1990).
Summary: [For the entire collection see Zbl 0732.00023.]
With any word over the alphabet $$D=\{r,\bar r,u,\bar u\}$$, we associate connected picture in the following manner: the reading of each letter of this word induces a unit like: $$r$$ ($$\bar r, u, \bar u$$ resp.) stands for a right (left, up, down resp.) move. We present a rewriting system which allows to obtain, from any word over D, all the words describing the same picture. Particularly, we give an algorithm to find in finite time, a minimal word describing a given picture: this word represents the shortest way to draw this picture ”without pen-up”.

MSC:
 68Q45 Formal languages and automata