{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:52Z","timestamp":1761611272233,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"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":["P20704-N18"],"award-info":[{"award-number":["P20704-N18"]}],"id":[{"id":"10.13039\/501100002428","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,10]]},"abstract":"<jats:p>Bounded treewidth and monadic second-order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know that any property of finite structures, which is expressible by an MSO sentence, can be decided in linear time (data complexity) if the structures have bounded treewidth. In principle, Courcelle's Theorem can be applied directly to construct concrete algorithms by transforming the MSO evaluation problem into a tree language recognition problem. The latter can then be solved via a finite tree automaton (FTA). However, this approach has turned out to be problematical, since even relatively simple MSO formulae may lead to a \u201cstate explosion\u201d of the FTA.<\/jats:p>\n          <jats:p>\n            In this work we propose monadic datalog (i.e., datalog where all intentional predicate symbols are unary) as an alternative method to tackle this class of fixed-parameter tractable problems. We show that if some property of finite structures is expressible in MSO then this property can also be expressed by means of a monadic datalog program over the\n            <jats:italic>decomposed structure<\/jats:italic>\n            : we mean by this that the original structure is augmented with new elements and new relations that encode one of its tree decompositions. In the first place, we thus compare the expressive power of two query languages. However, we also show that the resulting fragment of datalog can be evaluated in linear time (both with respect to the program size and with respect to the data size). Hence, our transformation of an MSO query into a monadic datalog program yields an alternative proof of Courcelle's Theorem. In order to actually construct efficient algorithms for problems whose tractability is due to Courcelle's Theorem, we propose to use a fragment of full (i.e., not necessarily monadic) datalog which allows for a succinct representation of the corresponding monadic datalog programs and for an efficient execution. This new approach is put to work by devising datalog programs for the 3-Colorability problem of graphs and for the PRIMALITY problem of relational schemas (i.e., testing if some attribute in a relational schema is part of a key). We also report on experimental results with a prototype implementation.\n          <\/jats:p>","DOI":"10.1145\/1838552.1838555","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T14:16:37Z","timestamp":1288793797000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Monadic datalog over finite structures of bounded treewidth"],"prefix":"10.1145","volume":"12","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"Oxford University, Oxford, U.K."}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]},{"given":"Fang","family":"Wei","sequence":"additional","affiliation":[{"name":"Albert-Ludwigs-Universit\u00e4t Freiburg, Freiburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,11,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/3.5.685"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514897"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559809"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Ceri S. Gottlob G. and Tanca L. 1990. Logic Programming and Databases. Springer Berlin Germany.   Ceri S. Gottlob G. and Tanca L. 1990. Logic Programming and Databases. Springer Berlin Germany.","DOI":"10.1007\/978-3-642-83952-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90102-2"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","key":"e_1_2_1_12_1","unstructured":"Courcelle , B. 1990a. Graph rewriting: An algebraic and logic approach . In Handbook of Theoretical Computer Science , Vol. B. Elsevier Science Publishers, Amsterdam, The Netherlands, 193-- 242 . Courcelle, B. 1990a. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, Vol. B. Elsevier Science Publishers, Amsterdam, The Netherlands, 193--242."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York NY.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York NY.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_17_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Monographs in Mathematics. Springer Berlin Germany.  Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Monographs in Mathematics. Springer Berlin Germany."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200838"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the ESSLLI Workshop. Lecture Notes in Computer Science","volume":"1754","author":"Eiter T.","unstructured":"Eiter , T. , Gottlob , G. , and Veith , H . 1997a. Generalized quantifiers in logic programs . In Proceedings of the ESSLLI Workshop. Lecture Notes in Computer Science , vol. 1754 . Springer, Berlin, Germany, 72--98. Eiter, T., Gottlob, G., and Veith, H. 1997a. Generalized quantifiers in logic programs. In Proceedings of the ESSLLI Workshop. Lecture Notes in Computer Science, vol. 1754. Springer, Berlin, Germany, 72--98."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of LPNMR. Lecture Notes in Computer Science","volume":"1265","author":"Eiter T.","unstructured":"Eiter , T. , Gottlob , G. , and Veith , H . 1997b. Modular logic programming and generalized quantifiers . In Proceedings of LPNMR. Lecture Notes in Computer Science , vol. 1265 . Springer, Berlin, Germany, 290--309. Eiter, T., Gottlob, G., and Veith, H. 1997b. Modular logic programming and generalized quantifiers. In Proceedings of LPNMR. Lecture Notes in Computer Science, vol. 1265. Springer, Berlin, Germany, 290--309."},{"volume-title":"Proceedings of IJCAI. 90--96","author":"Eiter T.","key":"e_1_2_1_21_1","unstructured":"Eiter , T. , Ianni , G. , Schindlauer , R. , and Tompits , H . 2005. A uniform integration of higher-order reasoning and external evaluations in answer-set programming . In Proceedings of IJCAI. 90--96 . www.jcai.org. Eiter, T., Ianni, G., Schindlauer, R., and Tompits, H. 2005. A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In Proceedings of IJCAI. 90--96. www.jcai.org."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11762256_22"},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of STACS","author":"Fil\u00e9 G.","unstructured":"Fil\u00e9 , G. 1985. Tree automata and logic programs . In Proceedings of STACS . Lecture Notes in Computer Science , vol. 182 . Springer , Berlin, Germany , 119--130. Fil\u00e9, G. 1985. Tree automata and logic programs. In Proceedings of STACS. Lecture Notes in Computer Science, vol. 182. Springer, Berlin, Germany, 119--130."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_25_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer Berlin Germany.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer Berlin Germany."},{"key":"e_1_2_1_26_1","unstructured":"Foustoucos E. and Guessarian I. 2006. Complexity of monadic inf-datalog. application to temporal logic. CoRR abs\/cs\/0603122. http:\/\/arxiv.org\/abs\/cs\/0603122.  Foustoucos E. and Guessarian I. 2006. Complexity of monadic inf-datalog. application to temporal logic. CoRR abs\/cs\/0603122. http:\/\/arxiv.org\/abs\/cs\/0603122."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275546"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"volume-title":"Proceedings of AAAI. AAAI Press","author":"Gottlob G.","key":"e_1_2_1_31_1","unstructured":"Gottlob , G. , Pichler , R. , and Wei , F . 2006a. Bounded treewidth as a key to tractability of knowledge representation and reasoning . In Proceedings of AAAI. AAAI Press , Menlo Park, CA, 250--256. Gottlob, G., Pichler, R., and Wei, F. 2006a. Bounded treewidth as a key to tractability of knowledge representation and reasoning. In Proceedings of AAAI. AAAI Press, Menlo Park, CA, 250--256."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142370"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265554"},{"volume-title":"Proceedings of AAAI. AAAI Press","author":"Gottlob G.","key":"e_1_2_1_34_1","unstructured":"Gottlob , G. , Pichler , R. , and Wei , F . 2008. Abduction with bounded treewidth: From theoretical tractability to practically efficient computation . In Proceedings of AAAI. AAAI Press , Menlo Park, CA, 1541--1546. Gottlob, G., Pichler, R., and Wei, F. 2008. Abduction with bounded treewidth: From theoretical tractability to practically efficient computation. In Proceedings of AAAI. AAAI Press, Menlo Park, CA, 1541--1546."},{"key":"e_1_2_1_35_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of CSL","author":"Grohe M.","unstructured":"Grohe , M. 1999. Descriptive and parameterized complexity . In Proceedings of CSL . Lecture Notes in Computer Science , vol. 1683 . Springer , Berlin, Germany , 14--31. Grohe, M. 1999. Descriptive and parameterized complexity. In Proceedings of CSL. Lecture Notes in Computer Science, vol. 1683. Springer, Berlin, Germany, 14--31."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of (ALENEX). 4th International Workshop on Algorithm Engineering and Experiments, Revised Papers. Lecture Notes in Computer Science","volume":"2409","author":"Gustedt J.","unstructured":"Gustedt , J. , M\u00e6hle , O. A. , and Telle , J. A . 2002. The treewidth of Java programs . In Proceedings of (ALENEX). 4th International Workshop on Algorithm Engineering and Experiments, Revised Papers. Lecture Notes in Computer Science , vol. 2409 . Springer, Berlin, Germany, 86--97. Gustedt, J., M\u00e6hle, O. A., and Telle, J. A. 2002. The treewidth of Java programs. In Proceedings of (ALENEX). 4th International Workshop on Algorithm Engineering and Experiments, Revised Papers. Lecture Notes in Computer Science, vol. 2409. Springer, Berlin, Germany, 86--97."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275466"},{"volume-title":"Proceedings of IJCAI. 816--822","author":"Jakl M.","key":"e_1_2_1_38_1","unstructured":"Jakl , M. , Pichler , R. , and Woltran , S . 2009. Answer-set programming with bounded treewidth . In Proceedings of IJCAI. 816--822 . Jakl, M., Pichler, R., and Woltran, S. 2009. Answer-set programming with bounded treewidth. In Proceedings of IJCAI. 816--822."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/647267.760182"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(05)80078-2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"volume-title":"Elements of Finite Model Theory. Texts in Theoretical Computer Science","author":"Libkin L.","key":"e_1_2_1_43_1","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory. Texts in Theoretical Computer Science . Springer , Berlin, Germany . Libkin, L. 2004. Elements of Finite Model Theory. Texts in Theoretical Computer Science. Springer, Berlin, Germany."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"e_1_2_1_45_1","volume-title":"-J","author":"Mannila H.","year":"1992","unstructured":"Mannila , H. and R\u00e4ih\u00e4 , K . -J . 1992 . The design of relational databases. Addison-Wesley , Reading, MA. Mannila, H. and R\u00e4ih\u00e4, K.-J. 1992. The design of relational databases. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01257085"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the TLT. 5th International Treebanks and Linguistic Theories Conference (TLT). 235--246","author":"Maryns H.","year":"2006","unstructured":"Maryns , H. 2006 . On the implementation of tree automata: Limitations of the naive approach . In Proceedings of the TLT. 5th International Treebanks and Linguistic Theories Conference (TLT). 235--246 . Maryns, H. 2006. On the implementation of tree automata: Limitations of the naive approach. In Proceedings of the TLT. 5th International Treebanks and Linguistic Theories Conference (TLT). 235--246."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90124-X"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02846-5_14"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017944808396"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"volume-title":"Handbook of Formal Languages","author":"Thomas W.","key":"e_1_2_1_53_1","unstructured":"Thomas , W. 1997. Languages , automata, and logic . In Handbook of Formal Languages , Vol. III . Springer , New York, NY , 389--455. Thomas, W. 1997. Languages, automata, and logic. In Handbook of Formal Languages, Vol. III. Springer, New York, NY, 389--455."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman J. D.","key":"e_1_2_1_55_1","unstructured":"Ullman , J. D. 1989. Principles of Database and Knowledge-Base Systems , Vol. 1 . Computer Science Press , New York, NY . Ullman, J. D. 1989. Principles of Database and Knowledge-Base Systems, Vol. 1. Computer Science Press, New York, NY."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1226-x"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1838552.1838555","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1838552.1838555","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:11Z","timestamp":1750250471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1838552.1838555"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1838552.1838555"],"URL":"https:\/\/doi.org\/10.1145\/1838552.1838555","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}