Declarative encodings of acyclicity properties
- Many knowledge representation tasks involve trees or similar structures as abstract datatypes. However, devising compact and efficient declarative representations of such structural properties is non-obvious and can be challenging indeed. In this article, we take a number of acyclicity properties into consideration and investigate various logic-based approaches to encode them. We use answer set programming as the primary representation language but also consider mappings to related formalisms, such as propositional logic, difference logic and linear programming. We study the compactness of encodings and the resulting computational performance on benchmarks involving acyclic or tree structures.
| Author details: | Martin GebserORCiDGND, Tomi JanhunenORCiD, Jussi RintanenORCiD |
|---|---|
| DOI: | https://doi.org/10.1093/logcom/exv063 |
| ISSN: | 0955-792X |
| ISSN: | 1465-363X |
| Title of parent work (English): | Journal of logic and computation |
| Publisher: | Oxford Univ. Press |
| Place of publishing: | Eynsham, Oxford |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2015/09/08 |
| Publication year: | 2020 |
| Release date: | 2023/10/06 |
| Tag: | acyclicity properties; answer set programming; logic-based modeling; satisfiability |
| Volume: | 30 |
| Issue: | 4 |
| Number of pages: | 30 |
| First page: | 923 |
| Last Page: | 952 |
| Funding institution: | Finnish Centre of Excellence in Computational Inference Research (COIN); - Academy of Finland [251170] |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC classification: | 6 Technik, Medizin, angewandte Wissenschaften / 60 Technik / 600 Technik, Technologie |
| Peer review: | Referiert |
| Publishing method: | Open Access / Green Open-Access |
