{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:13Z","timestamp":1750306393707,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>\n            We present two restricted versions of one-tape Turing machines. Both characterize the class of context-free languages. In the first version, proposed by Hibbard in 1967 and called\n            <jats:italic>limited automata<\/jats:italic>\n            , each tape cell can be rewritten only in the first\n            <jats:italic>d<\/jats:italic>\n            visits, for a fixed constant\n            <jats:italic>d<\/jats:italic>\n            \u2265 2. Furthermore, for\n            <jats:italic>d<\/jats:italic>\n            = 2 deterministic limited automata are equivalent to deterministic pushdown automata, namely they characterize deterministic context-free languages. Further restricting the possible operations, we consider\n            <jats:italic>strongly limited automata<\/jats:italic>\n            . These models still characterize context-free languages. However, the deterministic version is less powerful than the deterministic version of limited automata. In fact, there exist deterministic context-free languages that are not accepted by any deterministic strongly limited automaton.\n          <\/jats:p>","DOI":"10.1145\/2818936.2818947","type":"journal-article","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T12:36:15Z","timestamp":1441715775000},"page":"37-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Guest Column"],"prefix":"10.1145","volume":"46","author":[{"given":"Giovanni","family":"Pighizzini","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Italy"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647892.739610"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2682"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321127.321132"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321450.321464"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.05.005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90399-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90513-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321495.321508"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050050"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"e_1_2_1_12_1","first-page":"153","volume-title":"DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings. Lecture Notes in Computer Science","volume":"9118","author":"Kutrib M.","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1965.14"},{"key":"e_1_2_1_14_1","unstructured":"McNaughton R. Papert S.A.: Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press (1971)   McNaughton R. Papert S.A.: Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press (1971)"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410800598X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90054-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90151-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31653-1_12"},{"key":"e_1_2_1_19_1","first-page":"430","volume-title":"6th Symposium, Tatranska Lomnica, Czechoslovakia","volume":"53","author":"Peckel J.","year":"1977"},{"issue":"1","key":"e_1_2_1_20_1","first-page":"107","article-title":"Nondeterministic one-tape off-line Turing machines. Journal of Automata","volume":"14","author":"Pighizzini G.","year":"2009","journal-title":"Languages and Combinatorics"},{"key":"e_1_2_1_21_1","unstructured":"Pighizzini G.: Strongly limited automata. Fundam. Inform. (to appear) a preliminary version appeared in: Bensch S. Freund R. Otto F. (eds.) Sixth Workshop on Non-Classical Models for Automata and Applications - NCMA 2014 Kassel Germany July 28-29 2014. Proceedings. books@ocg.at vol. 304 pp. 191--206. Osterreichische Computer Gesellschaft (2014)  Pighizzini G.: Strongly limited automata. Fundam. Inform. (to appear) a preliminary version appeared in: Bensch S. Freund R. Otto F. (eds.) Sixth Workshop on Non-Classical Models for Automata and Applications - NCMA 2014 Kassel Germany July 28-29 2014. Proceedings. books@ocg.at vol. 304 pp. 191--206. Osterreichische Computer Gesellschaft (2014)"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114400140"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1148"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0198"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1965.11"},{"key":"e_1_2_1_26_1","first-page":"58355","volume-title":"Lecture Notes in Computer Science","volume":"843","author":"Szepietowski A.","year":"1994"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.031"},{"key":"e_1_2_1_28_1","first-page":"33","article-title":"Turing machine computations with logarithmic delay, (in russian)","volume":"3","author":"Trakhtenbrot B.A.","year":"1964","journal-title":"Algebra I Logica"},{"key":"e_1_2_1_29_1","unstructured":"Wagner K.W. Wechsung G.: Computational Complexity. D. Reidel Publishing Company Dordrecht (1986)  Wagner K.W. Wechsung G.: Computational Complexity. D. Reidel Publishing Company Dordrecht (1986)"},{"key":"e_1_2_1_30_1","first-page":"457","volume-title":"4th Symposium, Mari\u00e1nsk\u00e9 L\u00e1zne, Czechoslovakia","volume":"32","author":"Wechsung G.","year":"1975"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90010-0"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818936.2818947","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818936.2818947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:17Z","timestamp":1750223237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818936.2818947"}},"subtitle":["One-Tape Turing Machine Variants and Language Recognition"],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1145\/2818936.2818947"],"URL":"https:\/\/doi.org\/10.1145\/2818936.2818947","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2015,9]]},"assertion":[{"value":"2015-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}