{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T16:13:16Z","timestamp":1771517596909,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T00:00:00Z","timestamp":1441670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["251170"],"award-info":[{"award-number":["251170"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/logcom\/exv063","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T13:10:16Z","timestamp":1494249016000},"page":"923-952","source":"Crossref","is-referenced-by-count":3,"title":["Declarative encodings of acyclicity properties"],"prefix":"10.1093","volume":"30","author":[{"given":"Martin","family":"Gebser","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, FI-00076 Aalto, Finland; University of Potsdam, Germany"}]},{"given":"Tomi","family":"Janhunen","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, FI-00076 Aalto, Finland"}]},{"given":"Jussi","family":"Rintanen","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, FI-00076 Aalto, Finland; Griffith University, Brisbane, Australia"}]}],"member":"286","published-online":{"date-parts":[[2015,9,8]]},"reference":[{"key":"2020062122333699700_B1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/B978-0-934613-40-8.50006-3","article-title":"Towards a theory of declarative knowledge","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"Apt","year":"1988"},{"key":"2020062122333699700_B2","volume-title":"Handbook of Satisfiability. Vol. 185 of Frontiers in Artificial Intelligence and Applications","author":"Biere","year":"2009"},{"key":"2020062122333699700_B3"},{"key":"2020062122333699700_B4"},{"key":"2020062122333699700_B5"},{"key":"2020062122333699700_B6","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/2043174.2043195","article-title":"Answer set programming at a glance","volume":"54","author":"Brewka","year":"2011","journal-title":"Communications of the ACM"},{"key":"2020062122333699700_B7","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/s10817-007-9082-1","article-title":"Inferring phylogenetic trees using answer set programming","volume":"39","author":"Brooks","year":"2007","journal-title":"Journal of Automated Reasoning"},{"key":"2020062122333699700_B8"},{"key":"2020062122333699700_B9"},{"key":"2020062122333699700_B10"},{"key":"2020062122333699700_B11"},{"key":"2020062122333699700_B12","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0304-3975(03)00221-4","article-title":"Enumerating and characterizing the perfect elimination orderings of a chordal graph","volume":"307","author":"Chandran","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"2020062122333699700_B13","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-1-4684-3384-5_11","article-title":"Negation as failure","volume-title":"Logic and Data Bases","author":"Clark","year":"1978"},{"key":"2020062122333699700_B14"},{"key":"2020062122333699700_B15"},{"key":"2020062122333699700_B16"},{"key":"2020062122333699700_B17","article-title":"Linear Programming and Extensions","volume-title":"Princeton Landmarks in Mathematics and Physics","author":"Dantzig","year":"1963"},{"key":"2020062122333699700_B18","volume-title":"Graph Theory. Vol. 173 of Graduate Texts in Mathematics","author":"Diestel","year":"2010"},{"key":"2020062122333699700_B19","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1017\/S1471068403001765","article-title":"Tight logic programs","volume":"3","author":"Erdem","year":"2003","journal-title":"Theory and Practice of Logic Programming"},{"key":"2020062122333699700_B20"},{"key":"2020062122333699700_B21"},{"key":"2020062122333699700_B22"},{"key":"2020062122333699700_B23"},{"key":"2020062122333699700_B24"},{"key":"2020062122333699700_B25","author":"Gebser","year":"2010","journal-title":"A user's guide to gringo, clasp, clingo, and iclingo"},{"key":"2020062122333699700_B26","doi-asserted-by":"crossref","DOI":"10.2200\/S00457ED1V01Y201211AIM019","article-title":"Answer Set Solving in Practice","volume-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning","author":"Gebser","year":"2012"},{"key":"2020062122333699700_B27","doi-asserted-by":"crossref","first-page":"1633","DOI":"10.1111\/j.1365-2699.2012.02723.x","article-title":"Convergence in the distribution patterns of Europe's plants and mammals is due to environmental forcing","volume":"39","author":"Heikinheimo","year":"2012","journal-title":"Journal of Biogeography"},{"key":"2020062122333699700_B28"},{"key":"2020062122333699700_B29"},{"key":"2020062122333699700_B30","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-20832-4_8","article-title":"Compact translations of non-disjunctive answer set programs to propositional clauses","volume-title":"Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday. Vol. 6565 of Lecture Notes in Computer Science","author":"Janhunen","year":"2011"},{"key":"2020062122333699700_B31"},{"key":"2020062122333699700_B32"},{"key":"2020062122333699700_B33"},{"key":"2020062122333699700_B34"},{"key":"2020062122333699700_B35"},{"key":"2020062122333699700_B36","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s10472-009-9118-9","article-title":"Stable models and difference logic","volume":"53","author":"Niemel\u00e4","year":"2008","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2020062122333699700_B37"},{"key":"2020062122333699700_B38","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(02)00187-X","article-title":"Extending and implementing the stable model semantics","volume":"138","author":"Simons","year":"2002","journal-title":"Artificial Intelligence"},{"key":"2020062122333699700_B39"},{"key":"2020062122333699700_B40"},{"key":"2020062122333699700_B41"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/4\/923\/33410449\/exv063.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/4\/923\/33410449\/exv063.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:33:47Z","timestamp":1592793227000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/4\/923\/2917838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,8]]},"references-count":41,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2015,9,8]]},"published-print":{"date-parts":[[2020,6,5]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exv063","relation":{},"ISSN":["1465-363X","0955-792X"],"issn-type":[{"value":"1465-363X","type":"electronic"},{"value":"0955-792X","type":"print"}],"subject":[],"published-other":{"date-parts":[[2020,6]]},"published":{"date-parts":[[2015,9,8]]}}}