Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-30870-3_11
Title: Automatic functions, linear time and learning
Authors: Case, J.
Jain, S. 
Seah, S.
Stephan, F. 
Issue Date: 2012
Source: Case, J.,Jain, S.,Seah, S.,Stephan, F. (2012). Automatic functions, linear time and learning. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7318 LNCS : 96-106. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-30870-3_11
Abstract: The present work determines the exact nature of linear time computable notions which characterise automatic functions (those whose graphs are recognised by a finite automaton). The paper also determines which type of linear time notions permit full learnability for learning in the limit of automatic classes (families of languages which are uniformly recognised by a finite automaton). In particular it is shown that a function is automatic iff there is a one-tape Turing machine with a left end which computes the function in linear time where the input before the computation and the output after the computation both start at the left end. It is known that learners realised as automatic update functions are restrictive for learning. In the present work it is shown that one can overcome the problem by providing work-tapes additional to a resource-bounded base tape while keeping the update-time to be linear in the length of the largest datum seen so far. In this model, one additional such worktape provides additional learning power over the automatic learner model and the two-work-tape model gives full learning power. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/43231
ISBN: 9783642308697
ISSN: 03029743
DOI: 10.1007/978-3-642-30870-3_11
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Dec 18, 2017

Page view(s)

59
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.