Complexity Measures for Language Recognition by Canonic Systems.
Abstract
A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C sub m, called a proof measure function, which is an indication of the complexity of the language defined. For certain simple but important classes of canonic systems, algebraic bounds on these functions can be derived from the structure of the system. Another transformation on C produces a system C sup (-1) which characterizes the recognition of strings generated by C. A relationship exists between the measure functions of C and C sup (-1), thus relating the complexity of the recognition procedure to that of the language description. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1970
- Accession Number
- AD0715134
Entities
People
- Joseph P. Haggerty
Organizations
- Massachusetts Institute of Technology