Séébold, Patrice; Slowinski, Karine 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”. Cited in 1 ReviewCited in 2 Documents MSC: 68Q45 Formal languages and automata Keywords:rewriting system; picture word; plotter pen; graph theory; pattern recognition Citations:Zbl 0732.00023 PDFBibTeX XMLCite \textit{P. Séébold} and \textit{K. Slowinski}, Lect. Notes Comput. Sci. None, 234--243 (1990; Zbl 0735.68053)