[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/238061.238066acmconferencesArticle/Chapter ViewAbstractPublication PagescoltConference Proceedingsconference-collections
Article
Free access

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

Published: 01 January 1996 Publication History
First page of PDF

References

[1]
Dana Angluin. Learning regular sets from queries and counterexamples. Information and Control, 75:87-106, 1987.
[2]
A. Biermann. The inference of regular lisp programs from examples. IEEE Transactions on Systems, Man and Cyberneizcs, 8(8), 1978.
[3]
R.Boppana and M. Sipser. The complexity of finite functions. In Handbook of Theoretical Computer Science, pages 758-804. Elsevier, 1990.
[4]
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.
[5]
William W. Cohen and Haym Hirsh. Learnability of description logics. In Proceedings of the Fifth Annual Workshop on Computational Learnzng Theory, Pittsburgh, Pennsylvania. 1992. ACM Press.
[6]
William W. Cohen and Haym Hirsh. The learnability of description logics with equality constraints. Machine Learning, 17(2/3). 1994.
[7]
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.
[8]
William W. Cohen and Haym Hirsh. Corrigendum for "learnability of description logics". In Proceedings of the E~ghth Annual Workshop on Computational Learnzng Theory, Santa Cruz. California, 1995. ACM Press.
[9]
William W.cohen and C. David Page Jr. Polynomial learnability and inductive logic programming: Methods and results. New Generation Computzng, 13(3), 1995.
[10]
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.
[11]
Allen Cypher, editor. Watch what I do: Programming by demonstratzon. The MIT Press. Cambridge, Massachusetts, 1993.
[12]
Sago D~,eroski, Stephen Muggleton, and Stuart Russell. Pac-learnability of determinate logic programs. In Proceedings of the 1992 Workshop on Computational Learmng Theory, Pittsburgh. Pennsylvania, 1992.
[13]
Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie. Efficient learning of typical finite automata from random walks. In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 315-324. ACM Press, 1993.
[14]
Micheal Kearns and Les Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In ~1th Annual Symposium on the Theory of Computzng. ACM Press. 1989.
[15]
JSrg-Uwe Kietz. Some computational lower bounds for the computational complexity of inductive logic programming. In Proceedings of the 1993 European Conference on Machine Learning, Vienna, Austria, 1993.
[16]
J. W. Lloyd. Foundations of Logic Programmzng: Second Edition. Springer-Verlag, 1987.
[17]
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.
[18]
Stephen Muggleton and Cao Feng. Efficient induction of logic programs. In Inductzve Logic Programming. Academic Press, 1992.
[19]
C. D. Page and A. M. Frisch. Generalization and learnability: A study of constrained atoms. In Inductive Logic Programming. Academic Press, 1992.
[20]
L. Pitt and M. Frazier. Classic learning. In Proceedzngs of the Seventh Annual ACM Conference on Computational Learning Theory, New Brunswick, N J, 1994. ACM Press.
[21]
Leonard Pitt and Manfred Warmuth. Prediction-preserving reducibility. Journal of Computer and System Sciences, 41:430-467, 1990.
[22]
Phillip D. Summers. A methodology for LISP program construction from examples. Journal of the Association for Computing Machinery, 24(1):161-175, January 1977.
[23]
L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11), November 1984.
[24]
W. A. Woods and J. G. Schmolze. The KL-ONE family. Computers And Mathematics With Apphcatzons, 23(2-5), March 1992.

Cited By

View all

Index Terms

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

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    COLT '96: Proceedings of the ninth annual conference on Computational learning theory
    January 1996
    344 pages
    ISBN:0897918118
    DOI:10.1145/238061
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 January 1996

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    9COLT96
    Sponsor:
    9COLT96: 9th Annual Conference on Computational Learning Theory
    June 28 - July 1, 1996
    Desenzano del Garda, Italy

    Acceptance Rates

    Overall Acceptance Rate 35 of 71 submissions, 49%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)32
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 14 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)On the non-efficient PAC learnability of conjunctive queriesInformation Processing Letters10.1016/j.ipl.2023.106431183(106431)Online publication date: Jan-2024
    • (2005)Prediction-hardness of acyclic conjunctive queriesTheoretical Computer Science10.1016/j.tcs.2005.09.006348:1(84-94)Online publication date: 2-Dec-2005
    • (2001)On the Hardness of Learning Acyclic Conjunctive QueriesAlgorithmic Learning Theory10.1007/3-540-40992-0_18(238-251)Online publication date: 19-Oct-2001
    • (1998)Learning atomic formulas with prescribed propertiesProceedings of the eleventh annual conference on Computational learning theory10.1145/279943.279978(166-174)Online publication date: 24-Jul-1998
    • (1997)Learning logic programs by using the product homomorphism methodProceedings of the tenth annual conference on Computational learning theory10.1145/267460.267468(10-20)Online publication date: 1-Jul-1997

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media