Rational and affine expressions for image description. (English) Zbl 0784.68058

The authors present methods based on automata techniques to generate and infer ‘images’. Languages and relations over an arbitrary alphabet are treated as images, strings being considered as rational coordinates. The generation of an images is done from a set of rational or affine expression.
The most important parts of the article is generation, including comparison of various methods. For inference the authors sketch a quad- tree approach and announcee (added in proof) an automated algorithm for data compression based on slight extension of these techniques and wavelets.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI


[1] Barnsley, M. F., Fractals Everywhere (1988), Academic Press: Academic Press New York · Zbl 0691.58001
[2] Barnsley, M. F.; Devaney, R. L.; Mandelbrot, B. B.; Peitgen, H.-O.; Saupe, De; Voss, R. F., Science of Fractal Images (1988), Springer: Springer Berlin
[3] Barnsley, M. F.; Jacquin, A.; Reuter, L.; Sloan, A. D., Harnessing chaos for image synthesis, Computer Graphics, SIGGRAPH 1988 Conference Proceedings (1988)
[4] Berstel, J.; Morcrette, M., Compact representation of patterns by finite automata, Proceedings Pixim ’89, 387-402 (1989), Paris
[5] Berstel, J.; Nait Abdallah, A., Quadtrees generated by finite automata, AFCET 61/62, 167-175 (1989)
[6] Boasson, L.; Nivat, M., Adherences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[7] Cohen, R.; Gold, A., Theory of ω-languages, Part I and II, J. Comput. System Sci., 15, 169-208 (1977)
[8] Culik, K.; Dube, S., Affine automata and related techniques for generation of complex images, (Tech. Rept. TR90009, 452 (1990), Department of Computer Science, University of S. Carolina), 224-231, Preliminary version in: Proceedings of MFCS 1990, Lecture Notes in Computer Science Springer, Berlin
[9] Culik, K.; Yu, S., Cellular automata, ωω-regular sets, and sofic systems, Discrete Appl. Math., 32, 85-101 (1991) · Zbl 0743.68085
[10] Even, S., Rational numbers and regular events, IEEE Trans. Electron. Comput., 13, 740-741 (1964) · Zbl 0178.33101
[11] Gleick, J., Chaos—Making a New Science (1988), Penguin Books: Penguin Books Harmondsworth · Zbl 0706.58002
[12] Hartmanis, J.; Stearns, R. E., Sets of numbers defined by finite automata, Amer. Math. Monthly, 74, 539-542 (1967) · Zbl 0149.01002
[13] Hunter, G. M.; Steiglitz, K., Operations on images using quadtrees, IEEE Trans. Pattern Anal. Machine Intell., 1, 145-153 (1979)
[14] Mandelbrot, B., The Fractal Geometry of Nature (1982), Freeman: Freeman San Francisco, CA · Zbl 0504.28001
[15] Mazoyer, J., An overview of the firing squad synchronization problem, (Choffrut, C., Automata Networks, 316 (1988), Springer: Springer Berlin), 82-94, Lecture Notes in Computer Science · Zbl 0656.68054
[16] Shallit, J.; Stolfi, J., Two methods for generating fractals, Comput. Graphics, 13, 185-191 (1989)
[17] Staiger, L., Quadtrees and the Hausdorff dimension of pictures, Workshop on Geometrical Problems of Image Processing, 173-178 (1989), Georgenthal · Zbl 0679.68169
[18] Tzeng, W. G., The equivalence and learning of probabilistic automata, FOCS Proceedings, 268-273 (1989)
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.