Automatic functions, linear time and learning
The present work determines the exact nature of {\em 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 aut...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2013-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/734/pdf |
| _version_ | 1797268734365138944 |
|---|---|
| author | John Case Sanjay Jain Frank Stephan Frank Stephan |
| author_facet | John Case Sanjay Jain Frank Stephan Frank Stephan |
| author_sort | John Case |
| collection | DOAJ |
| description | The present work determines the exact nature of {\em 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
work tape provides additional learning power over the automatic learner model
and two additional work tapes give full learning power. Furthermore, one can
also consider additional queues or additional stacks in place of additional
work tapes and for these devices, one queue or two stacks are sufficient for
full learning power while one stack is insufficient. |
| first_indexed | 2024-04-25T01:37:11Z |
| format | Article |
| id | doaj.art-ec8ec2f1bca54bf2bddd609da4a8de02 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:11Z |
| publishDate | 2013-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-ec8ec2f1bca54bf2bddd609da4a8de022024-03-08T09:29:28ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742013-09-01Volume 9, Issue 310.2168/LMCS-9(3:19)2013734Automatic functions, linear time and learningJohn CaseSanjay JainFrank Stephanhttps://orcid.org/0000-0001-9152-1706Frank Stephanhttps://orcid.org/0000-0001-9152-1706The present work determines the exact nature of {\em 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 work tape provides additional learning power over the automatic learner model and two additional work tapes give full learning power. Furthermore, one can also consider additional queues or additional stacks in place of additional work tapes and for these devices, one queue or two stacks are sufficient for full learning power while one stack is insufficient.https://lmcs.episciences.org/734/pdfcomputer science - formal languages and automata theory |
| spellingShingle | John Case Sanjay Jain Frank Stephan Frank Stephan Automatic functions, linear time and learning Logical Methods in Computer Science computer science - formal languages and automata theory |
| title | Automatic functions, linear time and learning |
| title_full | Automatic functions, linear time and learning |
| title_fullStr | Automatic functions, linear time and learning |
| title_full_unstemmed | Automatic functions, linear time and learning |
| title_short | Automatic functions, linear time and learning |
| title_sort | automatic functions linear time and learning |
| topic | computer science - formal languages and automata theory |
| url | https://lmcs.episciences.org/734/pdf |
| work_keys_str_mv | AT johncase automaticfunctionslineartimeandlearning AT sanjayjain automaticfunctionslineartimeandlearning AT frankstephan automaticfunctionslineartimeandlearning AT frankstephan automaticfunctionslineartimeandlearning |