Testing Program Correctness
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Krishna M. Kavi', 'PO_EMAI': None, 'PO_PHON': None}
This proposal seeks to develop mathematical methods of computer              science for the purpose of testing program correctness.  The simpler            but nevertheless nontrivial problem of deciding whether or not a given          program on a given input outputs the correct answer will be                     investigated.                                                                      Consider a program P that, while having been written to solve                general instances of a certain problem, is actually run on just one or          a few select instances.  In this case, instead of proving the                   correctness of program P on all inputs, it suffices to prove that the           output of P on the given few instances is correct (or to exhibit a bug          in P).                                                                             For example, suppose program P is supposed to decide if two graphs G         and H are isomorphic.  If P supplies the isomorphism, then it is easy           to check that the isomorphism really works.  Interestingly, the                 interactive proof for graph nonisomorphism serves to test the                   correctness of a program that asserts that G and H are not isomorphic.          Given any program for graph isomorphism, this test procedure either             gives quantifiable mathematical evidence that the program's answer is           correct, or else it proves that the program has a bug.                             This raises the question: which computational problems (such as              graph isomorphism) have the property that a program for the problem on          any given input can be efficiently tested for correctness?  Initial             studies show that a large collection of programming problems drawn from         block designs, graphs, codes, matrices over GF(q), latin squares, etc.,         can be tested by similar techniques.  A useful natural (group                   theoretic) description of a broad class of computational problems,              including those mentioned above, whose programs can be tested by such           schemes is sought.
{'FirstName': 'Manuel', 'LastName': 'Blum', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Manuel Blum', 'EmailAddress': 'mblum@cs.cmu.edu', 'NSF_ID': '000098920', 'StartDate': '09/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'University of California-Berkeley', 'CityName': 'BERKELEY', 'ZipCode': '947101749', 'PhoneNumber': '5106433891', 'StreetAddress': '1608 4TH ST STE 201', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'California', 'StateCode': 'CA', 'CONGRESSDISTRICT': '12', 'CONGRESS_DISTRICT_ORG': 'CA12', 'ORG_UEI_NUM': 'GS3YEVSS12N6', 'ORG_LGL_BUS_NAME': 'REGENTS OF THE UNIVERSITY OF CALIFORNIA, THE', 'ORG_PRNT_UEI_NUM': None}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
[{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}, {'Code': '2865', 'Text': 'NUMERIC, SYMBOLIC & GEO COMPUT'}, {'Code': '2880', 'Text': 'SOFTWARE ENGINEERING AND LANGU'}, {'Code': '9145', 'Text': 'SPECIAL PROGRAMS-RESERVE'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8813632.xml'}