{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:49Z","timestamp":1751429449103,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T00:00:00Z","timestamp":1471564800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2016,8,19]]},"abstract":"<jats:p> We initiate a complexity theoretic study of the language based graph reachability problem (L\u2013REACH) : Fix a language L. Given a graph whose edges are labelled with alphabet symbols of the language L and two special vertices s and t, test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L. We study variants of this problem with different graph classes and different language classes and obtain complexity theoretic characterizations for all of them. Our main results are the following: <\/jats:p><jats:p> Restricting the language using formal language theory we show that the complexity of L\u2013REACH increases with the power of the formal language class. We show that there is a regular language for which the L\u2013REACH is NL-complete even for undirected graphs. In the case of linear languages, the complexity of L\u2013REACH does not go beyond the complexity of L itself. Further, there is a deterministic context-free language L for which L\u2013DAGREACH is LogCFL-complete. We use L\u2013REACH as a lens to study structural complexity. In this direction we show that there is a language A in TC<jats:sup>0<\/jats:sup> for which A\u2013DAGREACH is NP-complete. Using this we show that P vs NP question is equivalent to P vs DAGREACH<jats:sup>\u22121<\/jats:sup>(P) <jats:sup>1<\/jats:sup> question. This leads to the intriguing possibility that by proving DAGREACH<jats:sup>\u22121<\/jats:sup>(P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes. Note that we do not know a way to upward translate the separation of complexity classes. <\/jats:p>","DOI":"10.3233\/fi-2016-1371","type":"journal-article","created":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T14:24:34Z","timestamp":1471616674000},"page":"471-483","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of L-reachability"],"prefix":"10.1177","volume":"145","author":[{"given":"Balagopal","family":"Komarath","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India. , ,"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India. , ,"}]},{"given":"K.S.","family":"Sunil","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India. , ,"}]}],"member":"179","published-online":{"date-parts":[[2016,8,19]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2016-1371","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2016-1371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:50:06Z","timestamp":1751367006000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2016-1371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,19]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,19]]}},"alternative-id":["10.3233\/FI-2016-1371"],"URL":"https:\/\/doi.org\/10.3233\/fi-2016-1371","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2016,8,19]]}}}