Accession Number : ADA328418

Title :   Labelled Formal Languages and Their Uses.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Greene, Daniel H.

PDF Url : ADA328418

Report Date : MAY 1991

Pagination or Media Count : 158

Abstract : This research augments formal languages with the machinery necessary to describe labelled combinatorial objects such as trees, permutations, and networks. The most attractive feature of this method of describing combinatorial objects is the direct translation to generating functions, treating the grammar of an ordinary formal language as a set of equations and then solving these equations yields an enumerating generating function. This is still true of labelled formal languages although the equations are usually differential rather than rational or algebraic. There are two promising applications for labelled formal languages. In the analysis of algorithms one often identifies combinatorial quantities that can be described with labelled formal languages and, using the translation mentioned about, these quantities can be easily computed. The other application uses labelled formal languages to control a general-purpose system for the ranking, sequencing, and selection of combinatorial objects. Both of these applications demonstrate the value of labelled formal languages as a descriptive and analytic tool.

Descriptors :   *ALGORITHMS, *PROGRAMMING LANGUAGES, COMPUTER LOGIC, COMPUTER PROGRAMMING, THESES, COMBINATORIAL ANALYSIS, PERMUTATIONS, FIELDS(COMPUTER PROGRAMS), CONTEXT SENSITIVE GRAMMARS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE