{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:41Z","timestamp":1750220081046,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":28,"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\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["N00615"],"award-info":[{"award-number":["N00615"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,17]]},"DOI":"10.1145\/3530800.3534531","type":"proceedings-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T22:27:18Z","timestamp":1653344838000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Universal provenance for regular path queries"],"prefix":"10.1145","author":[{"given":"G\u00f6sta","family":"Grahne","sequence":"first","affiliation":[{"name":"Concordia University, Montreal, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyi","family":"Liu","sequence":"additional","affiliation":[{"name":"Concordia University, Montreal, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nematollaah","family":"Shiri","sequence":"additional","affiliation":[{"name":"Concordia University, Montreal, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,12]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1963.263416"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_3_2_1_4_1","first-page":"1","volume-title":"29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference)","volume":"183","author":"Dannert K. M.","year":"2021","unstructured":"K. M. Dannert , E. Gr\u00e4del , M. Naaf , and V. Tannen . Semiring provenance for fixed-point logic. In C. Baier and J. Goubault-Larrecq, editors , 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference) , volume 183 of LIPIcs, pages 17: 1 -- 17 :22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 2021 . K. M. Dannert, E. Gr\u00e4del, M. Naaf, and V. Tannen. Semiring provenance for fixed-point logic. In C. Baier and J. Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference), volume 183 of LIPIcs, pages 17:1--17:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"e_1_3_2_1_5_1","volume-title":"Oct","author":"De Domenico M.","year":"2013","unstructured":"M. De Domenico , A. Lima , P. Mougel , and M. Musolesi . The anatomy of a scientific rumor. Scientific Reports, 3(1) , Oct 2013 . M. De Domenico, A. Lima, P. Mougel, and M. Musolesi. The anatomy of a scientific rumor. Scientific Reports, 3(1), Oct 2013."},{"key":"e_1_3_2_1_6_1","first-page":"312","volume-title":"Approximation to the smallest regular expression for a given regular language","author":"Delgado M.","year":"2005","unstructured":"M. Delgado and J. Morais . Approximation to the smallest regular expression for a given regular language . In M. Domaratzki, A. Okhotin, K. Salomaa, and S. Yu, editors, Implementation and Application of Automata, pages 312 -- 314 , Berlin, Heidelberg, 2005 . Springer Berlin Heidelberg . M. Delgado and J. Morais. Approximation to the smallest regular expression for a given regular language. In M. Domaratzki, A. Okhotin, K. Salomaa, and S. Yu, editors, Implementation and Application of Automata, pages 312--314, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5"},{"key":"e_1_3_2_1_8_1","volume-title":"Automata, languages, and machines. A. Pure and applied mathematics","author":"Eilenberg S.","year":"1974","unstructured":"S. Eilenberg . Automata, languages, and machines. A. Pure and applied mathematics . Academic Press , 1974 . S. Eilenberg. Automata, languages, and machines. A. Pure and applied mathematics. Academic Press, 1974."},{"key":"e_1_3_2_1_9_1","first-page":"153","volume-title":"Joint 2013 EDBT\/ICDT Conferences, ICDT '13 Proceedings","author":"Geerts F.","year":"2013","unstructured":"F. Geerts , G. Karvounarakis , V. Christophides , and I. Fundulaki . Algebraic structures for capturing the provenance of SPARQL queries. In W. Tan, G. Guerrini, B. Catania, and A. Gounaris, editors , Joint 2013 EDBT\/ICDT Conferences, ICDT '13 Proceedings , Genoa, Italy, March 18--22 , 2013 , pages 153 -- 164 . ACM, 2013. F. Geerts, G. Karvounarakis, V. Christophides, and I. Fundulaki. Algebraic structures for capturing the provenance of SPARQL queries. In W. Tan, G. Guerrini, B. Catania, and A. Gounaris, editors, Joint 2013 EDBT\/ICDT Conferences, ICDT '13 Proceedings, Genoa, Italy, March 18--22, 2013, pages 153--164. ACM, 2013."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.001"},{"key":"e_1_3_2_1_11_1","volume-title":"Data provenance. Found. Trends Databases, 9(3--4):209--441","author":"Glavic B.","year":"2021","unstructured":"B. Glavic . Data provenance. Found. Trends Databases, 9(3--4):209--441 , 2021 . B. Glavic. Data provenance. Found. Trends Databases, 9(3--4):209--441, 2021."},{"key":"e_1_3_2_1_12_1","volume-title":"Semiring provenance for first-order model checking. CoRR, abs\/1712.01980","author":"Gr\u00e4del E.","year":"2017","unstructured":"E. Gr\u00e4del and V. Tannen . Semiring provenance for first-order model checking. CoRR, abs\/1712.01980 , 2017 . E. Gr\u00e4del and V. Tannen. Semiring provenance for first-order model checking. CoRR, abs\/1712.01980, 2017."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.09.025"},{"key":"e_1_3_2_1_15_1","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman . Introduction to Automata Theory, Languages and Computation . Addison-Wesley , 1979 . J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"e_1_3_2_1_17_1","volume-title":"Polynomials for Multidimensional Provenance in Graph Databases. Master's Thesis","author":"Liu T.","year":"2021","unstructured":"T. Liu . Polynomials for Multidimensional Provenance in Graph Databases. Master's Thesis , Concordia University , 2021 . T. Liu. Polynomials for Multidimensional Provenance in Graph Databases. Master's Thesis, Concordia University, 2021."},{"key":"e_1_3_2_1_18_1","volume-title":"6th Workshop on the Theory and Practice of Provenance, TaPP'14","author":"Luttenberger M.","year":"2014","unstructured":"M. Luttenberger and M. Schlund . Regular expressions for provenance. In A. Chapman, B. Lud\u00e4scher, and A. Schreiber, editors , 6th Workshop on the Theory and Practice of Provenance, TaPP'14 , Cologne, Germany, June 12--13 , 2014 . USENIX Association, 2014. M. Luttenberger and M. Schlund. Regular expressions for provenance. In A. Chapman, B. Lud\u00e4scher, and A. Schreiber, editors, 6th Workshop on the Theory and Practice of Provenance, TaPP'14, Cologne, Germany, June 12--13, 2014. USENIX Association, 2014."},{"key":"e_1_3_2_1_19_1","first-page":"18","volume-title":"ICDT 2019 - 22nd International Conference on Database Theory","author":"Maniu S.","year":"2019","unstructured":"S. Maniu , P. Senellart , and S. Jog . An experimental study of the treewidth of real-world graph data . In ICDT 2019 - 22nd International Conference on Database Theory , page 18 , Lisbon, Portugal , Mar. 2019 . S. Maniu, P. Senellart, and S. Jog. An experimental study of the treewidth of real-world graph data. In ICDT 2019 - 22nd International Conference on Database Theory, page 18, Lisbon, Portugal, Mar. 2019."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.31.16"},{"key":"e_1_3_2_1_22_1","volume-title":"10th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2018","author":"Ramusat Y.","year":"2018","unstructured":"Y. Ramusat , S. Maniu , and P. Senellart . Semiring provenance over graph databases. In M. Herschel, editor , 10th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2018 , London, UK, July 11--12 , 2018 . USENIX Association, 2018. Y. Ramusat, S. Maniu, and P. Senellart. Semiring provenance over graph databases. In M. Herschel, editor, 10th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2018, London, UK, July 11--12, 2018. USENIX Association, 2018."},{"key":"e_1_3_2_1_23_1","first-page":"73","volume-title":"Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021","author":"Ramusat Y.","year":"2021","unstructured":"Y. Ramusat , S. Maniu , and P. Senellart . Provenance-based algorithms for rich queries over graph databases. In Y. Velegrakis, D. Zeinalipour-Yazti, P. K. Chrysanthis, and F. Guerra, editors , Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021 , Nicosia, Cyprus, March 23 - 26 , 2021 , pages 73 -- 84 . OpenProceedings.org, 2021. Y. Ramusat, S. Maniu, and P. Senellart. Provenance-based algorithms for rich queries over graph databases. In Y. Velegrakis, D. Zeinalipour-Yazti, P. K. Chrysanthis, and F. Guerra, editors, Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021, Nicosia, Cyprus, March 23 - 26, 2021, pages 73--84. OpenProceedings.org, 2021."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1629683"},{"key":"e_1_3_2_1_25_1","volume-title":"Automata and rational expressions. CoRR, abs\/1502.03573","author":"Sakarovitch J.","year":"2015","unstructured":"J. Sakarovitch . Automata and rational expressions. CoRR, abs\/1502.03573 , 2015 . J. Sakarovitch. Automata and rational expressions. CoRR, abs\/1502.03573, 2015."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051528.3051533"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902305"},{"key":"e_1_3_2_1_28_1","volume-title":"8th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2016","author":"Yan Z.","year":"2016","unstructured":"Z. Yan , V. Tannen , and Z. G. Ives . Fine-grained provenance for linear algebra operators. In S. C. Boulakia, editor , 8th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2016 , Washington, D.C., USA, June 8--9 , 2016 . USENIX Association, 2016. Z. Yan, V. Tannen, and Z. G. Ives. Fine-grained provenance for linear algebra operators. In S. C. Boulakia, editor, 8th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2016, Washington, D.C., USA, June 8--9, 2016. USENIX Association, 2016."}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Philadelphia Pennsylvania","acronym":"SIGMOD\/PODS '22"},"container-title":["Proceedings of the 14th International Workshop on the Theory and Practice of Provenance"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530800.3534531","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530800.3534531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:25Z","timestamp":1750183765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530800.3534531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":28,"alternative-id":["10.1145\/3530800.3534531","10.1145\/3530800"],"URL":"https:\/\/doi.org\/10.1145\/3530800.3534531","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}