{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T16:57:18Z","timestamp":1771952238148,"version":"3.50.1"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,11]]},"abstract":"<jats:p> Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to a single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d \u2265 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Sch\u00fctzenberger representation for contextfree languages, we present a new conversion from context-free languages into 2-limited automata. <\/jats:p>","DOI":"10.1142\/s0129054114400140","type":"journal-article","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T03:48:03Z","timestamp":1421207283000},"page":"897-916","source":"Crossref","is-referenced-by-count":30,"title":["LIMITED AUTOMATA AND REGULAR LANGUAGES"],"prefix":"10.1142","volume":"25","author":[{"given":"GIOVANNI","family":"PIGHIZZINI","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano via Comelico 39, 20135 Milano, Italy"}]},{"given":"ANDREA","family":"PISONI","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano via Comelico 39, 20135 Milano, Italy"}]}],"member":"219","published-online":{"date-parts":[[2015,1,14]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01371727"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90399-2"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90513-X"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.013"},{"issue":"3","key":"p_9","first-page":"287","volume":"5","author":"Mereghetti C.","year":"2000","journal-title":"Languages and Combinatorics"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979935431X"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31653-1_12"},{"issue":"1","key":"p_12","first-page":"107","volume":"14","author":"Pighizzini G.","year":"2009","journal-title":"Languages and Combinatorics"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0198"},{"issue":"2","key":"p_18","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:37:02Z","timestamp":1565116622000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":13,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2015,1,14]]},"published-print":{"date-parts":[[2014,11]]}},"alternative-id":["10.1142\/S0129054114400140"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400140","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11]]}}}