The expressive power of analog recurrent neural networks on infinite input streams

Détails

ID Serval
serval:BIB_D2B7F0C17222
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Titre
The expressive power of analog recurrent neural networks on infinite input streams
Périodique
Theoretical Computer Science
Auteur⸱e⸱s
Cabessa  J., Villa  A. E. P.
ISSN
0304-3975
Statut éditorial
Publié
Date de publication
06/2012
Peer-reviewed
Oui
Volume
436
Pages
23-34
Langue
anglais
Résumé
We consider analog recurrent neural networks working on infinite input streams, provide a complete topological characterization of their expressive power, and compare it to the expressive power of classical infinite word reading abstract machines. More precisely, we consider analog recurrent neural networks as language recognizers over the Cantor space, and prove that the classes of image-languages recognized by deterministic and non-deterministic analog networks correspond precisely to the respective classes of image-sets and image-sets of the Cantor space. Furthermore, we show that the result can be generalized to more expressive analog networks equipped with any kind of Borel accepting condition. Therefore, in the deterministic case, the expressive power of analog neural nets turns out to be comparable to the expressive power of any kind of Büchi abstract machine, whereas in the non-deterministic case, analog recurrent networks turn out to be strictly more expressive than any other kind of Büchi or Muller abstract machine, including the main cases of classical automata, image-counter automata, image-counter automata, pushdown automata, and Turing machines.
Mots-clé
analog neural networks, analog computation, topology, Borel sets, analytic sets, ω-Automata, Turing machines
Web of science
Open Access
Oui
Création de la notice
29/01/2013 12:57
Dernière modification de la notice
20/08/2019 16:52
Données d'usage