The dual DFA learning problem (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The dual DFA learning problem (extended abstract): hardness results for programming by demonstration and learning first-order representations

Full text

Pdf (1.25 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: 29 - 40

Year of Publication: 1996

ISBN:0-89791-811-8

Author

William W. Cohen

AT&T Laboratories, 600 Mountain Avenue, Murray Hill, NJ

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): 3, Downloads (12 Months): 11, 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.238066 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.

	Angluin, 1987	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]
	Biermann, 1978	A. Biermann. The inference of regular lisp programs from examples. IEEE Transactions on Systems, Man and Cyberneizcs, 8(8), 1978.
	Boppana and Sipser, 1990	Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Borgida, 1992	Alex Borgida. Description logics are not just for the flightless-birds: a new look at the utility and foundations of description logics. Technical Report DCS-TR-295. Rutgers University Department of Computer Science, 1992.
	Cohen and Hirsh, 1992	William W. Cohen , Haym Hirsh, Learnability of description logics, Proceedings of the fifth annual workshop on Computational learning theory, p.116-127, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130398]
	Cohen and Hirsh, 1994a	William W. Cohen , Haym Hirsh, The Learnability of Description Logics with Equality Constraints, Machine Learning, v.17 n.2-3, p.169-199, Nov./Dec. 1994 [doi>10.1007/BF00993470]
	Cohen and Hirsh, 1994b	William W. Cohen and Haym Hirsh. Learning the CLASSIC description logic: Theoretical and experimental results. In Prznciples of Knowledge Represeniaiwn and Reasomng: Proceedings of the Fourth Internatwnal Conference (KRgd). Morgan Kaufmann, 1994.
	Cohen and Hirsh, 1995	William W. Cohen , Haym Hirsh, Corrigendum for "learnability of description logics", Proceedings of the eighth annual conference on Computational learning theory, p.463, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.372773]
	Cohen and Jr, 1995	William W.cohen and C. David Page Jr. Polynomial learnability and inductive logic programming: Methods and results. New Generation Computzng, 13(3), 1995.
	Cohen, 1993	William W. Cohen. Cryptographic limitations on learning one-clause logic programs. In Proceedzngs of the Tenth Natwnal Conference on Artificial Intelhgence, Washington, D.C., 1993.
	Cypher, 1993	Allen Cypher , Daniel C. Halbert , David Kurlander , Henry Lieberman , David Maulsby , Brad A. Myers , Alan Turransky, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
	Dzeroski et al., 1992	Sašo Džeroski , Stephen Muggleton , Stuart Russell, PAC-learnability of determinate logic programs, Proceedings of the fifth annual workshop on Computational learning theory, p.128-135, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130399]
	Freund et al., 1993	Yoav Freund , Michael Kearns , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, Efficient learning of typical finite automata from random walks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.315-324, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167191]
	Kearns and Valiant, 1989	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	Kietz, 1993	Jörg-Uwe Kietz, Some Lower Bounds for the Computational Complexity of Inductive Logic Programming, Proceedings of the European Conference on Machine Learning, p.115-123, April 05-07, 1993
	Lloyd, 1987	J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	MacGregor, 1991	R. M. MacGregor. The evolving technology of classification-based knowledge representation systems. In John Sowa, editor, Principles of semantzc networks: exploratzons zn the representation of knowledge. Morgan Kaufmann, 1991.
	Muggleton and Feng, 1992	Stephen Muggleton and Cao Feng. Efficient induction of logic programs. In Inductzve Logic Programming. Academic Press, 1992.
	Page and Frisch, 1992	C. D. Page and A. M. Frisch. Generalization and learnability: A study of constrained atoms. In Inductive Logic Programming. Academic Press, 1992.
	Pitt and Frazier, 1994	Michael Frazier , Leonard Pitt, CLASSIC learning, Proceedings of the seventh annual conference on Computational learning theory, p.23-34, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.174994]
	Pitt and Warmuth, 1990	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	Summers, 1977	Phillip D. Summers, A Methodology for LISP Program Construction from Examples, Journal of the ACM (JACM), v.24 n.1, p.161-175, Jan. 1977 [doi>10.1145/321992.322002]
	Valiant, 1984	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]
	Woods and Schmolze, 1992	W. A. Woods and J. G. Schmolze. The KL-ONE family. Computers And Mathematics With Apphcatzons, 23(2-5), March 1992.

CITED BY 3

	Tamás Horváth , Robert H. Sloan , György Turán, Learning logic programs by using the product homomorphism method, Proceedings of the tenth annual conference on Computational learning theory, p.10-20, July 06-09, 1997, Nashville, Tennessee, United States
	Kouichi Hirata, Prediction-hardness of acyclic conjunctive queries, Theoretical Computer Science, v.348 n.1, p.84-94, 2 December 2005
	Irene Tsapara , György Turán, Learning atomic formulas with prescribed properties, Proceedings of the eleventh annual conference on Computational learning theory, p.166-174, July 24-26, 1998, Madison, Wisconsin, United States