{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:37:15Z","timestamp":1742956635550,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030229955"},{"type":"electronic","value":"9783030229962"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-22996-2_10","type":"book-chapter","created":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T23:02:56Z","timestamp":1562194976000},"page":"108-119","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Conjunctive Regular Path Query Homomorphisms"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Beaudou","sequence":"first","affiliation":[]},{"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"given":"Florent","family":"Madelaine","sequence":"additional","affiliation":[]},{"given":"Lhouari","family":"Nourine","sequence":"additional","affiliation":[]},{"given":"Ga\u00e9tan","family":"Richard","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"10_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"10_CR2","doi-asserted-by":"publisher","unstructured":"Angles, R., et al.: G-CORE: a core for future graph query languages. In: SIGMOD Conference 2018. ACM (2018). https:\/\/doi.org\/10.1145\/3183713.3190654","DOI":"10.1145\/3183713.3190654"},{"key":"10_CR3","doi-asserted-by":"publisher","unstructured":"Baeza, P.B.: Querying graph databases. In: PODS 2013 (2013). https:\/\/doi.org\/10.1145\/2463664.2465216","DOI":"10.1145\/2463664.2465216"},{"issue":"4","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1137\/15M1034714","volume":"45","author":"P Barcel\u00f3","year":"2016","unstructured":"Barcel\u00f3, P., Romero, M., Vardi, M.Y.: Semantic acyclicity on graph databases. SIAM J. Comput. 45(4), 1339\u20131376 (2016). https:\/\/doi.org\/10.1137\/15M1034714","journal-title":"SIAM J. Comput."},{"key":"10_CR5","doi-asserted-by":"publisher","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: FOCS 2017 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.37","DOI":"10.1109\/FOCS.2017.37"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ejc.2017.10.001","volume":"69","author":"J Bulin","year":"2018","unstructured":"Bulin, J.: On the complexity of $$H$$-coloring for special oriented trees. Eur. J. Comb. 69, 54\u201375 (2018). https:\/\/doi.org\/10.1016\/j.ejc.2017.10.001","journal-title":"Eur. J. Comb."},{"key":"10_CR7","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse. In: KR 2000 (2000)"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/3093754.3093759","volume":"46","author":"W Czerwinski","year":"2017","unstructured":"Czerwinski, W., Martens, W., Niewerth, M., Parys, P.: Optimizing tree patterns for querying graph- and tree-structured data. SIGMOD Rec. 46(1), 15\u201322 (2017). https:\/\/doi.org\/10.1145\/3093754.3093759","journal-title":"SIGMOD Rec."},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998). https:\/\/doi.org\/10.1137\/S0097539794266766","journal-title":"SIAM J. Comput."},{"key":"10_CR10","doi-asserted-by":"publisher","unstructured":"Florescu, D., Levy, A.Y., Suciu, D.: Query containment for conjunctive queries with regular expressions. In: PODS 1998 (1998). https:\/\/doi.org\/10.1145\/275487.275503","DOI":"10.1145\/275487.275503"},{"issue":"1","key":"10_CR11","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Nesetril, J.: On the complexity of H-coloring. J. Comb. Theory Ser. B 48(1), 92\u2013110 (1990). https:\/\/doi.org\/10.1016\/0095-8956(90)90132-J","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\u20133","key":"10_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","volume":"109","author":"P Hell","year":"1992","unstructured":"Hell, P., Nesetril, J.: The core of a graph. Discrete Math. 109(1\u20133), 117\u2013126 (1992). https:\/\/doi.org\/10.1016\/0012-365X(92)90282-K","journal-title":"Discrete Math."},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"HB Hunt","year":"1976","unstructured":"Hunt, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12, 222\u2013268 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"10_CR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D.A., Cooper, M.C.: Constraints, consistency and closure. Artif. Intell. 101(1\u20132), 251\u2013265 (1998). https:\/\/doi.org\/10.1016\/S0004-3702(98)00022-8","journal-title":"Artif. Intell."},{"key":"10_CR15","doi-asserted-by":"publisher","unstructured":"Kimelfeld, B., Sagiv, Y.: Revisiting redundancy and minimization in an XPath fragment. In: EDBT 2008 (2008). https:\/\/doi.org\/10.1145\/1353343.1353355","DOI":"10.1145\/1353343.1353355"},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"PG Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302\u2013332 (2000). https:\/\/doi.org\/10.1006\/jcss.2000.1713","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"10_CR17","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995). https:\/\/doi.org\/10.1137\/S009753979122370X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/962446.962448","volume":"51","author":"G Miklau","year":"2004","unstructured":"Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. J. ACM 51(1), 2\u201345 (2004). https:\/\/doi.org\/10.1145\/962446.962448","journal-title":"J. ACM"},{"key":"10_CR19","doi-asserted-by":"publisher","unstructured":"Romero, M., Barcel\u00f3, P., Vardi, M.Y.: The homomorphism problem for regular graph patterns. In: LICS 2017 (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005106","DOI":"10.1109\/LICS.2017.8005106"},{"key":"10_CR20","volume-title":"Algorithms","author":"R Sedgewick","year":"2011","unstructured":"Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Reading (2011)","edition":"4"},{"key":"10_CR21","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: STOC 1973 (1973). https:\/\/doi.org\/10.1145\/800125.804029","DOI":"10.1145\/800125.804029"},{"key":"10_CR22","doi-asserted-by":"publisher","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: FOCS 2017 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.38","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Lecture Notes in Computer Science","Computing with Foresight and Industry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22996-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:20:09Z","timestamp":1709810409000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-22996-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030229955","9783030229962"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22996-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"19 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Durham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/community.dur.ac.uk\/cie.2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Also included are 7 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}