{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T20:58:16Z","timestamp":1648760296866},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p> This paper presents a practical algorithm for the uniform membership problem of labeled multidigraphs of tree-width at most 2 for spanning tree automata. Though the theoretical existence of a linear-time algorithm for the membership problem for graphs of bounded tree-width was shown in the previous study, the implementation of the linear-time algorithm is expected to be impractical because it requires the construction of a finite-state automaton whose size is super-exponential in the size of the tree automaton and the tree-width of graphs. In addition, the tree automaton itself should be a part of the input in practical situations. <\/jats:p>","DOI":"10.1142\/s012905411740007x","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T08:31:43Z","timestamp":1513326703000},"page":"563-581","source":"Crossref","is-referenced-by-count":1,"title":["A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata"],"prefix":"10.1142","volume":"28","author":[{"given":"Akio","family":"Fujiyoshi","sequence":"first","affiliation":[{"name":"Department of Computer and Information Sciences, Ibaraki University, 4-12-1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan"}]}],"member":"219","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"S012905411740007XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"S012905411740007XBIB002","doi-asserted-by":"publisher","DOI":"10.1137\/0607033"},{"key":"S012905411740007XBIB003","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013549"},{"key":"S012905411740007XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S012905411740007XBIB006","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619"},{"key":"S012905411740007XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"S012905411740007XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.006"},{"key":"S012905411740007XBIB013","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.E94.D.233"},{"key":"S012905411740007XBIB015","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9554-x"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411740007X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:20:25Z","timestamp":1565194825000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411740007X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":9,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,12,15]]},"published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1142\/S012905411740007X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411740007x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}