Affine Automata and Classical Fractals
- PDF / 147,304 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 28 Downloads / 160 Views
AFFINE AUTOMATA AND CLASSICAL FRACTALS
UDC 519.713.4
I. K. Rystsov
Abstract. This article reveals the relationship between fractal geometry and automata theory. It is shown that at least classical fractals are attractors of contracting affine automata and also that the symbolic space of a contracting affine automaton is continuously mapped onto its attractor. Keywords: affine automaton, fractal, attractor. INTRODUCTION B. Mandelbrot, the founder of fractal geometry [1], noted in his addition to [2] that, in his investigations, he relied on works of G. Cantor, F. Hausdorff, V. Sierpinski, and many other mathematicians. B. Mandelbrot introduced the concept of a fractal, i.e., a geometric figure that may be considered as the antipode of a smooth figure. Many fractals have the property of self-likelihood, i.e., are sets of points invariant under some similarity transformations. Whereas earlier the constructions of such sets constructed by G. Cantor and V. Sierpinski seemed to many mathematicians to be “monsters” or exceptions from the general rule, the situation radically changed with the appearance of fractals. It turned out that it is fractality rather than smoothness that is peculiar to many natural forms [1]. B. Mandelbrot also noted the close relationship of fractal geometry with dynamic systems, namely, many fractals are limiting objects (attractors) of some dynamic processes. Continuing works of Julia and Fatou, B. Mandelbrot was engaged in the theory of iterations of quadratic maps onto the complex plane and constructed a set called by his name later on [2]. The purpose of this article is to establish a relationship between fractal geometry and automata theory. At first sight, this relationship seems to be unusual, however, automata are typical representatives of discrete dynamic systems and, consequently, can have attractors. Here, we restrict ourselves to the consideration of affine automata, which are sufficient for the construction of classical fractals. Note that affine transformations were already used for constructing fractals called “iterated function systems” [3]. Automata allow one not only to avoid the use of this incorrect terminology (since any system of functions can be iterated) but have obvious methodical advantages over this approach and present the theoretical basis for constructing fractals in the form of discrete dynamic systems. 1. AFFINE AUTOMATA Note that a Euclidean space is understood to be a finite-dimensional linear vector space R q , where R is the field of real numbers supplied with the Euclidean metrics, i.e., between any two vectors s = ( s1 , ..., sq ) and t = ( t1 , K , t q ) , the following distance is defined:
|| s - t || = ( s1 - t1 ) 2 + K + ( sq - t q ) 2 .
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, January–February, 2018, pp. 13–23. Original article submitted March 22, 2017. 1060-0396/18/5401-0011 ©2018 Springer Science+Business Media, LL
Data Loading...
