{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:26:35Z","timestamp":1754195195269},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and pushdown automata. Roughly speaking, one-time nondeterminism means that at the outset the computation is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. We characterize the computational power of one-time nondeterministic finite automata (OTNFAs) and one-time nondeterministic pushdown devices. Moreover, we study the descriptional complexity of these machines. For instance, we show that for an [Formula: see text]-state OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol, [Formula: see text] states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. In case of pushdown automata, the conversion of a nondeterministic to a one-time nondeterministic as well as the conversion of a one-time nondeterministic to a deterministic one turn out to be non-recursive, that is, the trade-offs in size cannot be bounded by any recursive function. <\/jats:p>","DOI":"10.1142\/s012905411940029x","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1069-1089","source":"Crossref","is-referenced-by-count":1,"title":["One-Time Nondeterministic Computations"],"prefix":"10.1142","volume":"30","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S012905411940029XBIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-281-4"},{"key":"S012905411940029XBIB003","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S012905411940029XBIB004","first-page":"193","volume":"8","author":"Goldstine J.","year":"2002","journal-title":"J. UCS"},{"key":"S012905411940029XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"key":"S012905411940029XBIB006","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"S012905411940029XBIB007","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"S012905411940029XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90016-6"},{"key":"S012905411940029XBIB009","doi-asserted-by":"publisher","DOI":"10.1142\/9789812794499_0033"},{"key":"S012905411940029XBIB010","series-title":"SIAM-AMS Proceedings","first-page":"1","volume-title":"Complexity of Computing","volume":"7","author":"Hartmanis J.","year":"1974"},{"key":"S012905411940029XBIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00267-8"},{"key":"S012905411940029XBIB013","doi-asserted-by":"publisher","DOI":"10.1142\/9781848165458_0001"},{"key":"S012905411940029XBIB014","first-page":"37","volume-title":"A Half-Century of Automata Theory: Celebration and Inspiration","author":"Hopcroft J. E.","year":"2000"},{"key":"S012905411940029XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.01.015"},{"key":"S012905411940029XBIB016","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.11"},{"key":"S012905411940029XBIB017","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10854-8_30"},{"key":"S012905411940029XBIB018","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"S012905411940029XBIB019","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"S012905411940029XBIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-41148-3_11"},{"key":"S012905411940029XBIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411940029X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:07:18Z","timestamp":1568876838000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411940029X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":19,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S012905411940029X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411940029x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}