{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T07:30:51Z","timestamp":1789716651813,"version":"4.0.1"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00224-018-9901-2","type":"journal-article","created":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T02:34:07Z","timestamp":1547001247000},"page":"1620-1678","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Evaluating Datalog via Tree Automata and Cycluits"],"prefix":"10.1007","volume":"63","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6158-4607","authenticated-orcid":false,"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"9901_CR1","volume-title":"Foundations of databases","author":"S Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases. Addison-Wesley, Reading (1995)"},{"key":"9901_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3) (1997)","DOI":"10.1007\/BF02523189"},{"key":"9901_CR3","unstructured":"Amarilli, A.: Leveraging the structure of uncertain data. Ph.D. thesis, T\u00e9l\u00e9com ParisTech (2016)"},{"key":"9901_CR4","unstructured":"Amarilli, A., Bourhis, P., Monet, M., Senellart, P.: Combined Tractability of Query Evaluation via Tree Automata and Cycluits. In: ICDT (2017)"},{"key":"9901_CR5","unstructured":"Amarilli, A., Bourhis, P., Monet, M., Senellart, P.: Combined tractability of query evaluation via tree automata and cycluits (extended version). arXiv: 1612.04203 . Extended version of [4] (2017)"},{"key":"9901_CR6","doi-asserted-by":"crossref","unstructured":"Amarilli, A., Bourhis, P., Senellart, P.: Provenance Circuits for Trees and Treelike Instances. In: ICALP (2015)","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"9901_CR7","doi-asserted-by":"crossref","unstructured":"Amarilli, A., Monet, M., Senellart, P.: Conjunctive Queries on Probabilistic Graphs: Combined Complexity. In: PODS (2017)","DOI":"10.1145\/3034786.3056121"},{"key":"9901_CR8","doi-asserted-by":"crossref","unstructured":"Ba\u0307ra\u0307ny, V., ten Cate, B., Otto, M.: Queries with guarded negation. PVLDB 5(11) (2012)","DOI":"10.14778\/2350229.2350250"},{"key":"9901_CR9","doi-asserted-by":"crossref","unstructured":"Ba\u0307ra\u0307ny, V., Ten Cate, B., Segoufin, L.: Guarded negation. J ACM 62(3) (2015)","DOI":"10.1145\/2701414"},{"key":"9901_CR10","unstructured":"Barcel\u00f3, P.: Querying graph databases. In: PODS (2013)"},{"key":"9901_CR11","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3, P., Romero, M., Vardi, M.Y.: Does query evaluation tractability help query containment?. In: PODS (2014)","DOI":"10.1145\/2594538.2594553"},{"key":"9901_CR12","unstructured":"Benedikt, M., Bourhis, P., Gottlob, G., Senellart, P.: Monadic datalog and limited access containment. Unpublished (2016)"},{"key":"9901_CR13","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Bourhis, P., Senellart, P.: Monadic datalog containment. In: ICALP (2012)","DOI":"10.1007\/978-3-642-31585-5_11"},{"key":"9901_CR14","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Bourhis, P., Vanden Boom, M.: A step up in expressiveness of decidable fixpoint logics. In: LICS (2016)","DOI":"10.1145\/2933575.2933592"},{"key":"9901_CR15","doi-asserted-by":"crossref","unstructured":"Benedikt, M., ten Cate, B., Vanden Boom, M.: Effective interpolation and preservation in guarded logics. In: LICS (2014)","DOI":"10.1145\/2603088.2603108"},{"key":"9901_CR16","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Gottlob, G.: The impact of virtual views on containment. PVLDB 3(1-2) (2010)","DOI":"10.14778\/1920841.1920882"},{"key":"9901_CR17","doi-asserted-by":"crossref","unstructured":"Berry, A., Pogorelcnik, R., Simonet, G.: An introduction to clique minimal separator decomposition. Algorithms 3(2) (2010)","DOI":"10.3390\/a3020197"},{"key":"9901_CR18","doi-asserted-by":"crossref","unstructured":"Berwanger, D., Gra\u0307del, E.: Games and model checking for guarded logics. In: LPAR (2001)","DOI":"10.1007\/3-540-45653-8_5"},{"key":"9901_CR19","doi-asserted-by":"crossref","unstructured":"Birget, J. C.: State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory 26(3) (1993)","DOI":"10.1007\/BF01371727"},{"key":"9901_CR20","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput 25(6) (1996)","DOI":"10.1137\/S0097539793251219"},{"key":"9901_CR21","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput 208(3) (2010)","DOI":"10.1016\/j.ic.2009.03.008"},{"key":"9901_CR22","doi-asserted-by":"crossref","unstructured":"Cachat, T.: Two-way tree automata solving pushdown games. In: Automata Logics, and Infinite Games, Chap. 17. Springer (2002)","DOI":"10.1007\/3-540-36387-4_17"},{"key":"9901_CR23","unstructured":"Calvanese, D., De Giacomo, G., Lenzeniri, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse. In: KR (2000)"},{"key":"9901_CR24","doi-asserted-by":"crossref","unstructured":"Chandra, A. K., Vardi, M. Y.: The implication problem for functional and inclusion dependencies is undecidable. SIAM Journal on Computing 14(3) (1985)","DOI":"10.1137\/0214049"},{"key":"9901_CR25","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata: Techniques and applications (2007)"},{"key":"9901_CR26","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S., Gaifman, H., Kanellakis, P., Vardi, M.: Decidable Optimization Problems for Database Logic Programs. In: STOC (1988)","DOI":"10.1145\/62212.62259"},{"key":"9901_CR27","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput 85(1) (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"9901_CR28","unstructured":"Deutch, D., Milo, T., Roy, S., Tannen, V.: Circuits for Datalog Provenance. In: ICDT (2014)"},{"key":"9901_CR29","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Simplicial decompositions of graphs: A survey of applications. Discrete Math 75(1) (1989)","DOI":"10.1016\/0012-365X(89)90084-8"},{"key":"9901_CR30","doi-asserted-by":"crossref","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J ACM 30(3) (1983)","DOI":"10.1145\/2402.322390"},{"key":"9901_CR31","doi-asserted-by":"crossref","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions j.ACM 49(6) (2002)","DOI":"10.1145\/602220.602222"},{"key":"9901_CR32","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin (2006)"},{"key":"9901_CR33","doi-asserted-by":"crossref","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J Combinatorial Theory 16(1) (1974)","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"9901_CR34","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Gra\u0307del, E., Veith, H.: Datalog LITE: A deductive query language with linear time model checking. ACM Trans. Comput. Log 3(1) (2002)","DOI":"10.1145\/504077.504079"},{"key":"9901_CR35","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Treewidth and hypertree width. In: Tractability: Practical Approaches to Hard Problems, Chap. 1. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781139177801.002"},{"key":"9901_CR36","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. JCSS 64(3) (2002)","DOI":"10.1006\/jcss.2001.1809"},{"key":"9901_CR37","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. JCSS 66(4) (2003)","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"9901_CR38","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic Datalog over finite structures of bounded treewidth. TOCL 12(1) (2010)","DOI":"10.1145\/1838552.1838555"},{"key":"9901_CR39","doi-asserted-by":"crossref","unstructured":"Gra\u0307del, E.: Guarded fixed point logics and the monadic theory of countable trees. Theor. Comput. Sci. 288(1) (2002)","DOI":"10.1016\/S0304-3975(01)00151-7"},{"key":"9901_CR40","doi-asserted-by":"crossref","unstructured":"Green, T. J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS (2007)","DOI":"10.1145\/1265530.1265535"},{"key":"9901_CR41","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. TALG 11(1) (2014)","DOI":"10.1145\/2636918"},{"key":"9901_CR42","doi-asserted-by":"crossref","unstructured":"Imielinski, T., Lipski Jr., W.: Incomplete information in relational databases. J ACM 31(4) (1984)","DOI":"10.1145\/1634.1886"},{"key":"9901_CR43","doi-asserted-by":"crossref","unstructured":"Leimer, H.G.: Optimal decomposition by clique separators. Discrete Math 113(1-3) (1993)","DOI":"10.1016\/0012-365X(93)90510-Z"},{"key":"9901_CR44","doi-asserted-by":"crossref","unstructured":"Leinders, D., Marx, M., Tyszkiewicz, J., Den Bussche, J.V.: The semijoin algebra and the guarded fragment. Journal of Logic Language and Information 14(3) (2005)","DOI":"10.1007\/s10849-005-5789-8"},{"key":"9901_CR45","unstructured":"Malik, S.: Analysis of cyclic combinational circuits. In: ICCAD (1993)"},{"key":"9901_CR46","doi-asserted-by":"crossref","unstructured":"Maniu, S., Cheng, R., Senellart, P.: An indexing framework for queries on probabilistic graphs. ACM Transactions on Database Systems 42(2) (2017)","DOI":"10.1145\/3044713"},{"key":"9901_CR47","unstructured":"Mendelzon, A. O., Wood, P.T.: Finding regular simple paths in graph databases. In: VLDB (1989)"},{"key":"9901_CR48","doi-asserted-by":"crossref","unstructured":"Meyer, A. R.: Weak Monadic Second Order Theory of Succesor is Not Elementary-Recursive. In: Logic Colloquium (1975)","DOI":"10.1007\/BFb0064872"},{"key":"9901_CR49","doi-asserted-by":"crossref","unstructured":"Mitchell, J. C.: The implication problem for functional and inclusion dependencies. Information and Control 56(3) (1983)","DOI":"10.1016\/S0019-9958(83)80002-3"},{"key":"9901_CR50","doi-asserted-by":"crossref","unstructured":"Monet, M.: Probabilistic evaluation of expressive queries on bounded-treewidth instances. In: SIGMOD\/PODS Phd Symposium (2016)","DOI":"10.1145\/2926693.2929905"},{"key":"9901_CR51","doi-asserted-by":"crossref","unstructured":"Riedel, M. D., Bruck, J., title=Cyclic Boolean circuits. Discrete Applied Mathematics 160(13-14) (2012)","DOI":"10.1016\/j.dam.2012.03.039"},{"key":"9901_CR52","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P. D.: Graph minors. III. Planar tree-width. J. Comb. theory, Ser B 36(1) (1984)","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"9901_CR53","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P. D.: Graph minors. II. Algorithmic aspects of tree-width. J Algorithms 7(3) (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"9901_CR54","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM Journal on Computing (1972)","DOI":"10.1109\/SWAT.1971.10"},{"key":"9901_CR55","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math 55(2) (1985)","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"9901_CR56","doi-asserted-by":"crossref","unstructured":"Tarjan, R. E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing 13(3) (1984)","DOI":"10.1137\/0213035"},{"key":"9901_CR57","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5 (1955)","DOI":"10.2140\/pjm.1955.5.285"},{"key":"9901_CR58","doi-asserted-by":"crossref","unstructured":"Thompson, K.: Programming Techniques: Regular Expression Search Algorithm. Communications of the ACM (1968)","DOI":"10.1145\/363347.363387"},{"key":"9901_CR59","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: STOC (1982)","DOI":"10.1145\/800070.802186"},{"key":"9901_CR60","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: PODS (1995)","DOI":"10.1145\/212433.212474"},{"key":"9901_CR61","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: VLDB (1981)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9901-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9901-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9901-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T22:46:28Z","timestamp":1662763588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9901-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":61,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9901"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9901-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"8 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}