Sentences and Circuits
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Bruce H. Barnes', 'PO_EMAI': None, 'PO_PHON': None}
The expressive power of sentences on finite models and the                      computational power of circuits with unbounded fan-in will be studied.          Lower bounds on the depth and size of two kinds of circuits will be             considered:  those whose gates are AND, or, and NOT, and those whose            gates are threshold functions.  In addition, the effectiveness of some          learning algorithms for threshold circuits will be investigated.                                                                                                Another topic is the average behavior of relational data bases that are         subjected to random updates.  Recent results of the principal                   investigator show that, in certain cases, as the data base evolves, the         truth of a query approaches a limiting value independent of the initial         configuration of the data base.  The proposed research is to extend             these results to more general cases.                                                                                                                            Work in finite model theory is planned.  One topic is to obtain                 nonlinear time lower bounds using model-theoretic reductions.  The              other is to analyze the asymptotic behavior of the probability of               sentences over certain classes of finite models.
{'FirstName': 'James', 'LastName': 'Lynch', 'PI_MID_INIT': 'F', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'James F Lynch', 'EmailAddress': 'jlynch@clarkson.edu', 'NSF_ID': '000167759', 'StartDate': '07/15/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Clarkson University', 'CityName': 'POTSDAM', 'ZipCode': '136761401', 'PhoneNumber': '3152686475', 'StreetAddress': '8 CLARKSON AVE', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'New York', 'StateCode': 'NY', 'CONGRESSDISTRICT': '21', 'CONGRESS_DISTRICT_ORG': 'NY21', 'ORG_UEI_NUM': 'SL2PF6R7MRN1', 'ORG_LGL_BUS_NAME': 'CLARKSON UNIVERSITY', 'ORG_PRNT_UEI_NUM': 'SL2PF6R7MRN1'}
{'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'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8805880.xml'}