
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