Accession Number : AD0715134

Title :   Complexity Measures for Language Recognition by Canonic Systems.

Descriptive Note : Master's thesis,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s) : Haggerty,Joseph P.

Report Date : OCT 1970

Pagination or Media Count : 48

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)

Descriptors :   (*SET THEORY, THEOREMS), (*PROGRAMMING LANGUAGES, DESIGN), COMPILERS, MATHEMATICAL LOGIC, THESES

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE