Conference item
On the complexity of inductively learning guarded clauses
- Abstract:
- We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the Σ P 2 -complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to k-guarded clauses for constant k.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 270.9KB, Terms of use)
-
- Publisher copy:
- 10.1609/aaai.v36i5.20500
Authors
- Publisher:
- Association for the Advancement of Artificial Intelligence
- Host title:
- Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022)
- Volume:
- 36
- Issue:
- 5
- Pages:
- 5600-5607
- Publication date:
- 2022-06-28
- Acceptance date:
- 2021-12-01
- Event title:
- 36th AAAI Conference on Artificial Intelligence (AAAI 2022)
- Event location:
- Online
- Event website:
- https://aaai.org/Conferences/AAAI-22/
- Event start date:
- 2022-02-22
- Event end date:
- 2022-03-01
- DOI:
- Language:
-
English
- Keywords:
- Pubs id:
-
1243815
- Local pid:
-
pubs:1243815
- Deposit date:
-
2022-03-17
Terms of use
- Copyright holder:
- Association for the Advancement of Artificial Intelligence
- Copyright date:
- 2022
- Rights statement:
- © 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
- Notes:
- This paper will be presented at the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), 22nd February - 1st March 2022. This is the accepted manuscript version of the article. The final version is available online from the Proceedings of AAAI at: https://doi.org/10.1609/aaai.v36i5.20500
If you are the owner of this record, you can report an update to it here: Report update to this record