| NSF Org: |
DMS Division Of Mathematical Sciences |
| Recipient: |
|
| Initial Amendment Date: | April 12, 2001 |
| Latest Amendment Date: | March 3, 2005 |
| Award Number: | 0100035 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Christopher Stark
DMS Division Of Mathematical Sciences MPS Directorate for Mathematical and Physical Sciences |
| Start Date: | June 1, 2001 |
| End Date: | May 31, 2007 (Estimated) |
| Total Intended Award Amount: | $300,000.00 |
| Total Awarded Amount to Date: | $328,440.00 |
| Funds Obligated to Date: |
FY 2002 = $60,000.00 FY 2003 = $60,000.00 FY 2004 = $60,000.00 FY 2005 = $88,440.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
341 PINE TREE RD ITHACA NY US 14850-2820 (607)255-5014 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
341 PINE TREE RD ITHACA NY US 14850-2820 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | FOUNDATIONS |
| Primary Program Source: |
app-0102 app-0103 app-0104 app-0105 |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.049 |
ABSTRACT
The proposed project includes research into a broad range of topics in computability theory (recursion theory) and logic both theoretical and applied to other areas of mathematics and computer science. Included in the first area are investigations of the structures of sets and functions ordered by relative complexity of computation. Particular emphasis will be placed on the issue of definability in the complexity structures of all sets and those which are effectively enumerable. Included in this area is the analysis of the relations between difficulty of computing functions and other issues such as rates of growth, complexity of their definitions in arithmetic and the strength of axiom systems needed to prove their existence. Applications of the methods of pure computability theory will be made in the areas of computable algebra and model theory. General methods will be developed for transferring results from arbitrary structures to ones in specific classes of interest such as lattices, groups and rings. Another area where issues of computability and complexity are to be studied is that of modal and intuitionistic logics and their model theory. These logics are now used to model issues in program verification and computer security. The second area includes the study of structures representable by finite automata, decision procedures, the analysis and development of nonmonotonic logic, concurrent programming models, and applications of linear programming ideas and algorithms to data structures and logic programming. A primary focus here will be the logical and mathematical foundations of hybrid (continuous and discrete) control theory as well as the practical implementation of algorithms for these subjects based on the theoretical work being done. An important tool to be developed in this area is that of infinitary automata.
The research proposed is of two types. The first is directed at a better understanding of the fundamental notions of computability and relative difficulty of computation for different tasks. The theoretical work deals both with the abstract notion of computability as well as with applications to specific branches of, and questions in, other areas of mathematics. One important application (within mathematics) concerns the general question of what starting information is needed to be able to compute various aspects of many important classes of mathematical structures. In practical terms, the results at times indicate that there are no algorithms for certain important tasks or that more information than might have been expected is needed to write programs calculating the desired results. Another aspect of this work stresses the impact that the specific concrete choice of representation of an abstract mathematical structure has on one's ability to compute specific functions and relations. The second type deals more directly with developing the mathematical (and especially logical) tools needed for the crucial areas of program verification, data management and automated control of real-world complex systems. Commercial applications are expected for some of this work and there has already been a spin off to a start-up company developing several applications including data compression and network management algorithms. Other applications of these techniques to be investigated include multimedia applications and distributed continuous systems.
Please report errors in award information by writing to: awardsearch@nsf.gov.
