Declarative encodings of acyclicity properties
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2020-06-05
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
30
Series
Journal of Logic and Computation, Volume 30, issue 4, pp. 923-952
Abstract
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.Description
Keywords
acyclicity properties, logic-based modeling, answer set programming, satisfiability
Other note
Citation
Gebser, M, Janhunen, T & Rintanen, J 2020, ' Declarative encodings of acyclicity properties ', Journal of Logic and Computation, vol. 30, no. 4, pp. 923-952 . https://doi.org/10.1093/logcom/exv063