Probability is more powerful than team for language identification from positive data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Probability is more powerful than team for language identification from positive data

Full text

Pdf (700 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 192 - 198

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Sanjay Jain
Arun Sharma

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 24, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/168304.168331 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	2	J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15-32, 1974.
	3	John Case , Christopher Lynes, Machine Inductive Inference and Language Identification, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.107-115, July 12-16, 1982
	4	Robert Daley , Bala Kalyanasundaram , Mahendran Velauthapillai, Breaking the probability ½ barrier in FIN-type learning, Proceedings of the fifth annual workshop on Computational learning theory, p.203-217, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130408]
	5	Robert Daley , Leonard Pitt , Mahendran Velauthapillai , Todd Will, Relations between probabilistic and team one-shot learners (extended abstract), Proceedings of the fourth annual workshop on Computational learning theory, p.228-239, August 05-07, 1991, Santa Cruz, California, United States
	6	R. Freivalds. Functions computable in the limit by probabilistic machines. Mathematical Foundations of Computer Scsence, 1975.
	7	R. Freivalds. Finite identification of general recursive functions by probabilistic strategies. In Proceedings o/ the Conference on Algebraic, Arsthmetlc and Categor. scal Methods in Computation Theory, pages 138-145. Akedemie-Verlag, Berlin, 1979.
	8	R. Freivalds. On the principle capabilities of probab'distic algorithms in inductive inference. Semwtika Inform, 12:137-140, 1979.
	9	Mark Andrew Fulk, A study of inductive inference machines, State University of New York at Buffalo, Buffalo, NY, 1986
	10	Mark A. Fulk, Prudence and other conditions on formal language learning, Information and Computation, v.85 n.1, p.1-11, March 1990 [doi>10.1016/0890-5401(90)90042-G]
	11	Gill. Computational complexity of probabilistic turing machines. SIAM Journal of Computing, 1977.
	12	E. M. Gold. Language identification in the limit. {nformation and Control, 10:447-474, 1967.
	13	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	14	Sanjay Jain , Arun Sharma, Finite learning by a “team”, Proceedings of the third annual workshop on Computational learning theory, p.163-177, August 06-08, 1990, Rochester, New York, United States
	15	Sanjay Jain , Arun Sharma, Language learning by a “team”, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.153-166, July 1990, Warwick University, England
	16	Daniel N. Osherson , Michael Stob , Scott Weinstein, Aggregating inductive expertise, Information and Control, v.70 n.1, p.69-95, July 1986 [doi>10.1016/S0019-9958(86)80025-0]
	17	L. Pitt. A characterization of probabilistic inference. In Proceedings of the ~5th Symposium on the Foundations of Computer Science, 1984.
	18	L. Pitt. A characterization of probabilistic inference. PhD thesis, Yale University, 1984.
	19	L. Pitt, Probabilistic inductive inference, Journal of the ACM (JACM), v.36 n.2, p.383-433, April 1989 [doi>10.1145/62044.62053]
	20	Leonard Pitt , Carl H. Smith, Probability and plurality for aggregations of learning machines, Information and Computation, v.77 n.1, p.77-92, April 1988 [doi>10.1016/0890-5401(88)90046-6]
	21	H. Rogers. G6del numberings of partial recursive functions. Journal of Symbolic Logic, 23:331-341, 1958.
	22	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	23	Mahendran Velauthapillai, Inductive inference with bounded number of mind changes, Proceedings of the second annual workshop on Computational learning theory, p.200-213, December 1989, Santa Cruz, California, United States