Declarative encodings of acyclicity properties

Research output: Contribution to journalArticleScientificpeer-review

128 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)923-952
Number of pages30
JournalJournal of Logic and Computation
Volume30
Issue number4
Early online date10 Sep 2015
DOIs
Publication statusPublished - 5 Jun 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • acyclicity properties
  • logic-based modeling
  • answer set programming
  • satisfiability

Fingerprint

Dive into the research topics of 'Declarative encodings of acyclicity properties'. Together they form a unique fingerprint.

Cite this