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.
MSC:
 68Q45 Formal languages and automata
Keywords:
plane homogeneous structures
Full Text: