Please use this identifier to cite or link to this item:
Title: Computational Limits on Team Identification of Languages
Authors: Jain, S. 
Sharma, A.
Issue Date: 10-Oct-1996
Citation: Jain, S., Sharma, A. (1996-10-10). Computational Limits on Team Identification of Languages. Information and Computation 130 (1) : 19-60. ScholarBank@NUS Repository.
Abstract: A team of learning machines is a multiset of learning machines. A team is said to successfully identify a concept just in case each member of some nonempty subset, of predetermined size, of the team identifies the concept. Team identification of programs for computable functions from their graphs has been investigated by Smith. Pitt showed that this notion is essentially equivalent to function identification by a single probabilistic machine. The present paper introduces, motivates, and studies the more difficult subject of team identification of grammars for languages from positive data. It is shown that an analog of Pitt's result about equivalence of team function identification and probabilistic function identification does not hold for language identification, and the results in the present paper reveal a very complex structure for team language identification. It is also shown that for certain cases probabilistic language identification is strictly more powerful than team language identification. Proofs of many results in the present paper involve very sophisticated diagonalization arguments. Two very general tools are presented that yield proofs of new results from simple arithmetic manipulation of the parameters of known ones. © 1996 Academic Press, Inc.
Source Title: Information and Computation
ISSN: 08905401
DOI: 10.1006/inco.1996.0081
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.