{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T08:22:10Z","timestamp":1792743730168,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["369116833"],"award-info":[{"award-number":["369116833"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3524149","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T09:29:54Z","timestamp":1655112594000},"page":"165-174","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs"],"prefix":"10.1145","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tina","family":"Popp","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.021"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103516.103517"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2467795"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.08.006"},{"key":"e_1_3_2_2_7_1","volume-title":"Symposium on Principles of Database Systems (PODS). 175--188","author":"Barcel\u00f3 Pablo","year":"2013","unstructured":"Pablo Barcel\u00f3 . 2013 . Querying graph databases . In Symposium on Principles of Database Systems (PODS). 175--188 . Pablo Barcel\u00f3. 2013. Querying graph databases. In Symposium on Principles of Database Systems (PODS). 175--188."},{"key":"e_1_3_2_2_8_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs","author":"Barcel\u00f3 Pablo","unstructured":"Pablo Barcel\u00f3 , Diego Figueira , and Miguel Romero . 2019. Boundedness of Conjunctive Regular Path Queries . In International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs , Vol. 132). 104:1--104: 15 . Pablo Barcel\u00f3, Diego Figueira, and Miguel Romero. 2019. Boundedness of Conjunctive Regular Path Queries. In International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 132). 104:1--104:15."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"key":"e_1_3_2_2_11_1","first-page":"315","article-title":"Regular Path Queries in Lightweight Description Logics","volume":"53","author":"Bienvenu Meghyn","year":"2015","unstructured":"Meghyn Bienvenu , Magdalena Ortiz , and Mantas Simkus . 2015 . Regular Path Queries in Lightweight Description Logics : Complexity and Algorithms. J. Artif. Intell. Res. , Vol. 53 (2015), 315 -- 374 . Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. 2015. Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms. J. Artif. Intell. Res., Vol. 53 (2015), 315--374.","journal-title":"Complexity and Algorithms. J. Artif. Intell. Res."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45276-0_1"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1223034"},{"key":"e_1_3_2_2_14_1","volume-title":"Navigating the Maze of Wikidata Query Logs. In The Web Conference (WWW). ACM. To appear.","author":"Bonifati Angela","year":"2019","unstructured":"Angela Bonifati , Wim Martens , and Thomas Tim . 2019 . Navigating the Maze of Wikidata Query Logs. In The Web Conference (WWW). ACM. To appear. Angela Bonifati, Wim Martens, and Thomas Tim. 2019. Navigating the Maze of Wikidata Query Logs. In The Web Conference (WWW). ACM. To appear."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3167892.3167895"},{"key":"e_1_3_2_2_16_1","unstructured":"Diego Calvanese Giuseppe De Giacomo Maurizio Lenzerini and Moshe Y. Vardi. 2000 a. Containment of Conjunctive Regular Path Queries with Inverse. In KR. Morgan Kaufmann 176--185.  Diego Calvanese Giuseppe De Giacomo Maurizio Lenzerini and Moshe Y. Vardi. 2000 a. Containment of Conjunctive Regular Path Queries with Inverse. In KR. Morgan Kaufmann 176--185."},{"key":"e_1_3_2_2_17_1","volume-title":"View-Based Query Processing for Regular Path Queries with Inverse. In Symposium on Principles of Database Systems (PODS). ACM, 58--66","author":"Calvanese Diego","unstructured":"Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , and Moshe Y. Vardi . 2000 b . View-Based Query Processing for Regular Path Queries with Inverse. In Symposium on Principles of Database Systems (PODS). ACM, 58--66 . Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000 b. View-Based Query Processing for Regular Path Queries with Inverse. In Symposium on Principles of Database Systems (PODS). ACM, 58--66."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1805"},{"key":"e_1_3_2_2_19_1","volume-title":"Schmid","author":"Casel Katrin","year":"2021","unstructured":"Katrin Casel and Markus L . Schmid . 2021 . Fine-Grained Complexity of Regular Path Queries. In ICDT (LIPIcs , Vol. 186). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 19:1--19: 20 . Katrin Casel and Markus L. Schmid. 2021. Fine-Grained Complexity of Regular Path Queries. In ICDT (LIPIcs, Vol. 186). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 19:1--19:20."},{"key":"e_1_3_2_2_20_1","volume-title":"Paths through fixed vertices in edge-colored graphs. Math\u00e9matiques et Sciences humaines","author":"Chou W. S.","year":"1994","unstructured":"W. S. Chou , Y. Manoussakis , O. Megalakaki , M. Spyratos , and Zs. Tuza . 1994. Paths through fixed vertices in edge-colored graphs. Math\u00e9matiques et Sciences humaines , Vol. 127 ( 1994 ), 49--58. http:\/\/www.numdam.org\/item\/MSH_1994__127__49_0\/ W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, and Zs. Tuza. 1994. Paths through fixed vertices in edge-colored graphs. Math\u00e9matiques et Sciences humaines, Vol. 127 (1994), 49--58. http:\/\/www.numdam.org\/item\/MSH_1994__127__49_0\/"},{"key":"e_1_3_2_2_21_1","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330","author":"Cruz Isabel F.","unstructured":"Isabel F. Cruz , Alberto O. Mendelzon , and Peter T. Wood . 1987. A Graphical Query Language Supporting Recursion . In ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330 . Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. 1987. A Graphical Query Language Supporting Recursion. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330."},{"key":"e_1_3_2_2_22_1","volume-title":"Discrete Applied Mathematics","volume":"292","author":"Darmann Andreas","year":"2021","unstructured":"Andreas Darmann and Janosch D\u00f6cker . 2021 . On simplified NP-complete variants of Monotone 3-Sat . Discrete Applied Mathematics , Vol. 292 (03 2021), 45--58. Andreas Darmann and Janosch D\u00f6cker. 2021. On simplified NP-complete variants of Monotone 3-Sat. Discrete Applied Mathematics, Vol. 292 (03 2021), 45--58."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Alin Deutsch Nadime Francis Alastair Green Keith Hare Bei Li Leonid Libkin Tobias Lindaaker Victor Marsault Wim Martens Jan Michels Filip Murlak Stefan Plantikow Petra Selmer Hannes Voigt Oskar van Rest Domagoj Vrgoc Mingxi Wu and Fred Zemke. 2021. Graph Pattern Matching in GQL and SQL\/PGQ. arxiv: 2112.06217 [cs.DB]  Alin Deutsch Nadime Francis Alastair Green Keith Hare Bei Li Leonid Libkin Tobias Lindaaker Victor Marsault Wim Martens Jan Michels Filip Murlak Stefan Plantikow Petra Selmer Hannes Voigt Oskar van Rest Domagoj Vrgoc Mingxi Wu and Fred Zemke. 2021. Graph Pattern Matching in GQL and SQL\/PGQ. arxiv: 2112.06217 [cs.DB]","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_3_2_2_24_1","volume-title":"DBPL (Lecture Notes in Computer Science","volume":"39","author":"Deutsch Alin","year":"2001","unstructured":"Alin Deutsch and Val Tannen . 2001 . Optimization Properties for Classes of Conjunctive Regular Path Queries . In DBPL (Lecture Notes in Computer Science , Vol. 2397). Springer, 21-- 39 . Alin Deutsch and Val Tannen. 2001. Optimization Properties for Classes of Conjunctive Regular Path Queries. In DBPL (Lecture Notes in Computer Science, Vol. 2397). Springer, 21--39."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00121-2"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2873608.2873622"},{"key":"e_1_3_2_2_27_1","volume-title":"Wim Martens, Matthias Niewerth, and Tina Trautner.","author":"Figueira Diego","year":"2020","unstructured":"Diego Figueira , Adwait Godbole , Shankara Narayanan Krishna , Wim Martens, Matthias Niewerth, and Tina Trautner. 2020 . Containment of Simple Conjunctive Regular Path Queries. In KR. 371--380. Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. Containment of Simple Conjunctive Regular Path Queries. In KR. 371--380."},{"key":"e_1_3_2_2_28_1","volume-title":"Query Containment for Conjunctive Queries with Regular Expressions","author":"Florescu Daniela","unstructured":"Daniela Florescu , Alon Y. Levy , and Dan Suciu . 1998. Query Containment for Conjunctive Queries with Regular Expressions . In PODS. ACM Press , 139--148. Daniela Florescu, Alon Y. Levy, and Dan Suciu. 1998. Query Containment for Conjunctive Queries with Regular Expressions. In PODS. ACM Press, 139--148."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_3_2_2_30_1","volume-title":"International Conference on Database Theory (ICDT). OpenProceedings.org, 107--118","author":"Francis Nadime","year":"2014","unstructured":"Nadime Francis , Luc Segoufin , and Cristina Sirangelo . 2014 . Datalog Rewritings of Regular Path Queries using Views . In International Conference on Database Theory (ICDT). OpenProceedings.org, 107--118 . Nadime Francis, Luc Segoufin, and Cristina Sirangelo. 2014. Datalog Rewritings of Regular Path Queries using Views. In International Conference on Database Theory (ICDT). OpenProceedings.org, 107--118."},{"key":"e_1_3_2_2_31_1","first-page":"57","article-title":"On paths, trails and closed trails in edge-colored graphs","volume":"14","author":"Laurent Gourv\u00e8","year":"2012","unstructured":"Laurent Gourv\u00e8 s, Adria Ramos de Lyra , Carlos A. J. Martinhon , and J\u00e9r\u00f4me Monnot . 2012 . On paths, trails and closed trails in edge-colored graphs . Discret. Math. Theor. Comput. Sci. , Vol. 14 , 2 (2012), 57 -- 74 . Laurent Gourv\u00e8 s, Adria Ramos de Lyra, Carlos A. J. Martinhon, and J\u00e9r\u00f4me Monnot. 2012. On paths, trails and closed trails in edge-colored graphs. Discret. Math. Theor. Comput. Sci., Vol. 14, 2 (2012), 57--74.","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"e_1_3_2_2_32_1","volume-title":"The Linkage Problem for Group-labelled Graphs","author":"Huynh Tony","year":"2009","unstructured":"Tony Huynh . 2009. The Linkage Problem for Group-labelled Graphs . IEEE Expert \/ IEEE Intelligent Systems - EXPERT ( 01 2009 ). Tony Huynh. 2009. The Linkage Problem for Group-labelled Graphs. IEEE Expert \/ IEEE Intelligent Systems - EXPERT (01 2009)."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.12.002"},{"key":"e_1_3_2_2_34_1","volume-title":"The Graph Minor Algorithm with Parity Conditions","author":"Reed Bruce A.","unstructured":"Ken-ichi Kawarabayashi, Bruce A. Reed , and Paul Wollan . 2011. The Graph Minor Algorithm with Parity Conditions . In FOCS. IEEE Computer Society , 27--36. Ken-ichi Kawarabayashi, Bruce A. Reed, and Paul Wollan. 2011. The Graph Minor Algorithm with Parity Conditions. In FOCS. IEEE Computer Society, 27--36."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.002"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140403"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448513"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00091-Q"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958009"},{"key":"e_1_3_2_2_42_1","volume-title":"STACS (LIPIcs","volume":"16","author":"Martens Wim","year":"2020","unstructured":"Wim Martens , Matthias Niewerth , and Tina Trautner . 2020 . A Trichotomy for Regular Trail Queries . In STACS (LIPIcs , Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 7:1--7: 16 . Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. A Trichotomy for Regular Trail Queries. In STACS (LIPIcs, Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 7:1--7:16."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331446"},{"key":"e_1_3_2_2_44_1","volume-title":"Wood","author":"Mendelzon Alberto O.","year":"1995","unstructured":"Alberto O. Mendelzon and Peter T . Wood . 1995 . Finding Regular Simple Paths in Graph Databases. SIAM J. Comput ., Vol. 24 , 6 (12 1995), 1235--1258. Alberto O. Mendelzon and Peter T. Wood. 1995. Finding Regular Simple Paths in Graph Databases. SIAM J. Comput., Vol. 24, 6 (12 1995), 1235--1258."},{"key":"e_1_3_2_2_45_1","volume-title":"Regular Queries on Graph Databases. In International Conference on Database Theory (ICDT). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 177--194","author":"Reutter Juan L.","unstructured":"Juan L. Reutter , Miguel Romero , and Moshe Y. Vardi . 2015 . Regular Queries on Graph Databases. In International Conference on Database Theory (ICDT). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 177--194 . Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. 2015. Regular Queries on Graph Databases. In International Conference on Database Theory (ICDT). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 177--194."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9676-2"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_2_48_1","volume-title":"Stefania Dumbrava, Olaf Hartig","author":"Sakr Sherif","year":"2020","unstructured":"Sherif Sakr , Angela Bonifati , Hannes Voigt , Alexandru Iosup , Khaled Ammar , Renzo Angles , Walid Aref , Marcelo Arenas , Maciej Besta , Peter A. Boncz , Khuzaima Daudjee , Emanuele Della Valle , Stefania Dumbrava, Olaf Hartig , Bernhard Haslhofer , Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer \u00d6zsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei R. Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, G\u00e1bor Sz\u00e1rnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki. 2020 . The Future is Big Graphs! A Community View on Graph Processing Systems . arXiv:2012.06171 (2020). Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer \u00d6zsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei R. Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, G\u00e1bor Sz\u00e1rnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki. 2020. The Future is Big Graphs! A Community View on Graph Processing Systems. arXiv:2012.06171 (2020)."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00251-2"},{"key":"e_1_3_2_2_51_1","unstructured":"Tigergraph. 2021. GSQL Language Reference. https:\/\/docs.tigergraph.com\/v\/2.3\/dev\/gsql-ref .  Tigergraph. 2021. GSQL Language Reference. https:\/\/docs.tigergraph.com\/v\/2.3\/dev\/gsql-ref ."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3524149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T13:49:04Z","timestamp":1750168144000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":52,"alternative-id":["10.1145\/3517804.3524149","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3524149","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}