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
Distribution Statement : APPROVED FOR PUBLIC RELEASE