Learning one-variable pattern languages in linear average time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning one-variable pattern languages in linear average time

Full text

Pdf (1.47 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: 198 - 208

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Rüdiger Reischuk	Med. Universität zu Lübeck, Institut für Theoretische Informatik, Wallstraβe 40, 23560 Lübeck, Germany
Thomas Zeugmann	Department of Informatics, Kyushu University, Kasuga 816-8580, Japan

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): 4, Downloads (12 Months): 16, Citation Count: 5

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.279984 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	D. Angluin. Finding Patterns Common to a Set of Strings, Journal of Computer and System Sciences 21:46-62, 1980.
	2	Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
	3	T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Efficient learning of onevariable pattern languages from positive data, DOI- TR-128, Kyushu University, Fukuoka, Japan, 1996.
	4	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
	5	E. Gold. Language identification in the limit, Information & Control 10:447-474, 1967.
	6	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
	7	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]
	8	Steffen Lange , Thomas Zeugmann, Incremental learning from positive data, Journal of Computer and System Sciences, v.53 n.1, p.88-103, Aug. 1996 [doi>10.1006/jcss.1996.0051]
	9	Stephen Muggleton, Bayesian inductive logic programming, Proceedings of the seventh annual conference on Computational learning theory, p.3-11, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.178095]
	10	Leonard Pitt, Inductive Inference, DFAs, and Computational Complexity, Proceedings of the International Workshop on Analogical and Inductive Inference, p.18-44, October 01-06, 1989
	11	R. Reischuk and T. Zeugmann. Learning One- Variable Pattern Languages in Linear Average Time, DOI-TR-140, Kyushu University: Fukuoka, Japan, 1997. http://www.i.kyushu-u.ac.jp/thomas/tr.html
	12	A. Salomaa. Patterns, (The Formal Language Theory Colunm), EATCS Bulletin 54:46-62, 1994.
	13	A. Salomaa. Return to patterns, (The Formal Language Theory Column), EATCS Bulletin 55:144- 157, 1994.
	14	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
	15	Takeshi Shinohara , Setsuo Arikawa, Pattern Inference, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.259-291, January 1995
	16	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.
	17	Thomas Zeugmann, Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.117-145, 1998 [doi>10.1023/A:1018964207937]

CITED BY 5

	Peter Rossmanith , Thomas Zeugmann, Stochastic Finite Learning of the Pattern Languages, Machine Learning, v.44 n.1-2, p.67-91, July-August 2001
	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
	Thomas Zeugmann, From learning in the limit to stochastic finite learning, Theoretical Computer Science, v.364 n.1, p.77-97, 2 November 2006
	John Case , Sanjay Jain , Rüdiger Reischuk , Frank Stephan , Thomas Zeugmann, Learning a subclass of regular patterns in polynomial time, Theoretical Computer Science, v.364 n.1, p.115-131, 2 November 2006