{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T04:47:41Z","timestamp":1648788461445},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> Almost all the decision questions concerning the resource requirements of a computational device are undecidable. Here we want to understand the exact boundary that separates the undecidable from the decidable cases of such problems by considering the time complexity of very simple devices that include NFAs (1-way and 2-way), PDAs and PDAs augmented with counters - and their unambiguous restrictions. We consider several variations - based on whether the bound holds exactly or as an upper-bound and show decidability as well as undecidability results. In the case of decidable problems, we also attempt to determine more precisely the complexity class to which the problem belongs. <\/jats:p>","DOI":"10.1142\/s0129054114400280","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T01:32:14Z","timestamp":1424827934000},"page":"1127-1140","source":"Crossref","is-referenced-by-count":1,"title":["SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS"],"prefix":"10.1142","volume":"25","author":[{"given":"OSCAR H.","family":"IBARRA","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}]},{"given":"BALA","family":"RAVIKUMAR","sequence":"additional","affiliation":[{"name":"Department of Computer and Engineering Science, Sonoma State University, Rohnert Park, CA 94928, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90012-6"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321403"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321254"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90028-3"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744569"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90356-7"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90051-4"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/0207042"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240625"},{"key":"p_14","first-page":"254","author":"Kozen D.","year":"1977","journal-title":"IEEE Conf. on Foundations of Computer Science"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00377-3"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264285"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:14:17Z","timestamp":1565176457000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":15,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400280"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400280","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}