On the correspondence between neural folding architectures and tree automata
Auch gedruckt in der BibliothekQAA 5/A4.98,6
FakultätFakultät für Ingenieurwissenschaften und Informatik
Ressourcen- / MedientypBericht, Text
Datum der Freischaltung2013-06-06
The folding architecture together with adequate supervised training algorithms is a special recurrent neural network model designed to solve inductive inference tasks on structured domains. Recently, the generic architecture has been proven as a universal approximator of mappings from rooted labeled ordered trees to real vector spaces. In this article we explore formal correspondences to the automata theory in order to characterize the representational capabilities of different instances of the generic folding architecture. As the main result we prove that simple instances of the folding architecture have the computational power of at least the class of deterministic bottom-up tree automata. All proofs are carried out in a constructive manner and a detailed analysis of the space complexity of the construction schemes is provided. We derive bounds for the principled node complexity of folding architecture implementations of tree automata. The possible embedding of the neural folding architecture into a general knowledge-injection-refinement-extraction framework is briefly discussed.