{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:50:08Z","timestamp":1769975408244,"version":"3.49.0"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,9,17]],"date-time":"2013-09-17T00:00:00Z","timestamp":1379376000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The present work determines the exact nature of {\\em linear time computable}\nnotions which characterise automatic functions (those whose graphs are\nrecognised by a finite automaton). The paper also determines which type of\nlinear time notions permit full learnability for learning in the limit of\nautomatic classes (families of languages which are uniformly recognised by a\nfinite automaton). In particular it is shown that a function is automatic iff\nthere is a one-tape Turing machine with a left end which computes the function\nin linear time where the input before the computation and the output after the\ncomputation both start at the left end. It is known that learners realised as\nautomatic update functions are restrictive for learning. In the present work it\nis shown that one can overcome the problem by providing work tapes additional\nto a resource-bounded base tape while keeping the update-time to be linear in\nthe length of the largest datum seen so far. In this model, one additional such\nwork tape provides additional learning power over the automatic learner model\nand two additional work tapes give full learning power. Furthermore, one can\nalso consider additional queues or additional stacks in place of additional\nwork tapes and for these devices, one queue or two stacks are sufficient for\nfull learning power while one stack is insufficient.<\/jats:p>","DOI":"10.2168\/lmcs-9(3:19)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:44:29Z","timestamp":1385732669000},"source":"Crossref","is-referenced-by-count":7,"title":["Automatic functions, linear time and learning"],"prefix":"10.46298","volume":"Volume 9, Issue 3","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9152-1706","authenticated-orcid":false,"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9152-1706","authenticated-orcid":false,"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2013,9,17]]},"reference":[{"key":"791:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/734\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/734\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:54:48Z","timestamp":1681242888000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,17]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(3:19)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1306.3726","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1306.3726","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,17]]},"article-number":"734"}}