Efficient identification of regular expressions from representative examples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient identification of regular expressions from representative examples

Full text

Pdf (813 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: 236 - 242

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Alvis Brāzma

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): 15, Downloads (12 Months): 43, 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/168304.168340 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	Dana Angluin, Equivalence queries and approximate fingerprints, Proceedings of the second annual workshop on Computational learning theory, p.134-145, December 1989, Santa Cruz, California, United States
	2	D.Angluin. A note on the number of queries to identify regular languages. Information and Computation, 51:76-87, 1981.
	3	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	4	J. M. Barzdin , G. J. Barzdin, Rapid construction of algebraic axioms from samples, Theoretical Computer Science, v.90 n.1, p.199-208, Nov. 1991 [doi>10.1016/0304-3975(91)90307-N]
	5	J.M.Barzdin. Some rules of inductwe znference and thew use for program synthes~s. In proceedings of IFIP, 1983, North Holland, 333-338.
	6	Alvis Brazma, Inductive Synthesis of Dot Expressions, Baltic Computer Science, Selected Papers, p.156-212, January 1991
	7	Alvis Brāzma, Learning a subclass of regular expressions by recognizing periodic repetitions, Proceedings of the Fourth Scandinavian Conference on Artificial intelligence---93, p.137-146, June 1993, Stockholm, Sweden
	8	W.W.Cohen. Learmng Restrzcted Classes of Regular Languages Uszng Loop Induction. Technical Memorandum, AT& T Bell Laboratories, Dec. 12, 1990.
	9	R.Freivalds, E.Kinber, R.Wiehagen. Inductwe ~nference from good examples. Lecture Notes in Artificial Intelligence, 397, 1-18, 1989.
	10	E.M.Gold. Language ~dentzficatwn ~n the hm~t. Inform. contr., 10:447-474, 1967.
	11	Efim B. Kinber, Learning A Class of Regular Expressions via Restricted Subset Queries, Proceedings of the International Workshop on Analogical and Inductive Inference, p.232-243, October 05-09, 1992
	12	L.Pitt. Inductive Inference, DFAs, and Computatwnal Complexzty. Lecture Notes in Artificial Intelligence, 397:18-44, Springer-Verlag, 1989
	13	N.Tanida, T.Yokomori. Polynomial-tzme identificatwn of strictly regular languages zn the hmit, IEICE Trans. Inf. &; Syst., V E75-D, 1992, 125-132.
	14	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	15	Rolf Wiehagen, From Inductive Inference to Algorithmic Learning Theory, Proceedings of the Third Workshop on Algorithmic Learning Theory, p.13-24, October 20-22, 1992

CITED BY 7

	Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: a system for extracting document type descriptors from XML documents, ACM SIGMOD Record, v.29 n.2, p.165-176, June 2000
	Jun-Ki Min , Jae-Yong Ahn , Chin-Wan Chung, Efficient extraction of schemas for XML documents, Information Processing Letters, v.85 n.1, p.7-12, 16 January 2003
	Geert Jan Bex , Frank Neven , Thomas Schwentick , Karl Tuyls, Inference of concise DTDs from XML data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: Learning Document Type Descriptors from XML Document Collections, Data Mining and Knowledge Discovery, v.7 n.1, p.23-56, January 2003
	A. V. Leonov , R. R. Khusnutdinov, Study and Development of the DTD Generation System for XML Documents, Programming and Computing Software, v.31 n.4, p.197-210, July 2005
	Geert Jan Bex , Wouter Gelade , Frank Neven , Stijn Vansummeren, Learning deterministic regular expressions for the inference of schemas from XML data, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Henning Fernau, Algorithms for learning regular expressions from positive data, Information and Computation, v.207 n.4, p.521-541, April, 2009