{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T08:22:08Z","timestamp":1792743728525,"version":"4.5.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Regular path queries (RPQs) are an essential component of graph query\nlanguages. Such queries consider a regular expression r and a directed\nedge-labeled graph G and search for paths in G for which the sequence of labels\nis in the language of r. In order to avoid having to consider infinitely many\npaths, some database engines restrict such paths to be trails, that is, they\nonly consider paths without repeated edges. In this paper we consider the\nevaluation problem for RPQs under trail semantics, in the case where the\nexpression is fixed. We show that, in this setting, there exists a trichotomy.\nMore precisely, the complexity of RPQ evaluation divides the regular languages\ninto the finite languages, the class Ttract (for which the problem is\ntractable), and the rest. Interestingly, the tractable class in the trichotomy\nis larger than for the trichotomy for simple paths, discovered by Bagan,\nBonifati, and Groz [JCSS 2020]. In addition to this trichotomy result, we also\nstudy characterizations of the tractable class, its expressivity, the\nrecognition problem, closure properties, and show how the decision problem can\nbe extended to the enumeration problem, which is relevant to practice.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:20)2023","type":"journal-article","created":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T08:20:16Z","timestamp":1701937216000},"source":"Crossref","is-referenced-by-count":6,"title":["A Trichotomy for Regular Trail Queries"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tina","family":"Popp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2023,12,7]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12659\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12659\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T08:20:16Z","timestamp":1701937216000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/8604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:20)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"1903.00226v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1903.00226v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1903.00226","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1903.00226","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,7]]},"article-number":"8604"}}