{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:41:10Z","timestamp":1784198470327,"version":"3.55.0"},"reference-count":114,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T00:00:00Z","timestamp":1634860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"crossref","award":["RP\/R1\/201074"],"award-info":[{"award-number":["RP\/R1\/201074"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M025268\/1, EP\/R013667\/1, EP\/N510129\/1, and EP\/N015843\/1"],"award-info":[{"award-number":["EP\/M025268\/1, EP\/R013667\/1, EP\/N510129\/1, and EP\/N015843\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001961","name":"AXA Research Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001961","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            This work investigates the decidability and complexity of database query answering under guarded existential rules with nonmonotonic negation according to the classical stable model semantics. In this setting, existential quantification is interpreted via Skolem functions, and the unique name assumption is adopted. As a first result, we show the decidability of answering first-order queries based on such rules by a translation into the satisfiability problem for guarded second-order formulas having the tree-model property. To obtain precise complexity results for unions of conjunctive queries, we transform the original problem in polynomial time into an intermediate problem that is easier to analyze: query answering for guarded disjunctive existential rules with stratified negation. We obtain precise bounds for the general setting and for various restricted settings. We also consider extensions of the original formalism with negative constraints, keys, and the possibility of negated atoms in queries. Finally, we show how the above results can be used to provide decidability and complexity results for a natural adaptation of the stable model semantics to description logics such as\u00a0\n            <jats:italic>ELHI<\/jats:italic>\n            and the\n            <jats:italic>DL-Lite<\/jats:italic>\n            \u00a0family.\n          <\/jats:p>","DOI":"10.1145\/3447508","type":"journal-article","created":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T00:15:17Z","timestamp":1634948117000},"page":"1-87","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity"],"prefix":"10.1145","volume":"68","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"Hernich","sequence":"additional","affiliation":[{"name":"Amazon Web Services, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Clemens","family":"Kupke","sequence":"additional","affiliation":[{"name":"University of Strathclyde, Glasgow, Scotland, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Lukasiewicz","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40564-8_6"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000257"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034794"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745758"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/2669205"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594555"},{"key":"e_1_3_3_10_2","first-page":"364","volume-title":"Proceedings of the IJCAI","author":"Baader Franz","year":"2005","unstructured":"Franz Baader , Sebastian Brandt , and Carsten Lutz . 2005. Pushing the \\mathcal {EL} envelope. In Proceedings of the IJCAI . 364\u2013369."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-017-9563-9"},{"key":"e_1_3_3_12_2","first-page":"466","volume-title":"Proceedings of the KR","author":"Baget Jean-Fran\u00e7ois","year":"2010","unstructured":"Jean-Fran\u00e7ois Baget , Michel Lecl\u00e8re , and Marie-Laure Mugnier . 2010. Walking the decidability line for rules with existential variables. In Proceedings of the KR . 466\u2013476."},{"key":"e_1_3_3_13_2","first-page":"677","volume-title":"Proceedings of the IJCAI","author":"Baget Jean-Fran\u00e7ois","year":"2009","unstructured":"Jean-Fran\u00e7ois Baget , Michel Lecl\u00e8re , Marie-Laure Mugnier , and Eric Salvat . 2009. Extending decidable cases for rules with existential variables. In Proceedings of the IJCAI . 677\u2013682."},{"key":"e_1_3_3_14_2","first-page":"712","volume-title":"Proceedings of the IJCAI","author":"Baget Jean-Fran\u00e7ois","year":"2011","unstructured":"Jean-Fran\u00e7ois Baget , Marie-Laure Mugnier , Sebastian Rudolph , and Micha\u00ebl Thomazo . 2011. Walking the complexity lines for generalized guarded existential rules. In Proceedings of the IJCAI . 712\u2013717."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10843-2_7"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00856-7_1"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-73117-9_1"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213888"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319688"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322238"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210059"},{"key":"e_1_3_3_23_2","article-title":"Datalog: Bag semantics via set semantics","author":"Bertossi Leopoldo","year":"2018","unstructured":"Leopoldo Bertossi , Georg Gottlob , and Reinhard Pichler . 2018. Datalog: Bag semantics via set semantics. arXiv preprint arXiv:1803.06445 (2018).","journal-title":"arXiv preprint arXiv:1803.06445"},{"key":"e_1_3_3_24_2","first-page":"775","volume-title":"Proceedings of the IJCAI","author":"Bienvenu Meghyn","year":"2013","unstructured":"Meghyn Bienvenu and Riccardo Rosati . 2013. Tractable approximations of consistent query answering for robust ontology-based data access. In Proceedings of the IJCAI . 775\u2013781."},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-319-14726-0_8","volume-title":"Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation","author":"Bonatti Piero","year":"2015","unstructured":"Piero Bonatti , Marco Faella , Carsten Lutz , Luigi Sauro , and Frank Wolter . 2015. Decidability of circumscribed description logics revisited. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation . Springer, 112\u2013124."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.02.001"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.07.002"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.3233\/IA-2011-0009"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976736"},{"key":"e_1_3_3_30_2","first-page":"796","volume-title":"Proceedings of the IJCAI","author":"Bourhis Pierre","year":"2013","unstructured":"Pierre Bourhis , Michael Morak , and Andreas Pieris . 2013. The Impact of disjunction on query answering under guarded-based existential rules. In Proceedings of the IJCAI . 796\u2013802."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2004.07.023"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000169"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.27"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/2019470.2019475"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802488"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214049"},{"key":"e_1_3_3_42_2","volume-title":"Proceedings of the Datalog 2.0 2019 \u2014 3rd International Workshop on the Resurgence of Datalog in Academia and Industry","author":"Clearman Jack","year":"2019","unstructured":"Jack Clearman , Ruslan R. Fayzrakhmanov , Georg Gottlob , Yavor Nenov , St\u00e9phane Reissfelder , Emanuel Sallinger , and Evgeny Sherkhonov . 2019. Feature engineering and explainability with Vadalog: A recommender systems application. In Proceedings of the Datalog 2.0 2019 \u2014 3rd International Workshop on the Resurgence of Datalog in Academia and Industry ."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/2414243"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_3_3_46_2","first-page":"149","volume-title":"Proceedings of the PODS","author":"Deutsch Alin","year":"2008","unstructured":"Alin Deutsch , Alan Nash , and Jeff B. Remmel . 2008. The chase revisisted. In Proceedings of the PODS . 149\u2013158."},{"key":"e_1_3_3_47_2","first-page":"21","volume-title":"Proceedings of the DBLP","author":"Deutsch Alin","year":"2001","unstructured":"Alin Deutsch and Val Tannen . 2001. Optimization properties for classes of conjunctive regular path queries. In Proceedings of the DBLP . 21\u201339. DOI:DOI:https:\/\/doi.org\/10.1007\/3-540-46093-4_2"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_15"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1599410.1599419"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63255-7_22"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.04.002"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/1656242.1656249"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-642-02463-4_12","volume-title":"Conceptual Modeling: Foundations and Applications","author":"Fagin Ronald","year":"2009","unstructured":"Ronald Fagin , Laura M. Haas , Mauricio Hern\u00e1ndez , Ren\u00e9e J. Miller , Lucian Popa , and Yannis Velegrakis . 2009. CLIO: Schema mapping creation and data exchange. In Conceptual Modeling: Foundations and Applications . Springer, 198\u2013236."},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_3_3_57_2","first-page":"372","volume-title":"Proceedings of the IJCAI","author":"Ferraris Paolo","year":"2007","unstructured":"Paolo Ferraris , Joohyung Lee , and Vladimir Lifschitz . 2007. A new perspective on stable models. In Proceedings of the IJCAI . 372\u2013379."},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.011"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189778"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.5555\/1971622.1971623"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_23"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3329120"},{"key":"e_1_3_3_63_2","first-page":"1070","volume-title":"Proceedings of the ICLP\/SLP","author":"Gelfond Michael","year":"1988","unstructured":"Michael Gelfond and Vladimir Lifschitz . 1988. The stable model semantics for logic programming. In Proceedings of the ICLP\/SLP . 1070\u20131080."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000399"},{"key":"e_1_3_3_65_2","first-page":"123","volume-title":"Proceedings of the DL","author":"Goncalves M. Elisabeth","year":"2000","unstructured":"M. Elisabeth Goncalves and Erich Gr\u00e4del . 2000. Decidability issues for action guarded logics. In Proceedings of the DL . 123\u2013132."},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_3_3_67_2","first-page":"757","volume-title":"Proceedings of the AAAI","author":"Gottlob Georg","year":"2012","unstructured":"Georg Gottlob , Andr\u00e9 Hernich , Clemens Kupke , and Thomas Lukasiewicz . 2012. Equality-friendly well-founded semantics and applications to description logics. In Proceedings of the AAAI . 757\u2013764."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_1"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000550"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/45"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346334"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507388"},{"key":"e_1_3_3_74_2","volume-title":"On the Universal Relation","author":"Graham Marc H.","year":"1979","unstructured":"Marc H. Graham . 1979. On the Universal Relation . Technical Report, University of Toronto, Computer Systems Research Group."},{"key":"e_1_3_3_75_2","first-page":"46","volume-title":"Proceedings of the AMW","author":"Grahne G\u00f6sta","year":"2011","unstructured":"G\u00f6sta Grahne and Adrian Onet . 2011. On conditional chase termination. In Proceedings of the AMW (2011), 46."},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.5555\/2566972.2566991"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274600"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465229"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-019-0237-9"},{"key":"e_1_3_3_81_2","volume-title":"Proceedings of the IJCAI","author":"Kr\u00f6tzsch Markus","year":"2011","unstructured":"Markus Kr\u00f6tzsch and Sebastian Rudolph . 2011. Extending decidable existential rules by joining acyclicity and guardedness. In Proceedings of the IJCAI ."},{"key":"e_1_3_3_84_2","volume-title":"Proceedings of the KR","author":"Leone Nicola","year":"2012","unstructured":"Nicola Leone , Marco Manna , Giorgio Terracina , and Pierfrancesco Veltri . 2012. Efficiently computable Datalog ^\\exists programs. In Proceedings of the KR ."},{"key":"e_1_3_3_85_2","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"e_1_3_3_86_2","unstructured":"John J.\n\t\t\t\t\t\t\tLeTourneau\n\t\t\t\t\t. 1968. Decision Problems Related to the Concept of Operation. Phd. Thesis. University of California Berkeley."},{"key":"e_1_3_3_87_2","doi-asserted-by":"publisher","DOI":"10.5555\/2214"},{"key":"e_1_3_3_88_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.111"},{"key":"e_1_3_3_89_2","first-page":"1031","volume-title":"Proceedings of the IJCAI","author":"Magka Despoina","year":"2013","unstructured":"Despoina Magka , Markus Kr\u00f6tzsch , and Ian Horrocks . 2013. Computing stable models for nonmonotonic existential rules. In Proceedings of the IJCAI . 1031\u20131038."},{"key":"e_1_3_3_90_2","doi-asserted-by":"publisher","DOI":"10.1186\/2041-1480-5-17"},{"key":"e_1_3_3_91_2","first-page":"365","volume-title":"Proceedings of the JELIA","author":"Maratea Marco","year":"2010","unstructured":"Marco Maratea , Francesco Ricca , and Pierfrancesco Veltri . 2010. DLV ^{\\mathit {MC}} : Enhanced model checking in DLV. In Proceedings of the JELIA . Springer, 365\u2013368."},{"key":"e_1_3_3_92_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001777"},{"key":"e_1_3_3_93_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90069-C"},{"key":"e_1_3_3_94_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559799"},{"key":"e_1_3_3_95_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2014.6818333"},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80002-3"},{"key":"e_1_3_3_97_2","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754403"},{"key":"e_1_3_3_98_2","doi-asserted-by":"crossref","unstructured":"Adrian Constantin\n\t\t\t\t\t\t\tOnet\n\t\t\t\t\t. 2012. The Chase Procedure and Its Applications . Ph.D. Dissertation. Concordia University.","DOI":"10.14708\/wm.v48i2.314"},{"key":"e_1_3_3_99_2","first-page":"57","volume-title":"Proceedings of the NMELP","author":"Pearce David","year":"1996","unstructured":"David Pearce . 1996. A new logical characterisation of stable models and answer sets. In Proceedings of the NMELP . Springer, 57\u201370."},{"key":"e_1_3_3_100_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-006-9028-z"},{"key":"e_1_3_3_101_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30227-8_15"},{"key":"e_1_3_3_102_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-005-8473-8"},{"key":"e_1_3_3_103_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89982-2_46"},{"key":"e_1_3_3_104_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77688-8_5"},{"key":"e_1_3_3_105_2","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin Michael O.","year":"1969","unstructured":"Michael O. Rabin . 1969. Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141 (1969), 1\u201335.","journal-title":"Trans. Am. Math. Soc."},{"key":"e_1_3_3_106_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/3-540-36387-4_18","volume-title":"Automata, Logics, and Infinite Games","author":"R\u00e4sch Thoralf","year":"2002","unstructured":"Thoralf R\u00e4sch . 2002. Introduction to guarded logics. In Automata, Logics, and Infinite Games . Springer, 321\u2013341."},{"key":"e_1_3_3_107_2","first-page":"20","article-title":"MASTRO at work: Experiences on ontology-based data access","volume":"573","author":"Savo Domenico Fabio","year":"2010","unstructured":"Domenico Fabio Savo , Domenico Lembo , Maurizio Lenzerini , Antonella Poggi , Mariano Rodriguez-Muro , Vittorio Romagnoli , Marco Ruzzi , and Gabriele Stella . 2010. MASTRO at work: Experiences on ontology-based data access. Proc. DL 573 (2010), 20\u201331.","journal-title":"Proc. DL"},{"key":"e_1_3_3_108_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1053"},{"key":"e_1_3_3_109_2","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"e_1_3_3_110_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_3_3_112_2","doi-asserted-by":"publisher","DOI":"10.5555\/294135.294145"},{"key":"e_1_3_3_113_2","first-page":"137","volume-title":"Proceedings of the STOC","author":"Vardi Moshe Y.","year":"1982","unstructured":"Moshe Y. Vardi . 1982. The complexity of relational query languages. In Proceedings of the STOC . 137\u2013146."},{"key":"e_1_3_3_114_2","unstructured":"Mantas\n\t\t\t\t\t\t\t\u0160imkus\n\t\t\t\t\t. 2010. Nonmonotonic Logic Programs with Function Symbols . Ph.D. Dissertation. TU Wien Austria."},{"key":"e_1_3_3_115_2","first-page":"311","volume-title":"Proceedings of the RuleML","author":"\u0160imkus Mantas","year":"2015","unstructured":"Mantas \u0160imkus . 2015. Binary frontier-guarded ASP with function symbols. In Proceedings of the RuleML . 311\u2013327."},{"key":"e_1_3_3_116_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5695"},{"key":"e_1_3_3_117_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/777"},{"key":"e_1_3_3_118_2","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:58Z","timestamp":1750193218000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,22]]},"references-count":114,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3447508"],"URL":"https:\/\/doi.org\/10.1145\/3447508","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,22]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}