zbMATH — the first resource for mathematics

On the simulation of growth of convex and tree-like configurations inhomogeneous structures. (English. Russian original) Zbl 0836.68066
Discrete Math. Appl. 5, No. 3, 217-232 (1995); translation from Diskretn. Mat. 7, No. 2, 61-78 (1995).
Summary: We consider models of growth of some configurations in plane homogeneous structures and also discuss a possibility of self-reconstruction of such configurations. In particular, we investigate the growth and self- reconstruction of discrete analogues of convex polygons and trees. We show that the construction and self-reconstruction can be fulfilled in linear time with respect to the diameter \(D\) of the configuration, using \(O(m \log D)\) states for a polygon with \(m\) edges, \(O(D)\) states for the self-reconstruction of a convex configuration, and \(O (\log h + \log p + \log \ell)\) for a tree, where \(h\) is the number of layers, \(p\) is the branching degree, and \(\ell\) is the width of the tree.
68Q45 Formal languages and automata
Full Text: DOI