Labelled Formal Languages and Their Uses.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1991
- Accession Number
- ADA328418
Entities
People
- Daniel H. Greene
Organizations
- Stanford University