{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:34Z","timestamp":1761611254684,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P17212P21840"],"award-info":[{"award-number":["P17212P21840"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST-2003-506779"],"award-info":[{"award-number":["IST-2003-506779"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We present the class FDNC of logic programs that allows for function symbols (F), disjunction (D), nonmonotonic negation under the answer set semantics (N), and constraints (C), while still retaining the decidability of the standard reasoning tasks. Thanks to these features, FDNC programs are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, and which allows also for common-sense reasoning in this context. This is evidenced, for instance, by tasks in reasoning about actions and planning: brave and open queries over FDNC programs capture the well-known problems of plan existence and secure (conformant) plan existence, respectively, in transition-based actions domains. As for reasoning from FDNC programs, we show that consistency checking and brave\/cautious reasoning tasks are ExpTime-complete in general, but have lower complexity under syntactic restrictions that give rise to a family of program classes. Furthermore, we also determine the complexity of open queries (i.e., with answer variables), for which deciding non-empty answers is shown to be ExpSpace -complete under cautious entailment. Furthermore, we present algorithms for all reasoning tasks that are worst-case optimal. The majority of them resorts to a finite representation of the stable models of an FDNC program that employs maximal founded sets of knots, which are labeled trees of depth at most 1 from which each stable model can be reconstructed. Due to this property, reasoning over FDNC programs can in many cases be reduced to reasoning from knots. Once the knot-representation for a program is derived (which can be done off-line), several reasoning tasks are not more expensive than in the function-free case, and some are even feasible in polynomial time. This knowledge compilation technique paves the way to potentially more efficient online reasoning methods not only for FDNC, but also for other formalisms.<\/jats:p>","DOI":"10.1145\/1656242.1656249","type":"journal-article","created":{"date-parts":[[2010,1,19]],"date-time":"2010-01-19T20:14:58Z","timestamp":1263932098000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["FDNC"],"prefix":"10.1145","volume":"11","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]},{"given":"Mantas","family":"\u0160imkus","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2010,1,22]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Alsa\u00e7 G. and Baral C. 2001. Reasoning in description logics using declarative logic programming. Tech. rep. Dept. Computer Science and Engineering Arizona State University.  Alsa\u00e7 G. and Baral C. 2001. Reasoning in description logics using declarative logic programming. Tech. rep. Dept. Computer Science and Engineering Arizona State University."},{"key":"e_1_2_2_2_1","first-page":"3","article-title":"The generalised completeness of Horn predicate logics as programming language","volume":"4","author":"Andreka H.","year":"1978","journal-title":"Acta Cybernet."},{"key":"e_1_2_2_3_1","unstructured":"Asparagus. Homepage (since 2005). http:\/\/asparagus.cs.uni-potsdam.de\/.  Asparagus. Homepage (since 2005). http:\/\/asparagus.cs.uni-potsdam.de\/."},{"volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05)","author":"Baader F.","key":"e_1_2_2_4_1"},{"key":"e_1_2_2_5_1","unstructured":"Baader F. Calvanese D. McGuinness D. Nardi D. and Patel-Schneider P. F. Eds. 2003. The Description Logic Handbook: Theory Implementation and Applications. Cambridge University Press Cambridge MA.   Baader F. Calvanese D. McGuinness D. Nardi D. and Patel-Schneider P. F. Eds. 2003. The Description Logic Handbook: Theory Implementation and Applications. Cambridge University Press Cambridge MA."},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Baral C. 2002. Knowledge Representation Reasoning and Declarative Problem Solving. Cambridge University Press Cambridge MA.   Baral C. 2002. Knowledge Representation Reasoning and Declarative Problem Solving. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511543357"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the 23rd International Conference on Logic Programming (ICLP","volume":"4670","author":"Baselice S.","year":"2007"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.02.001"},{"key":"e_1_2_2_9_1","first-page":"3","article-title":"A survey on knowledge compilation","volume":"10","author":"Cadoli M.","year":"1997","journal-title":"AI Comm."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)00030-A"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/151634.151635"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622810.1622817"},{"volume":"1348","volume-title":"Proceedings of the European Conference on Planning 1997 (ECP-97)","author":"Dimopoulos Y.","key":"e_1_2_2_14_1"},{"volume":"1265","volume-title":"Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97)","author":"Dix J.","key":"e_1_2_2_15_1"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00367-3"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/976706.976708"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)00027-7"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05)","author":"Eiter T.","key":"e_1_2_2_20_1"},{"volume":"1265","volume-title":"Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97)","author":"Eiter T.","key":"e_1_2_2_21_1"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_50"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Gelfond M. and Lifschitz V. 1991. Classical negation in logic programs and disjunctive databases. New Generat. Comput. 9 3\/4 365--386.  Gelfond M. and Lifschitz V. 1991. Classical negation in logic programs and disjunctive databases. New Generat. Comput. 9 3\/4 365--386.","DOI":"10.1007\/BF03037169"},{"volume-title":"Proceedings of the Joint International Conference and Symposium on Logic Programming (JICSLP-92)","author":"Gelfond M.","key":"e_1_2_2_24_1"},{"volume-title":"Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98)","author":"Giunchiglia E.","key":"e_1_2_2_25_1"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90043-9"},{"volume":"1809","volume-title":"Proceedings of the 5th European Conference Planning (ECP-99)","author":"Haslum P.","key":"e_1_2_2_27_1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Herbrand J. 1971. Logical Writings. Harvard University Press.  Herbrand J. 1971. Logical Writings. Harvard University Press.","DOI":"10.1007\/978-94-010-3072-4"},{"key":"e_1_2_2_29_1","unstructured":"Heymans S. 2006. Decidable open answer set programming. Ph.D. dissertation Theoretical Computer Science Lab Department of Computer Science Vrije Universiteit Brussel Brussels Belgium.  Heymans S. 2006. Decidable open answer set programming. Ph.D. dissertation Theoretical Computer Science Lab Department of Computer Science Vrije Universiteit Brussel Brussels Belgium."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11431053_27"},{"volume":"78","volume-title":"Proceedings of the Workshop on Answer Set Programming (ASP-2003)","author":"Heymans S.","key":"e_1_2_2_31_1"},{"volume-title":"Proceedings KR-2004","author":"Hustadt U.","key":"e_1_2_2_32_1"},{"key":"e_1_2_2_33_1","first-page":"251","article-title":"A survey of decidable first-order fragments and description logics","volume":"1","author":"Hustadt U.","year":"2004","journal-title":"J. Relat. Meth. Comput. Sci."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(87)90014-8"},{"volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence.","author":"Kaelbling L. P.","key":"e_1_2_2_35_1"},{"key":"e_1_2_2_36_1","first-page":"159","article-title":"Foundations for the situation calculus","volume":"2","author":"Levesque H. J.","year":"1998","journal-title":"Electronic Trans. Artif. Intell."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/341176.341179"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00186-8"},{"volume-title":"Proceedings of the 11th International Conference on Logic Programming (ICLP-94)","author":"Lifschitz V.","key":"e_1_2_2_39_1"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001777"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Marek V. W. and Truszczy\u0144ski M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm -- A25-Year Perspective Springer-Verlag Berlin Germany 375--398.  Marek V. W. and Truszczy\u0144ski M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm -- A25-Year Perspective Springer-Verlag Berlin Germany 375--398.","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90069-C"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(14)80008-3"},{"volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07)","year":"1991","author":"Morales A. R.","key":"e_1_2_2_44_1"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242681"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"volume":"1265","volume-title":"Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97)","author":"Niemel\u00e4 I.","key":"e_1_2_2_47_1"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91)","year":"1991","author":"Schild K.","key":"e_1_2_2_49_1"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183279"},{"volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-05)","author":"Son T. C.","key":"e_1_2_2_51_1"},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-04)","volume":"2923","author":"Swift T.","year":"2004"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/646400.688912"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002948"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1656242.1656249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1656242.1656249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:18Z","timestamp":1750250478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1656242.1656249"}},"subtitle":["Decidable nonmonotonic disjunctive logic programs with function symbols"],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1145\/1656242.1656249"],"URL":"https:\/\/doi.org\/10.1145\/1656242.1656249","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,1]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}