{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:31Z","timestamp":1750307371783,"version":"3.41.0"},"reference-count":3,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[1974,1,1]],"date-time":"1974-01-01T00:00:00Z","timestamp":126230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["GJ-34671"],"award-info":[{"award-number":["GJ-34671"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[1974,1]]},"abstract":"<jats:p>Hopcroft and Ullman (problem 3.10 [1]) pose the amusing question of whether the \"first third\" of a regular language L, FIRST-THIRD(L) = {x| x is a prefix of a member of L of length 3|x|}, is necessarily regular. To see that it is, we can adapt of 1-way deterministic finite-state acceptor (an FA, for short) for L to get a 2-way non-deterministic finite-state acceptor with endmarkers for FIRST-THIRD(L). This acceptor behaves like the FA on x until it reaches the right endmarker, and then it uses another pass over x at half speed to behave like the FA on some nondeterministically chosen continuation of length 2|x|. That such an acceptor accepts a regular language follows from an argument similar to that of Shepherdson for deterministic acceptors [2].<\/jats:p>","DOI":"10.1145\/1811129.1811132","type":"journal-article","created":{"date-parts":[[2010,6,11]],"date-time":"2010-06-11T18:52:51Z","timestamp":1276282371000},"page":"25-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A note on prefixes of regular languages"],"prefix":"10.1145","volume":"6","author":[{"given":"Joel I.","family":"Seiferas","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1974,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Formal Languages and Their Relation to Automata","author":"Hopcroft J. E.","year":"1969","unstructured":"Hopcroft , J. E. and Ullman , J. D. , Formal Languages and Their Relation to Automata , Addison-Wesley , Reading, Mass ., 1969 , p. 45. Hopcroft, J. E. and Ullman, J. D., Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969, p. 45."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0198"},{"key":"e_1_2_1_3_1","volume-title":"Automatentheorie und formale Sprachen, Bericht Tagung Oberwolfach Okt. 1969","author":"Siefkes D.","year":"1970","unstructured":"Siefkes , D. , Decidable extensions of monadic second order successor arithmetic . In Automatentheorie und formale Sprachen, Bericht Tagung Oberwolfach Okt. 1969 (ed. J. D\u00f6rr u. G. Hotz) Mannheim 1970 , 441--472. Siefkes, D., Decidable extensions of monadic second order successor arithmetic. In Automatentheorie und formale Sprachen, Bericht Tagung Oberwolfach Okt. 1969 (ed. J. D\u00f6rr u. G. Hotz) Mannheim 1970, 441--472."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1811129.1811132","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1811129.1811132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:54Z","timestamp":1750245774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1811129.1811132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,1]]},"references-count":3,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1974,1]]}},"alternative-id":["10.1145\/1811129.1811132"],"URL":"https:\/\/doi.org\/10.1145\/1811129.1811132","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[1974,1]]},"assertion":[{"value":"1974-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}