{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:33:23Z","timestamp":1648514003075},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O( log n) time. Furthermore, we present a series of strings that require [Formula: see text] time and space to answer reachability queries in O( log n) time for the same algorithm. Exhaustive computational calculations for strings of length n \u2264 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O( log n) time with a worst case time and space preprocessing complexity of [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054108005590","type":"journal-article","created":{"date-parts":[[2008,2,20]],"date-time":"2008-02-20T04:46:31Z","timestamp":1203482791000},"page":"147-162","source":"Crossref","is-referenced-by-count":0,"title":["REACHABILITY ON SUFFIX TREE GRAPHS"],"prefix":"10.1142","volume":"19","author":[{"given":"YASUTO","family":"HIGA","sequence":"first","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Motooka, Nishi-ku Fukuoka 819-0395, Japan"}]},{"given":"HIDEO","family":"BANNAI","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Motooka, Nishi-ku Fukuoka 819-0395, Japan"}]},{"given":"SHUNSUKE","family":"INENAGA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Electrical Engineering, Kyushu University, Nishi-ku Fukuoka 819-0395, Japan"}]},{"given":"MASAYUKI","family":"TAKEDA","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Motooka, Nishi-ku Fukuoka 819-0395, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90049-I"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2004.36"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90019-8"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00209-5"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:29:25Z","timestamp":1565177365000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":7,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0129054108005590"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005590","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}