{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:27Z","timestamp":1759063767058,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,3,23]],"date-time":"2010-03-23T00:00:00Z","timestamp":1269302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,3,23]]},"DOI":"10.1145\/1804669.1804691","type":"proceedings-article","created":{"date-parts":[[2010,5,18]],"date-time":"2010-05-18T13:46:25Z","timestamp":1274190385000},"page":"165-173","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of rooted phylogeny problems"],"prefix":"10.1145","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"CNRS\/LIX, \u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens K.","family":"Mueller","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,3,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases . Addison Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995."},{"key":"e_1_3_2_1_2_1","volume-title":"Relations related to betweenness: their structure and automorphisms. AMS Memoir, 131(623)","author":"Adeleke S.","year":"1998","unstructured":"S. Adeleke and P. M. Neumann . Relations related to betweenness: their structure and automorphisms. AMS Memoir, 131(623) , 1998 . S. Adeleke and P. M. Neumann. Relations related to betweenness: their structure and automorphisms. AMS Memoir, 131(623), 1998."},{"key":"e_1_3_2_1_3_1","first-page":"113","volume-title":"21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems","author":"Afrati F.","year":"1991","unstructured":"F. Afrati , S. S. Comadakis , and M. Yannakakis . On Datalog vs. polynomial time . In 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems , pages 113 -- 126 , 1991 . F. Afrati, S. S. Comadakis, and M. Yannakakis. On Datalog vs. polynomial time. In 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 113--126, 1991."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_53"},{"key":"e_1_3_2_1_8_1","volume-title":"CoRR abs\/0805.1473. Accepted for publication in the ACM Transactions of Computing Systems","author":"Bodirsky M.","year":"2008","unstructured":"M. Bodirsky and J. K\u00e1ra . A fast algorithm and Datalog inexpressibility for temporal reasoning. Preprint , CoRR abs\/0805.1473. Accepted for publication in the ACM Transactions of Computing Systems , 2008 . M. Bodirsky and J. K\u00e1ra. A fast algorithm and Datalog inexpressibility for temporal reasoning. Preprint, CoRR abs\/0805.1473. Accepted for publication in the ACM Transactions of Computing Systems, 2008."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.12.004"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00075-4"},{"key":"e_1_3_2_1_11_1","volume-title":"Building trees, hunting for trees, and comparing trees. PhD-thesis at the University of Canterbury","author":"Bryant D.","year":"1997","unstructured":"D. Bryant . Building trees, hunting for trees, and comparing trees. PhD-thesis at the University of Canterbury , 1997 . D. Bryant. Building trees, hunting for trees, and comparing trees. PhD-thesis at the University of Canterbury, 1997."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1995.1020"},{"key":"e_1_3_2_1_13_1","first-page":"181","article-title":"The complexity of constraint satisfaction: An algebraic approach (a survey paper). In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics","volume":"207","author":"Bulatov A.","year":"2005","unstructured":"A. Bulatov , P. Jeavons , and A. Krokhin . The complexity of constraint satisfaction: An algebraic approach (a survey paper). In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics , Chemistry , 207 : 181 -- 213 , 2005 . A. Bulatov, P. Jeavons, and A. Krokhin. The complexity of constraint satisfaction: An algebraic approach (a survey paper). In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry, 207:181--213, 2005.","journal-title":"Chemistry"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3115\/981732.981755"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1997310604991"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/377810"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90043-W"},{"key":"e_1_3_2_1_18_1","volume-title":"Vrije Universiteit","author":"Dekker M. C. H.","year":"1986","unstructured":"M. C. H. Dekker . Reconstruction methods for derivation trees. Masters thesis , Vrije Universiteit , Amsterdam , 1986 . M. C. H. Dekker. Reconstruction methods for derivation trees. Masters thesis, Vrije Universiteit, Amsterdam, 1986."},{"key":"e_1_3_2_1_19_1","volume-title":"Structure of partially ordered sets with transitive automorphism groups. AMS Memoir, 57(334)","author":"Droste M.","year":"1985","unstructured":"M. Droste . Structure of partially ordered sets with transitive automorphism groups. AMS Memoir, 57(334) , 1985 . M. Droste. Structure of partially ordered sets with transitive automorphism groups. AMS Memoir, 57(334), 1985."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-004-5899-8"},{"key":"e_1_3_2_1_21_1","volume-title":"Finite Model Theory","author":"Ebbinghaus H.-D.","year":"1999","unstructured":"H.-D. Ebbinghaus and J. Flum . Finite Model Theory . Springer , 1999 . 2 nd edition. H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999. 2nd edition.","edition":"2"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_23_1","volume-title":"Br.","author":"Grohe M.","year":"1994","unstructured":"M. Grohe . The structure of fixed-point logics. PhD-thesis at the Albert-Ludwigs Universit\u00e4t, Freiburg i . Br. , 1994 . M. Grohe. The structure of fixed-point logics. PhD-thesis at the Albert-Ludwigs Universit\u00e4t, Freiburg i. Br., 1994."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_3_2_1_25_1","first-page":"333","volume-title":"Proceedings of the 7th Symposium on Discrete Algorithms (SODA'96)","author":"Henzinger M.","year":"1996","unstructured":"M. Henzinger , V. King , and T. Warnow . Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology . In Proceedings of the 7th Symposium on Discrete Algorithms (SODA'96) , pages 333 -- 340 , 1996 . M. Henzinger, V. King, and T. Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In Proceedings of the 7th Symposium on Discrete Algorithms (SODA'96), pages 333--340, 1996."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/7.3.309"},{"key":"e_1_3_2_1_27_1","volume-title":"Graduate Texts in Computer Science","author":"Immerman N.","year":"1998","unstructured":"N. Immerman . Descriptive Complexity . Graduate Texts in Computer Science , Springer , 1998 . N. Immerman. Descriptive Complexity. Graduate Texts in Computer Science, Springer, 1998."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275511"},{"key":"e_1_3_2_1_30_1","first-page":"99","article-title":"Consistency in networks of relations","volume":"8","author":"Mackworth A. K.","year":"1977","unstructured":"A. K. Mackworth . Consistency in networks of relations . AI , 8 : 99 -- 118 , 1977 . A. K. Mackworth. Consistency in networks of relations. AI, 8:99--118, 1977.","journal-title":"AI"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00160-2"},{"key":"e_1_3_2_1_33_1","volume-title":"The two-valued iterative systems of mathematical logic. Annals of Mathematics studies, 5","author":"Post E. L.","year":"1941","unstructured":"E. L. Post . The two-valued iterative systems of mathematical logic. Annals of Mathematics studies, 5 , 1941 . E. L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematics studies, 5, 1941."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"}],"event":{"name":"EDBT\/ICDT '10: EDBT\/ICDT '10 joint conference","acronym":"EDBT\/ICDT '10","location":"Lausanne Switzerland"},"container-title":["Proceedings of the 13th International Conference on Database Theory"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1804669.1804691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1804669.1804691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:36Z","timestamp":1750286616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1804669.1804691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,23]]},"references-count":34,"alternative-id":["10.1145\/1804669.1804691","10.1145\/1804669"],"URL":"https:\/\/doi.org\/10.1145\/1804669.1804691","relation":{},"subject":[],"published":{"date-parts":[[2010,3,23]]},"assertion":[{"value":"2010-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}