Accession Number : AD0780355

Title :   Structure of Growth in Lindenmayer Systems,

Corporate Author : MATHEMATISCH CENTRUM AMSTERDAM (NETHERLANDS) AFDELING INFORMATICA

Personal Author(s) : Vitanyi,Paul M. B.

Report Date : 27 JAN 1973

Pagination or Media Count : 10

Abstract : Growth of word length in some rewriting systems (DOL's) is investigated by combinatorial arguments concerning the structure of production trees of individual letters. Several growth types are distinguished and algorithms are obtained to classify letters, DOL's and semi DOL's in these types. It is shown that polynomial growth can not occur without accompanying limited growth. A conceptually easy characterization of the nature of the different growth types is given, yielding expressions for the slowest growth possible in each growth type.

Descriptors :   *Language, *Mathematical logic, *Combinatorial analysis, Set theory, Recursive functions, Algorithms, Netherlands

Subject Categories : Linguistics
      Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE