id: 06065519
dt: a
an: 06065519
au: Case, John; Jain, Sanjay; Seah, Samuel; Stephan, Frank
ti: Automatic functions, linear time and learning.
so: Cooper, S. Barry (ed.) et al., How the world computes. Turing centenary
    conference and 8th conference on computability in Europe, CiE 2012,
    Cambridge, UK, June 18‒23, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-30869-7/pbk). Lecture Notes in Computer Science 7318, 96-106
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-30870-3_11
ab: Summary: 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.
rv: