Planar Map Generation by Parallel Binary Fission/Fusion Grammars

A new class of formal grammatical systems, based upon simultaneous (parallel) rewriting of symbols in strings, was introduced by A. Lindenmayer [1], intended as a theoretical model for development of filamentous biological organisms, e.g., by cell-division. Lindenmayer’s contributions have stimulated widespread interest and research in theoretical models for parallel generation in computer science as well as in biology. Initial advances pertained to string-based systems, i.e., linear or one-dimensional structures, but were followed by numerous proposals for addressing the difficult problem of generalization to nonlinear systems, capable of modeling development in two- or three-dimensional organisms or complex data structures. Some references to multi-dimensional or graph generation are given here [2,3,4,6,7,8,9,10,12,13,14,17], with emphasis on those relating to parallel generation, but space permits us only limited coverage, which may be augmented by consulting a recent comprehensive bibliography [16].