{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:34Z","timestamp":1759637734710},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_58","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"708-719","source":"Crossref","is-referenced-by-count":5,"title":["Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"58_CR1","unstructured":"S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases, Addison-Wesley Publishing Company (1995)."},{"key":"58_CR2","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/0004-3702(88)90023-9","volume":"35","author":"W. Bibel","year":"1988","unstructured":"W. Bibel. Constraint Satisfaction from a Deductive Viewpoint. In Artificial Intelligence, Vol 35, pp. 401\u2013413 (1988).","journal-title":"Artificial Intelligence"},{"key":"58_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. In SIAM Journal on Computing, Vol 25, No 6, pp. 1305\u20131317 (1996).","journal-title":"SIAM Journal on Computing"},{"key":"58_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Proc. of MFCS\u201997","author":"H.L. Bodlaender","year":"1997","unstructured":"H.L. Bodlaender. Treewidth: Algorithmic Techniques and Results. In Proc. of MFCS\u201997, LNCS 1295, pp. 19\u201336, Springer, (1997)."},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, P.M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases. In Proc. of STOC\u201977, pp. 77\u201390, ACM Press (1977).","DOI":"10.1145\/800105.803397"},{"key":"58_CR6","unstructured":"E.M. Clarke, O. Grumberg, D. Peled. Model Checking, MIT Press (1999)."},{"key":"58_CR7","series-title":"Lect Notes Comput Sci","first-page":"130","volume-title":"Proc. of ICDT\u201997","author":"Ch. Chekuri","year":"1997","unstructured":"Ch. Chekuri, A. Rajaraman. Conjunctive Query Containment Revisited. In Proc. of ICDT\u201997, LNCS 1186, pp. 130\u2013144, Springer (1997)."},{"key":"58_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/10719839_14","volume-title":"Proc. of LATIN 2000","author":"D.G. Corneil","year":"2000","unstructured":"D.G. Corneil, M. Habib, J.-M. Langlinel, B. Reed, U. Rotics. Polynomial Time Recognition of clique-width \u2264 3 graphs, extended abstract. In Proc. of LATIN 2000, LNCS 1776, pp. 126\u2013134, Springer (2000)."},{"key":"58_CR9","unstructured":"B. Courcelle. Graph Rewriting: An Algebraic and Logic Approach. In Handbook of Theoretical Computer Science, Vol 2, pp. 194\u2013241, J. van Leeuwen (ed.), Elsevier Science Publishers (1990)."},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90148-9","volume":"101","author":"B. Courcelle","year":"1992","unstructured":"B. Courcelle. Monadic second-order logic of graphs VII: Graphs as relational structures. In Theoretical Computer Science, Vol 101, pp. 3\u201333 (1992).","journal-title":"Theoretical Computer Science"},{"key":"58_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, J. Engelfriet, G. Rozenberg. Handle-rewriting hypergraph grammars. In Journal of Computer and System Sciences, Vol 46, pp. 218\u2013270 (1993).","journal-title":"Journal of Computer and System Sciences"},{"key":"58_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle, J.A. Makowsky, U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. In Theory of Computing Systems, Vol 33, pp. 125\u2013150 (2000).","journal-title":"Theory of Computing Systems"},{"key":"58_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle, S. Olariu. Upper bounds on the clique-width of graphs. In Discrete Applied Mathematics, Vol 101, pp. 77\u2013114 (2000).","journal-title":"Discrete Applied Mathematics"},{"key":"58_CR14","unstructured":"A. D\u2019Atri, M. Moscarini. Acyclic Hypergraphs: Their recognition and top-down versus bottom-up generation. Technical Report R.29, Consiglio Nazionale delle Ricerche, Istituto di Analisi dei Sistemi ed Informatica (1982)."},{"key":"58_CR15","unstructured":"R.G. Downey, M.R. Fellows. Parameterized Complexity, Springer-Verlag (1997)."},{"issue":"3","key":"58_CR16","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"R. Fagin. Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. In Journal of the ACM, Vol 30, No 3, pp. 514\u2013550 (1983).","journal-title":"Journal of the ACM"},{"key":"58_CR17","unstructured":"J. Flum, M. Frick, and M. Grohe. Query Evaluation via Tree-Decomposition. In Proc. of ICDT\u201901. Currently available at http:\/\/www.math.uic.edu\/grohe\/pub\/query.ps"},{"key":"58_CR18","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, F. Scarcello. The Complexity of Acyclic Conjunctive Queries. In Proc. of FOCS\u201998, pp. 706\u2013715, (1998). Full paper to appear in JACM.","DOI":"10.1109\/SFCS.1998.743521"},{"key":"58_CR19","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, F. Scarcello. Hypertree Decompositions and Tractable Queries. In Proc. of PODS\u201999, pp. 21\u201332, ACM Press (1999).","DOI":"10.1145\/303976.303979"},{"key":"58_CR20","unstructured":"G. Gottlob, N. Leone, F. Scarcello. A Comparison of Structural CSP Decomposition Methods. In Proc. of IJCAI\u201999, pp. 394\u2013399, Morgan Kaufmann, (1999)."},{"key":"58_CR21","doi-asserted-by":"crossref","unstructured":"G. Gottlob, R. Pichler. Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. Full paper. Available from the authors (2001).","DOI":"10.1007\/3-540-48224-5_58"},{"key":"58_CR22","doi-asserted-by":"crossref","unstructured":"M. Grohe, T. Schwentick, and L. Segoufin. When is the Evaluation of Conjunctive Queries Tractable Manuscript, currently available at: http:\/\/www.math.uic.edu\/grohe\/ pub\/grid.ps (2001).","DOI":"10.1145\/380752.380867"},{"key":"58_CR23","doi-asserted-by":"crossref","unstructured":"Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. In Proc. of PODS\u201998, pp. 205\u2013213, ACM Press (1998).","DOI":"10.1145\/275487.275511"},{"key":"58_CR24","unstructured":"K. Kunen: Answer Sets and Negation as Failure. In Proc. of the Fourth Int. Conf. on Logic Programming, Melbourne, pp. 219\u2013228 (1987)."},{"key":"58_CR25","unstructured":"M. Yannakakis. Algorithms for Acyclic Database Schemes. In Proc. of Int. Conf. on Very Large Data Bases (VLDB\u201981), pp. 82\u201394, Cannes, France (1981)."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:28:47Z","timestamp":1556922527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_58","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}