Polynomially bounded forgetting

Yi Zhou

    Research output: Chapter in Book / Conference PaperConference Paperpeer-review

    Abstract

    ![CDATA[Forgetting is one of the most important concepts in logic based problem solving, both from a theoretical and a practical point of view. However, the size of the forgetting result is exponential in worst case. To address this issue, we consider the problem of polynomially bounded forgetting, i.e., when the size of the forgetting result can be expressed polynomially.We coin the notion of polynomially bounded forgetting and distinguish several different levels. We then show that forgetting a set of variables under a polynomial bound can be reduced to forgetting a single one. However, checking variable polynomially bounded forgetting is ΣP 2 complete. Hence, we identify some sufficient conditions for this problem. Finally, we consider polynomially bounded forgetting in CNF formulas.]]
    Original languageEnglish
    Title of host publicationPRICAI 2014: Trends in Artificial Intelligence: Proceedings of the 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, Qld, Australia, December 1-5, 2014
    PublisherSpringer
    Pages422-434
    Number of pages13
    ISBN (Print)9783319135595
    DOIs
    Publication statusPublished - 2014
    EventPacific Rim International Conference on Artificial Intelligence -
    Duration: 13 Sept 2019 → …

    Publication series

    Name
    ISSN (Print)0302-9743

    Conference

    ConferencePacific Rim International Conference on Artificial Intelligence
    Period13/09/19 → …

    Fingerprint

    Dive into the research topics of 'Polynomially bounded forgetting'. Together they form a unique fingerprint.

    Cite this