Learnability of a subclass of extended pattern languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learnability of a subclass of extended pattern languages

Full text

Pdf (1.05 MB)

Source

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

Madison, Wisconsin, United States

Pages: 64 - 71

Year of Publication: 1998

ISBN:1-58113-057-0

Author

Andrew R. Mitchell

School of Computer Science and Engineering, University of New South Wales, Sydney 2052, Australia

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
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): 2, Downloads (12 Months): 21, Citation Count: 7

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/279943.279955 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.

	AJS97	Andris Ambainis , Sanjay Jain , Arun Sharma, Ordinal Mind Change Complexity of Language Identification, Proceedings of the Third European Conference on Computational Learning Theory, p.301-315, March 17-19, 1997
	AMS+92	S. Arikawa, S. Miyano, A. Shinohara, T. Shinohara, and A. Yamamoto. Algorithmic learning theory with elementary formal systems. IE- ICE ?Tans. Inf. and Syst., E75-D No. 4:405- 414, 1992.
	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 inf'erence of formzd languages from positive data.Information and Control, 45:117-135, 1980.
	ASMS91	Setsuo Arikawa , Takeshi Shinohara , Satoru Miyano , Ayumi Shinohara, More About Learning Elementary Formal Systems, Proceedings of the Second International Workshop on Nonmonotonic and Inductive Logic, p.107-117, December 02-06, 1991
	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
	ERS+97	Thomas Erlebach , Peter Rossmanith , Hans Stadtherr , Angelika Steger , Thomas Zeugmann, Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries, Proceedings of the 8th International Conference on Algorithmic Learning Theory, p.260-276, October 06-08, 1997
	Go167	E.M. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
	JS97	Sanjay Jain , Arun Sharma, Elementary formal systems, intrinsic complexity, and procrastination, Information and Computation, v.132 n.1, p.65-84, Jan. 10, 1997 [doi>10.1006/inco.1996.2614]
	JSSY95	Tao Jiang , Arto Salomaa , Kai Salomaa , Sheng Yu, Decision problems for patterns, Journal of Computer and System Sciences, v.50 n.1, p.53-63, Feb. 1995 [doi>10.1006/jcss.1995.1006]
	KP89	Michael Kearns , Leonard Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proceedings of the second annual workshop on Computational learning theory, p.57-71, December 1989, Santa Cruz, California, United States
	LW91	Steffen Lange , Rolf Wiehagen, Polynomial-time inference of arbitrary pattern languages, New Generation Computing, v.8 n.4, p.361-370, 1991 [doi>10.1007/BF03037093]
	Mar88	Assaf Marron, Learning pattern languages from a single initial example and from queries, Proceedings of the first annual workshop on Computational learning theory, p.345-358, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	Mit97	A. Mitchell. The learnability of nontrivial subsets of the extended pattern languages, July 1997. Honours thesis available from www.cse.unsw.edu.au/-andrewm/thesi s.ps.
	Nix83	R.P. Nix. Editing by example. Technical Report Research Report 280, Department of Computer Science, Yale University, 1983.
	OSW86	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
	Sch90	Robert E. Schapire, Pattern languages are not learnable, Proceedings of the third annual workshop on Computational learning theory, p.122-129, August 06-08, 1990, Rochester, New York, United States
	Shi82a	Takeshi Shinohara, Polynomial Time Inference of Extended Regular Pattern Languages, Proceedings of RIMS Symposium on Software Science and Engineering, p.115-127, January 1983
	Shi82b	T. Shinohara. Polynomial time inference of pattern languages and its applications. In Proc. of the 7th IBM Symposium on Mathematical Foundations of Computer Science, pages 191-209, 1982.
	Shi83	T. Stxinohara. Inferring unions of two pattern languages. Bulletin of lnformatics and Cybernetics, 20:83-88., 1983.
	Wri89	Keith Wright, Identification of unions of languages drawn from an identifiable class, Proceedings of the second annual workshop on Computational learning theory, p.328-333, December 1989, Santa Cruz, California, United States
	WZ94	R. Wiehagen and T. Zeugmann. Ignoring data may be the only way to learn efficiently. Journal of Experimental and Theoretical Artificial Intelligence, 6:131-144, 1994.

CITED BY 7

	Sally A. Goldman , Stephen S. Kwek, On learning unions of pattern languages and tree patterns in the mistake bound model, Theoretical Computer Science, v.288 n.2, p.237-254, 16 October 2002
	Daniel Reidenbach, A non-learnable class of E-pattern languages, Theoretical Computer Science, v.350 n.1, p.91-102, 18 January 2006
	Steffen Lange , Thomas Zeugmann , Sandra Zilles, Learning indexed families of recursive languages from positive data: A survey, Theoretical Computer Science, v.397 n.1-3, p.194-232, May, 2008
	Jochen Nessel , Steffen Lange, Learning erasing pattern languages with queries, Theoretical Computer Science, v.348 n.1, p.41-57, 2 December 2005
	Daniel Reidenbach, Discontinuities in pattern inference, Theoretical Computer Science, v.397 n.1-3, p.166-193, May, 2008
	Yen Kaow Ng , Takeshi Shinohara, Developments from enquiries into the learnability of the pattern languages from positive data, Theoretical Computer Science, v.397 n.1-3, p.150-165, May, 2008
	Dominik D. Freydenberger , Daniel Reidenbach, The unambiguity of segmented morphisms, Discrete Applied Mathematics, v.157 n.14, p.3055-3068, July, 2009