Synthesizing enumeration techniques for language learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Synthesizing enumeration techniques for language learning

Full text

Pdf (1.36 MB)

Source

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

Desenzano del Garda, Italy

Pages: 169 - 180

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Ganesh R. Baliga	Computer Science Department, Rowan College of New Jersey, Mullica Hill, NJ
John Case	Department of CIS, University of Delaware, Newark, DE
Sanjay Jain	Department of ISCS, National University of Singapore, Singapore

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
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): 14, Downloads (12 Months): 27, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/238061.238090 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.

	Ang80a	D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980.
	Ang80b	D. Angluin. Inductive inference of formal lang uages from positive data.Information and ontrol, 45:117-135, 1980.
	Ang82	Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
	AS83	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
	Bar74	J. Barzdin. Two theorems on the limiting synthesis of functions. In Theory of Algorithms and Programs, Latvian State Umversity, R~ga, 210:82-88, 1974.
	BB75	L. Blum and M. Blum. Toward a mathematical theory of inductive inference. Information and Control, 28:125-155, 1975.
	BC93	Ganesh Baliga , John Case, Learnability: admissible, co-finite, and hypersimple languages, Journal of Computer and System Sciences, v.53 n.1, p.26-32, Aug. 1996 [doi>10.1006/jcss.1996.0047]
	BCJ95	Ganesh Baliga , John Case , Sanjay Jain, Language learning with some negative information, Journal of Computer and System Sciences, v.51 n.2, p.273-285, Oct. 1995 [doi>10.1006/jcss.1995.1066]
	Ber85	Robert C. Berwick, The acquisition of syntactic knowledge, Massachusetts Institute of Technology, Cambridge, MA, 1985
	BF72	J. Barzdin and R. Freivalds. On the prediction of g{~neral recursive functions. Sower Mathematics okladyj 13:1224-1228~ 1972.
	Blu67	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]
	Cas74	J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15-32, 1974.
	Cas86	J. Case. Learning machines. In W. Demopoulos and A. Marras, editors, Language Learning and Concept Acquisition. Ablex Publishing Company, 1986.
	Cas88	John Case, The power of vacillation, Proceedings of the first annual workshop on Computational learning theory, p.196-205, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	Cas92	J. Caee. The power of vacillation in language learning. Technical Report 93-08, University of Delaware, 1992. Expands on {Cas88}; journal version revised for possible pubIication.
	Cas94	J. Case. Infinitary self-reference in learning theory. Journal of Experimental and Theoretical Artificial Intelligence, 6:3-16, 1994.
	CL82	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
	CS78	John Case , Carl Smith, Anomaly hierarchies of mechanized inductive inference, Proceedings of the tenth annual ACM symposium on Theory of computing, p.314-319, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804360]
	CS83	J. Case and C. Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25:193-220, 1983.
	dJK96	Dick de Jongh , Makoto Kanazawa, Angluin's theorem for indexed families of r.e. sets and applications, Proceedings of the ninth annual conference on Computational learning theory, p.193-204, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238095]
	Fre85	R. Freivalds. Recursiveness of the enumerating functions increases the inferrability of recursively enumerable sets. Bulletin of the European Association for Theoretical Computer Science, 27:35-40, 1985.
	Ful85	Mark Andrew Fulk, A study of inductive inference machines, State University of New York at Buffalo, Buffalo, NY, 1986
	Ful90a	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]
	Ful90b	M. Fulk. Robust separations in inductive inference. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 405-410, St. Louis, Missouri 1990.
	Gle86	L. Gleitman. Biological dispositions to learn language. In W. Demopoulos and A. Marras, editors, Language Learning and Concept Acquisition. Ablex Publ. Co., 1986.
	Gol67	E. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
	HU79	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	Kir92	D. Kirsh. PDP learnability and innate knowledge of language. In S. Davis, editor, Connect~omsm: Theory and Practice, pages 297-322. Oxford University Press, NY, 1992.
	KLHM93	S. Kapur, B. Lust, W. Harbert, and G. Martohardjono. Universal grammar and learnability theory: The case of binding domains and the 'subset principle'. In E. Reuland and W. Abraham, editors, Knowledge and Language, volume I, pages 185-216. Kluwer, 1993.
	KW80	R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR mathematicians - A survey. Information Sciences, 22:149- 169, 1980.
	LM89	N. Littlestone and Warmuth M. The weighted majority algorithm. In Symposium on the Theory of Computation, pages 256-261, 1989.
	LZ93	Steffen Lange , Thomas Zeugmann, Language learning in dependence on the space of hypotheses, Proceedings of the sixth annual conference on Computational learning theory, p.127-136, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168320]
	MR67	Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
	Muk92	Yasuhito Mukouchi, Characterization of Finite Identification, Proceedings of the International Workshop on Analogical and Inductive Inference, p.260-267, October 05-09, 1992
	MW87	R. Manzini and K. Wexler. Parameters, binding theory and learnability. Lingmstic Inquiry, 18:413-444, 1987.
	MY78	Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
	OSW82	D. Osherson, M. Stob, and S. Weinstein. Ideal learning machines. Cognitive Science, 6:277-290, 1982.
	OSW84	D. Osherson, M. Stob, and S. Weinstein. Learning theory and natural language. Cognition, 17:1-28, 1984.
	OSW86a	D. Osherson, M. Stob, and S. Weinstein. An analysis of a learning paradigm. In W. Demopoulos and A. Marras, editors, Language Learning and Concept Acquisztion. Ablex Pub- 1. Co., 1986.
	OSW86b	Daniel N. Osherson , Michael Stob , Scott Weinstein, Systems that learn: an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986
	OSW88	Daniel N. Osherson , Micheal Stob, Synthesizing inductive expertise, Information and Computation, v.77 n.2, p.138-161, May 1988 [doi>10.1016/0890-5401(88)90055-7]
	OW82a	D. Osherson and S. Weinstein. Criteria of language learning. Information and Control, 52:123-138, 1982.
	OW82b	D. Osherson and S. Weinstein. A note on formal learning theory. Cognitwn, 11:77-88, 1982.
	PEH64	M. Pour-E1 and W. Howard. A structural criterion for recursive enumeration without repetition. Zeitschrift flit Mathemat~sche Log~k und Grundlagen der Mathematzk, 10:105-114, 1964.
	PEP65	M. Pour-E1 and H. Putnam. Recursively enunumerable classes and their applicatmn to recursive sequences of formal theories. Arch. f. Math. Log. Grund., 8:104-121, 1965.
	Pin79	S. Pinker. Formal models of language learning. Cognition, 7:217-283, 1979.
	RC94	James S. Royer , John Case, Subrecursive programming systems: complexity & succinctness, Birkhauser Verlag, Basel, Switzerland, 1994
	Rog58	H. Rogers. GSdel numberings of partial recursive functions. Journal of Symbolzc Logic, 23:331- 341, 1958.
	Rog67	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	Roy87	James S. Royer, A connotational theory of program structure, Springer-Verlag New York, Inc., New York, NY, 1987
	Sha71	N. Shapiro. Review of "Limiti ng recursion" by E.M. Gold and "Trial and error predicates and the solution to a problem of Mostowski" by l.i. Putnam. Journal of Symbolic Logic, 36:342, 1971.
	WC80	K. Wexler and P. Culicover. Formal Principles of Language Acquzsitwn. MIT Press, Cambridge, Mass, 1980.
	Wex82	K. Wexler. On extensional learnability. Cognition, 11:89-95, 1982.
	Wex93	K. Wexler. The subset principle is an intensional principle. In E. Reuland and W. Abraham, editors, Knowledge and Language, volume I, pages 217-239. Kluwer, 1993.
	Wie90	Rolf Wiehagen, A Thesis in Inductive Inference, Proceedings of the 1st International Workshop on Nonmonotonic and Inductive Logic, p.184-207, December 04-07, 1990
	ZL95	Thomas Zeugmann , Steffen Lange, A Guided Tour Across the Boundaries of Learning Recursive Languages, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.190-258, January 1995

CITED BY 3

	Sebastiaan A. Terwijn, Extensional set learning (extended abstract), Proceedings of the twelfth annual conference on Computational learning theory, p.243-248, July 07-09, 1999, Santa Cruz, California, United States
	Frank Stephan , Yuri Ventsov, Learning algebraic structures from text, Theoretical Computer Science, v.268 n.2, p.221-273, 17 October 2001
	John Case , Sanjay Jain , Arun Sharma, Synthesizing noise-tolerant language learners, Theoretical Computer Science, v.261 n.1, p.31-56, 06/17/2001